C for循环索引：在新CPU中前向索引更快？
在我订阅的邮件列表中，两位相当知识渊博的（IMO）程序员正在讨论一些优化的代码，并说出以下内容：
在5 – 8年前发布的CPU上，向后循环迭代的速度稍快（ 例如，
for (int i=x-1; i>=0; i--) {...}），因为将i与零进行比较比将其与其他数字相比更有效。 但是对于非常近期的CPU（ 例如从2008年到2009年），推测性加载器逻辑使得如果for循环向前迭代它会更好（ 例如for (int i=0; i< x; i++) {...}） 。
我的问题是，这是真的吗？ 最近是否更改了CPU实现，这样前向循环迭代现在比后向迭代有优势？ 如果是这样，对此有何解释？ 即改变了什么？
（是的，我知道，过早的优化是所有邪恶的根源，在考虑微优化之前检查我的算法等等…大多数我只是好奇）
你真的在询问预取，而不是关于循环控制逻辑。
通常，循环性能不会由控制逻辑决定（即增量/减量和每次检查的条件）。 除了非常紧凑的循环外，做这些事情所花费的时间是无关紧要的。 如果您对此感兴趣，请查看John Knoeller关于8086计数器寄存器具体细节的答案 ，以及为什么在倒计时更有效率的情况下可能会如此。 正如John所说， 分支预测 （以及推测）可以在这里发挥作用，就像指令预取一样 。
当迭代顺序改变循环接触内存的顺序时，它会显着影响性能。 请求内存地址的顺序可能会影响缓存中的内容，以及当不再有空间获取新缓存行时从缓存中逐出的内容。 必须比不需要更频繁地访问内存比比较，增量或减少要昂贵得多。 在现代CPU上，从处理器到内存可能需要数千个周期，而处理器可能必须在部分或全部时间内空闲。
你可能熟悉缓存 ，所以我不会在这里详述所有细节。 您可能不知道的是，现代处理器使用了大量预取器来尝试预测接下来在不同级别的内存层次结构中需要哪些数据。 一旦他们预测到，他们会尝试从内存或较低级别的缓存中提取数据，以便在您处理它时获得所需的内容。 根据他们接下来的需求，您的表现在使用时可能会有所提高，也可能不会提高。
请查看英特尔针对硬件预取程序进行优化的指南 。 列出了四个prefetchers; 两个用于NetBurst芯片：
- NetBurst的硬件预取器可以向前或向后检测内存访问流，并尝试将这些位置的数据加载到L2缓存中。
- NetBurst 还有一个相邻的缓存行（ACL）预取程序 ，当你获取第一个缓存行时 ，它会自动加载两个相邻的缓存行。
和两个核心 ：
- Core有一个稍微复杂的硬件预取器; 除了连续的引用流之外，它还可以检测跨步访问，因此如果每隔一个元素，每隔4个步骤遍历一个数组，它会做得更好。
- Core还有像NetBurst这样的ACL预取器。
如果您正在向前遍历数组，那么您将生成一堆连续的，通常是连续的内存引用。 ACL预取程序对于正向循环（因为你最终会使用那些后续缓存行）要比向后循环更好，但是如果预取程序可以检测到这种情况，你可以做好向后的内存引用（就像硬件一样）预取）。 Core上的硬件预取程序可以检测步幅，这有助于更复杂的数组遍历。
在某些情况下，这些简单的启发式方法可能会让您陷入困境。 例如，英特尔实际上建议您关闭服务器的相邻缓存行预取，因为它们往往比桌面用户计算机生成更多随机内存引用。 在服务器上不使用相邻缓存行的概率较高，因此获取实际上不会使用的数据最终会污染缓存（填充不需要的数据），并且性能会受到影响。 有关解决此类问题的更多信息，请参阅Supercomputing 2009中的这篇论文， 了解如何使用机器学习来调整大型数据中心的预取程序 。 谷歌的一些人正在写论文; 表现是他们非常关注的事情。
简单的启发式方法不会帮助您使用更复杂的算法，您可能必须开始考虑L1，L2等缓存的大小。 例如，图像处理通常要求您对2D图像的子部分执行某些操作，但是您遍历图像的顺序可能会影响它在缓存中保留在缓存中的有效部分。 如果您对此类事物感兴趣，请查看Z顺序遍历和循环平铺 。 这是将图像数据的2D位置映射到内存的1D位置以提高性能的非常基本的示例。 这也是编译器无法始终以最佳方式重构代码的区域，但手动重构C代码可以大大提高缓存性能。
我希望这能让您了解迭代顺序如何影响内存性能。 它确实取决于特定的架构，但这些想法很普遍。 如果你能在Intel上理解它，你应该能够理解对AMD和Power的预取，并且你真的不需要知道汇编来构建你的代码以利用内存。 你只需要了解一点计算机架构。
我不知道。 但我确实知道如何写一个快速的基准而不保证科学的有效性（实际上，有一个相当严格的无效保证）。 它有趣的结果：
#include #include int main(void) { int i; int s; clock_t start_time, end_time; int centiseconds; start_time = clock(); s = 1; for (i = 0; i < 1000000000; i++) { s = s + i; } end_time = clock(); centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC; printf("Answer is %d; Forward took %ld centiseconds\n", s, centiseconds); start_time = clock(); s = 1; for (i = 999999999; i >= 0; i--) { s = s + i; } end_time = clock(); centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC; printf("Answer is %d; Backward took %ld centiseconds\n", s, centiseconds); return 0; }
在Cygwin上使用gcc 3.4.4编译-O9，在32位Windows XP中运行“AMD Athlon（tm）64处理器3500+”（2211 MHz）：
Answer is -1243309311; Forward took 93 centiseconds Answer is -1243309311; Backward took 92 centiseconds
（答案在几次重复中以1的方式变化。）
使用gcc 4.4.1在32位Ubuntu Linux上运行“Intel（R）Atom（TM）CPU N270 @ 1.60GHz”（800 MHz，可能只有一个核心，在程序中）编译-I9。
Answer is -1243309311; Forward took 196 centiseconds Answer is -1243309311; Backward took 228 centiseconds
（答案在几次重复中以1的方式变化。）
查看代码，正向循环转换为：
; Gcc 3.4.4 on Cygwin for Athlon ; Gcc 4.4.1 on Ubuntu for Atom L5: .L2: addl %eax, %ebx addl %eax, %ebx incl %eax addl $1, %eax cmpl $999999999, %eax cmpl $1000000000, %eax jle L5 jne .L2
落后于：
L9: .L3: addl %eax, %ebx addl %eax, %ebx decl %eax subl $1, $eax jns L9 cmpl $-1, %eax jne .L3
这表明GCC的行为在这两个版本之间发生了变化，如果不是其他的话！
将较旧的GCC循环粘贴到较新的GCC的asm文件中会得到以下结果：
Answer is -1243309311; Forward took 194 centiseconds Answer is -1243309311; Backward took 133 centiseconds
总结：在> 5岁的Athlon上，GCC 3.4.4产生的循环速度相同。 在新的（<1年？）Atom上，后向循环明显更快。 海湾合作委员会第4.4.1段针对这一特定情况略有回归，至少就我个人而言，我个人并不感到困扰。 （我必须确保在循环之后使用s ，否则编译器会完全忽略计算。）
[1]我永远不记得系统信息的命令……
是。 但有一点需要注意。 向后循环的想法更快，从未应用于所有旧CPU。 这是一个x86的东西（如8086到486，可能是Pentium，虽然我没有想到更多）。
该优化从未应用于我所知道的任何其他CPU架构。
这就是原因。
8086有一个专门针对循环计数器进行优化的寄存器。 您将循环计数放在CX中，然后有几个指令递减CX，然后设置条件代码，如果它变为零。 事实上，在其他指令（REP前缀）之前有一个指令前缀，它基本上会迭代另一条指令，直到CX达到0。
回到我们计算指令和指令的时候，使用cx知道固定循环计数，因为你的循环计数器是可行的方法，并且cx被优化用于倒计时。
但那是很久以前的事了。 自Pentium以来，这些复杂的指令总体上比使用更多，更简单的指令更慢。 （RISC宝贝！）这些天我们尝试做的关键是尝试在加载寄存器和使用它之间花些时间，因为只要你不尝试使用相同的寄存器，管道实际上每个周期可以做多件事一次不止一件事。
现在杀死性能的东西不是比较，它是分支，然后只有当分支预测预测错误时。
在观察到向后和向前迭代数组时性能显着下降后，我偶然发现了这个问题。 我担心它会成为预取者，但上面的答案使我确信情况并非如此。 然后我进一步调查并发现看起来GCC（4.8.4）无法在后向循环中利用SIMD操作的全部function。
实际上，使用-S -O3 -mavx编译以下代码（从这里开始 ）：
for (i = 0; i < N; ++i) r[i] = (a[i] + b[i]) * c[i];
导致基本上：
.L10: addl $1, %edx vmovupd (%rdi,%rax), %xmm1 vinsertf128 $0x1, 16(%rdi,%rax), %ymm1, %ymm1 vmovupd (%rsi,%rax), %xmm0 vinsertf128 $0x1, 16(%rsi,%rax), %ymm0, %ymm0 vaddpd (%r9,%rax), %ymm1, %ymm1 vmulpd %ymm0, %ymm1, %ymm0 vmovupd %xmm0, (%rcx,%rax) vextractf128 $0x1, %ymm0, 16(%rcx,%rax) addq $32, %rax cmpl %r8d, %edx jb .L10
即使用AVX扩展并行执行4次双重操作的汇编代码（例如vaddpd，vmulpd）。
相反，以下代码使用相同的参数编译：
for (i = 0; i < N; ++i) r[N-1-i] = (a[N-1-i] + b[N-1-i]) * c[N-1-i];
生产：
.L5: vmovsd a+79992(%rax), %xmm0 subq $8, %rax vaddsd b+80000(%rax), %xmm0, %xmm0 vmulsd c+80000(%rax), %xmm0, %xmm0 vmovsd %xmm0, r+80000(%rax) cmpq $-80000, %rax jne .L5
当时只执行一次双重操作（vaddsd，vmulsd）。
这个事实本身可能是在向后迭代与向前迭代时性能之间的因素4。
使用-ftree-vectorizer-verbose=2 ，看起来问题是向后存储：“存储的负步骤”。 实际上，如果a ， b和c被向后读，但是r被正向写入，则代码再次被矢量化。
不，我们不能说CPU实现已经改变，以使前向循环更快。 这与CPU本身没什么关系。
它与你没有指定你正在谈论的CPU，以及哪个编译器这一事实有关。
你不能问一个关于C标签的CPU问题的一揽子问题，并希望得到一个明智的答案，因为C标准中的任何内容都没有规定CPU在各种操作中应该有多快。
如果你想重新定义你的问题以定位特定的CPU和机器语言（因为你从C编译器获得的机器语言完全取决于编译器），你可能会得到更好的答案。
在任何一种情况下，都无所谓。 您应该依赖于编写编译器的人比您更了解如何从各种CPU中获得最后一英寸性能的事实。
你应该迭代的方向一直由你必须做的事情决定。 例如，如果必须按升序处理数组元素，则使用：
for (i = 0; i < 1000; i++) { process (a[i]); }
而不是：
for (i = 999; i >= 0; i--) { process (a[999-i]); }
只是因为你在倒退时可能获得的任何好处都超过了对i的额外计算所淹没。 很可能是一个裸体循环（没有在体内完成的工作）在一个方向上可能比另一个方向更快但是，如果你有这样一个裸露的循环，它无论如何都没有做任何真正的工作。
顺便说一下，无论如何，上述两个循环都可能归结为相同的机器代码。 我已经看到了GCC优化器发布的一些代码，这让我头疼。 在我看来，编译器编写者在疯狂的优化级别上只是一个物种。
我的建议：始终先为可读性编程，然后针对您遇到的任何特定性能问题（“让它先工作， 然后让它快速工作”）。
在优化循环时，我宁愿研究循环展开（因为它减少了比较次数与退出值，并且可能针对并行处理（mmx）进行优化，具体取决于循环内部的内容）。
它可能不会在速度方面产生差异，但我经常写道：
for (i = n; --i >= 0; ) blah blah
我认为这一次产生了更清洁的assembly。
当然，在回答这类问题时，我冒着肯定这很重要的风险。 这是一个微观优化的问题，它与过早的优化密切相关，每个人都说你不应该这样做 ，但是SO仍然充斥着它。