Jer*_*ner 18 c optimization for-loop
在我订阅的邮件列表中,两位相当知识渊博的(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实现,这样前向循环迭代现在比后向迭代有优势？如果是这样,那有什么解释呢？即改变了什么？
(是的,我知道,过早的优化是所有邪恶的根源,在考虑微优化之前检查我的算法等等...大多数我只是好奇)
Tod*_*lin 28
你真的在询问预取,而不是关于循环控制逻辑.
通常,循环性能不会由控制逻辑决定(即增量/减量和每次检查的条件).除非是非常紧凑的循环,否则执行这些操作所花费的时间是无关紧要的.如果您对此感兴趣,请查看John Knoeller关于8086计数器寄存器详细信息的答案,以及为什么在过去倒数更有效的情况下可能会如此.正如约翰所说,分支预测(以及推测)可以在这里发挥作用,就像指令预取一样.
迭代顺序可以当它改变在你的循环触动记忆的顺序显著影响性能.请求内存地址的顺序可能会影响缓存中的内容,以及当不再有空间获取新缓存行时从缓存中逐出的内容.不得不经常访问内存比比较,增量或减量要昂贵得多.在现代CPU上,从处理器到内存可能需要数千个周期,而处理器可能必须在部分或全部时间闲置.
你可能熟悉缓存,所以我不会在这里详细介绍所有这些细节.您可能不知道的是,现代处理器使用大量预取器来尝试预测接下来在不同级别的内存层次结构中需要哪些数据.一旦他们预测到,他们会尝试从内存或较低级别的缓存中提取数据,以便在您处理它时获得所需的内容.根据他们接下来所需要的程度,您的表现在使用时可能会有所提高,也可能不会提高.
请查看英特尔针对硬件预取程序进行优化的指南.列出了四个prefetchers; 两个用于NetBurst芯片:
和两个核心:
如果你正在向前遍历一个数组,那么你将生成一堆顺序的,通常是连续的内存引用.ACL预取程序对于正向循环(因为你最终会使用那些后续的高速缓存行)要比向后循环好得多,但是如果预取程序可以检测到这种情况,你可以做好向后的内存引用(就像硬件一样)预取).Core上的硬件预取程序可以检测步幅,这有助于更复杂的数组遍历.
在某些情况下,这些简单的启发式方法可能会让您陷入困境.例如,英特尔实际上建议您关闭服务器的相邻缓存行预取,因为它们往往比桌面用户计算机产生更多的随机内存引用.在服务器上不使用相邻高速缓存行的概率较高,因此获取实际上不会使用的数据最终会污染您的高速缓存(填充不需要的数据),并且性能会受到影响.有关解决此类问题的更多信息,请参阅Supercomputing 2009中的这篇论文,了解如何使用机器学习来调整大型数据中心的预取程序.谷歌的一些人正在写论文; 表现是他们非常关心的事情.
简单的启发式方法不会帮助您使用更复杂的算法,您可能必须开始考虑L1,L2等缓存的大小.例如,图像处理通常要求您对2D图像的子部分执行某些操作,但是遍历图像的顺序可能会影响它在缓存中保留在缓存中的有效部分.如果您对此类事物感兴趣,请查看Z顺序遍历和循环平铺.这是将图像数据的2D局部映射到内存的1D位置以提高性能的非常基本的示例.这也是编译器无法始终以最佳方式重构代码的区域,但手动重构C代码可以极大地提高缓存性能.
我希望这能让您了解迭代顺序如何影响内存性能.它确实取决于特定的架构,但这些想法很普遍.如果你能在英特尔上理解它,你应该能够理解AMD和Power的预取,而你真的不需要知道汇编来构建代码以利用内存.你只需要了解一点计算机架构.
Edm*_*und 12
我不知道.但我确实知道如何编写一个快速的基准而不保证科学的有效性(实际上,这是一个非常严格的无效保证).它有趣的结果:
#include <time.h>
#include <stdio.h>
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 操作的能力。
事实上，编译以下代码（从这里）-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 扩展并行执行四个双重操作的汇编代码（例如，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是向前写的，代码又被向量化了。