使用更多的内存会降低性能吗？

Question

特别是记忆化会使性能下降吗？性能增加是否是线性的？

我有一个函数需要调用一些复杂的数学函数200,000,000次。如果不使用记忆化（保存值/缓存），需要1分钟才能完成。如果我保存这些值-大约有5,000,000个唯一条目-它仍然需要30秒。这些值是双倍精度，我正在使用自己的哈希函数，哈希表大小约为20,000,000（为了使计算哈希值变得更容易）。

但是，复杂的数学函数仍然只运行了5,000,000次（我甚至使用计数器检查过）。为什么它没有以大约5,000,000/200,000,000的速度运行？

在此之前，我没有使用任何大型数据结构，现在我使用了一个大小为20,000,000的双数组来进行澄清。我不知道这是否会有所不同。

- mergesort

---

“这要看情况”可能是考虑到问题的提出方式，唯一明智的答案。请记住，具有均匀随机访问的大型数据结构可能会产生大量缓存未命中，这是非常昂贵的。也许可以使用缓存分析器（如massif）对其进行分析。 - Kerrek SB

谢谢！我以前用过Massif，我认为那是一个堆分析器。在搜索缓存分析器后，我看到了Cachegrind（可能是你指的）。否则我永远不会找到它。 - mergesort

数学有多复杂？现在的CPU速度非常快，但内存访问却很慢。对于40兆字节的随机访问，每次访问可能需要1000个或更多的周期，这相当于几个超越函数或近千个简单算术运算。 - R.. GitHub STOP HELPING ICE

顺便说一下，我通常会把记忆化放在“被认为有害”的垃圾箱里。除非在极端情况下，它本来就只是略微有用的，而且在考虑到现实世界中的全局状态，特别是没有受到互斥锁保护的全局状态时，这种效用更是微不足道。为了使记忆化在可能存在线程的程序中工作，需要添加必要的锁定，这将使其变得更加浪费时间。 - R.. GitHub STOP HELPING ICE

数学并不是很复杂。它实际上是为了一个项目和学习记忆化和优化。谢谢！ - mergesort

@angrymonkey：是的，抱歉，我混淆了两个。确实是Cachegrind。 - Kerrek SB

Answer 1

更多的内存使用通常会显著降低性能——主要问题在于大型数据结构无法适应处理器缓存，需要更长时间才能访问。

在现代处理器上，您会发现重新计算数学计算比从内存中获取结果要快得多。内存访问基本上是瓶颈，而不是 CPU。

此外，如果您正在进行memoization，则要注意哈希和查找函数的潜在开销。特别是，如果您没有正确实现哈希函数并且有许多哈希碰撞，则可能会遭受非常昂贵的查找费用。

- mikera

Answer 2

所有性能问题的答案都是“进行基准测试并找出答案”。始终如此。因此，您的实际运行时结果是您的答案-从经验上来看，它的表现就是这样。您可以使用诸如valgrind的callgrind/cachegrind工具来了解原因。

现在，我要忽略你谈论哈希的事实-我认为你知道，如果哈希计算的成本占运行函数体成本的显著比例，备忘录化将无济于事。因此，为了下面的目的，假设哈希的成本为零。

话虽如此，CPU密集型代码性能中最大的因素之一是缓存命中率。这是您的处理器在查找信息时是否必须转到RAM以获取它；如果它已经在缓存中热了，访问延迟会低数千倍，CPU会更快地完成工作（我有点简化了，因为不是所有内存命中都会导致流水线停顿，但这是其要旨）。

因此，尽管“使用更多内存”与性能下降没有直接相关性（我的意思是，使用它的“行为”确实会导致性能下降，但我假设您在这里谈论的不是分配对象的成本），但当您拥有更广泛的RAM区域，其中可能存在您需要的内容时，得到缓存命中的几率较低，这可能会严重降低代码的运行速度。

备忘录化仅在函数执行时间较长时才是优胜者。通常情况下是这样，但这是一种权衡，并且即使在理想情况下，将十个函数调用备忘录化为五个将永远不会给您带来50％的理论加速。

这种反直觉的行为（“但Borealid，我正在做更多的工作，怎么可能更快？！”）是一个典型例子，说明为什么您应该总是仔细检查您实施的“优化”是否提高了性能。过早地进行优化是万恶之源。

- Borealid

---

不幸的是，在这种情况下，标准建议进行性能分析并不一定非常有用。至少存在两个明显的问题。首先，为了使分析结果更有意义，通常需要让系统的其余部分尽可能接近空闲状态，但在这种情况下，这可能会影响您的结果。其次，开发人员运行的程序和用户运行的程序通常截然不同，这也会影响结果。底线是：除非您可以在用户的机器上以他们正常运行的方式进行分析，否则性能分析可能会产生无用的结果。 - Jerry Coffin

所以我使用了 CacheGrind 来观察命中率（或者实际上是缺失率），发现大约为 0.9%。我认为这已经足够实现更高的性能提升了，但事实并非如此。这里到底出了什么问题？ - mergesort

@JerryCoffin 这并不完全正确。分析结果用于确定热点位置以及特定更改是优化还是劣化。通常最好在尽可能接近目标的环境中运行，但即使没有访问其精确设置，您也可以推断出什么是一个好主意。angrymonkey：如果您几乎从不错过缓存，则应查看您花费时间的位置（callgrind）。备忘录实现和旧实现之间发生了什么变化？ - Borealid