Ale*_*pin 31 optimization caching loops
我只是偶然发现了这篇博文.作者展示了两个循环通过矩形并计算某些东西的代码示例(我的猜测是计算代码只是一个占位符).在其中一个示例中,他垂直扫描矩形,另一个水平扫描矩形.然后他说第二个是最快的,每个程序员都应该知道原因.现在我不能成为程序员,因为对我来说它看起来完全一样.任何人都可以向我解释一个吗？
谢谢.
Rob*_*ick 54
缓存一致性.当您水平扫描时,您的数据将在内存中更加紧密,因此您将减少缓存未命中率,从而提高性能.对于足够小的矩形,这无关紧要.
答案已被接受,但我不认为这是整个故事.
是的,缓存是所有这些元素必须以某种顺序存储在内存中的一个重要原因.如果按照存储顺序对它们进行索引,则可能会减少缓存未命中数.有可能.
另一个问题(许多答案也提到)是几乎每个处理器都有一个非常快速的整数增量指令.它们通常没有非常快的"增加一定量乘以第二个任意数量".当你指数"反对谷物"时,这就是你所要求的.
第三个问题是优化.已经对优化这种循环进行了大量的努力和研究,如果您以某种合理的顺序对其进行索引,那么您的编译器将更有可能将这些优化之一置于其中.
缓存确实是原因,但是如果你想知道论证的内容,你可以看看U. Drepper的"每个程序员应该知道的内存":
http://people.redhat.com/drepper/cpumemory.pdf
稍微扩展以前的答案：
通常，作为程序员，我们可以将程序的可寻址内存视为一个平面的字节数组，从 0x00000000 到 0xFFFFFFFF。操作系统会保留其中的一些地址（比如所有低于 0x800000000 的地址）供自己使用，但我们可以对其他地址做我们喜欢做的事情。所有这些内存位置都位于计算机的 RAM 中，当我们想要读取它们或写入它们时，我们会发出适当的指令。
但这不是真的！这个简单的进程内存模型有很多复杂性：虚拟内存、交换和缓存。
与 RAM 对话需要相当长的时间。它比进入硬盘快得多，因为不涉及任何旋转板或磁铁，但按照现代 CPU 的标准，它仍然很慢。因此，当您尝试从内存中的特定位置读取数据时，您的 CPU 不会只是将该位置读取到寄存器中并称其为良好。相反，它将该位置/和一堆附近的位置/读取到位于CPU 上的处理器缓存中，并且可以比主内存更快地访问。
现在我们对计算机的行为有了更复杂但更正确的看法。当我们尝试读取内存中的某个位置时，首先我们会查看处理器缓存以查看该位置的值是否已经存储在那里。如果是，我们使用缓存中的值。如果不是，我们将在主内存中进行更长时间的访问，检索该值以及它的几个邻居并将它们粘贴到缓存中，踢出一些以前存在的内容以腾出空间。
现在我们可以看到为什么第二个代码片段比第一个更快。在第二个例子中，我们第一次访问a[0]，b[0]和c[0]。每个值被缓存，与他们的邻居，说一起a[1..7]，b[1..7]和c[1..7]。然后当我们访问a[1], b[1], 和 时c[1]，它们已经在缓存中，我们可以快速读取它们。最终我们到达a[8]，并且必须再次访问 RAM，但是八次中有七次我们使用了很好的快速缓存内存，而不是笨重的慢速 RAM 内存。
（那么，为什么不访问a，b和c踢对方从缓存中？这是一个有点复杂，但本质上是处理器决定在那里通过其地址存储在缓存中的给定值，所以三个对象不在附近彼此在空间上不太可能缓存到同一位置。）
相比之下，请考虑 lbrandy 帖子中的第一个片段。我们首先阅读a[0], b[0], and c[0], 缓存a[1..7], b[1..7], and c[1..7]。然后，我们访问a[width]，b[width]和c[width]。假设宽度 >= 8（可能是这样，否则我们不会关心这种低级优化），我们必须再次访问 RAM，缓存一组新值。当我们到达 时a[1]，它可能已经被踢出缓存，为其他东西腾出空间。在比处理器缓存大的三个阵列的非常罕见的情况下，很可能 / 每次读取 / 都会错过缓存，从而极大地降低性能。
这是对现代缓存行为的非常高级别的讨论。对于更深入和技术性的内容，这看起来像是对该主题的彻底但可读的处理。