c - 循环索引的C语言:在新CPU中正向索引是否更快？

Question

在我订阅的邮件列表中，两个相当博学的(IMO)程序员在讨论一些优化的代码，并说出一些类似的内容:

On the CPUs released 5-8 years ago, it was slightly faster to iterate for loops backwards (e.g. for (int i=x-1; i>=0; i--) {...}) because comparing i to zero is more efficient than comparing it to some other number. But with very recent CPUs (e.g. from 2008-2009) the speculative loader logic is such that it works better if the for loop is iterated forward (e.g. for (int i=0; i< x; i++) {...}).

我的问题是，这是真的吗？ CPU的实现最近是否发生了变化，以至于正向循环迭代现在比反向迭代具有优势？如果是这样，对此有何解释？即发生了什么变化？

(是的，我知道，过早的优化是万恶之源，请在担心微优化之前查看我的算法，等等。。。我主要是好奇的)

Answer 1

您实际上是在询问预取，而不是循环控制逻辑。

通常，控制逻辑不会决定循环性能(即每次递增/递减以及每次检查的条件)。除了非常紧密的循环外，执行这些操作所花费的时间是无关紧要的。如果您对此感兴趣，请查看John Knoeller's answer，了解8086计数器寄存器上的详细信息，以及为什么过去倒计数更为有效的原因可能如此。正如John所说，branch prediction(以及推测)在这里的表现中也可以发挥作用，instruction prefetching也可以。

当迭代顺序更改循环接触内存的顺序时，会严重影响性能。请求内存地址的顺序可能会影响到cache中的内容，以及在不再有空间获取新缓存行时从缓存中清除的内容。与比较，递增或递减相比，必须比所需时间更频繁地访问内存的成本要高得多。在现代CPU上，从处理器到内存的访问可能要花费数千个周期，并且您的处理器可能必须闲置一段时间。

您可能对caches很熟悉，所以在这里我不会赘述所有这些细节。您可能不知道的是，现代处理器会使用大量的预取器来尝试预测在内存层次结构的不同级别上下一步需要什么数据。一旦做出预测，他们便会尝试从内存或低级缓存中提取数据，以便在处理数据时拥有所需的数据。根据他们掌握下一步需求的程度，使用它们的性能可能会有所改善，也可能不会有所改善。

看看Intel's guide to optimizing for hardware prefetchers。列出了四个预取器； NetBurst芯片有两个:

NetBurst的硬件预取器可以检测到向前或向后的内存访问流，并将尝试将这些位置的数据加载到L2缓存中。

NetBurst还具有一个相邻缓存行(ACL)预取程序，当您提取第一个时，它将自动加载两个相邻的缓存行。

和两个 Core:

Core具有稍微更复杂的硬件预取器；它不仅可以检测连续引用流，还可以检测跨步访问，因此，如果您每隔一个元素，每4个元素等等遍历一个数组，它将做得更好。

Core还具有ACL预取程序，例如NetBurst。

如果要向前遍历数组，则将生成一堆顺序的，通常是连续的内存引用。对于前向循环，ACL预取器的性能要好得多(因为您最终将使用这些后续的缓存行)，而对于后向循环，ACL预取器的性能要好得多，但是如果预取器可以检测到这种情况，则可以向后进行内存引用(与硬件一样)预取器)。 Core上的硬件预取器可以检测到步幅，这有助于进行更复杂的数组遍历。

这些简单的启发式 可能会在某些情况下使您陷入麻烦。例如，英特尔实际上建议您关闭服务器的相邻高速缓存行预取，因为与台式机用户相比，它们倾向于提供更多的随机内存引用。在服务器上，不使用相邻高速缓存行的可能性更高，因此，获取您实际上不打算使用的数据将污染高速缓存(将不需要的数据填充到高速缓存中)，从而降低性能。有关解决此类问题的更多信息，请参阅Supercomputing 2009上using machine learning to tune prefetchers in large data centers上的本文。谷歌上有些人在那张纸上。性能是他们非常关心的事情。

简单的启发式方法无法帮助您使用更复杂的算法，因此您可能必须开始考虑L1，L2等高速缓存的大小。例如，图像处理通常要求您对2D图像的各个部分执行某些操作，但是遍历图像的顺序可能会影响有用部分在缓存中的保留状态，而不会被逐出。如果您对这种事情感兴趣，请看看Z-order traversals和loop tiling。这是将图像数据的2D局部性映射到内存的1D局部性以提高性能的非常基本的示例。在这方面，编译器并不总是能够以最佳方式重组代码，但是手动重组C代码可以大大提高缓存性能。

我希望这可以使您了解迭代顺序如何影响内存性能。它的确取决于特定的体系结构，但是想法是笼统的。如果您可以在AMD和Power上理解预取功能，那么您应该能够理解它，而您实际上并不需要知道汇编程序来构造代码以利用内存。您只需要了解一些计算机体系结构。