TL;DR:第一个循环在Haswell CPU上运行速度快18%。为什么?循环来自使用ptr++
和++ptr
的gcc -O0
(未优化)循环,但问题是为什么生成的asm表现不同,而不是关于如何编写更好的C.
假设我们有这两个循环:
movl $0, -48(%ebp) //Loop counter set to 0
movl $_data, -12(%ebp) //Pointer to the data array
movl %eax, -96(%ebp)
movl %edx, -92(%ebp)
jmp L21
L22:
// ptr++
movl -12(%ebp), %eax //Get the current address
leal 4(%eax), %edx //Calculate the next address
movl %edx, -12(%ebp) //Store the new (next) address
// rest of the loop is the same as the other
movl -48(%ebp), %edx //Get the loop counter to edx
movl %edx, (%eax) //Move the loop counter value to the CURRENT address, note -12(%ebp) contains already the next one
addl $1, -48(%ebp) //Increase the counter
L21:
cmpl $999999, -48(%ebp)
jle L22
第二个:
movl %eax, -104(%ebp)
movl %edx, -100(%ebp)
movl $_data-4, -12(%ebp) //Address of the data - 1 element (4 byte)
movl $0, -48(%ebp) //Set the loop counter to 0
jmp L23
L24:
// ++ptr
addl $4, -12(%ebp) //Calculate the CURRENT address by adding one sizeof(int)==4 bytes
movl -12(%ebp), %eax //Store in eax the address
// rest of the loop is the same as the other
movl -48(%ebp), %edx //Store in edx the current loop counter
movl %edx, (%eax) //Move the loop counter value to the current stored address location
addl $1, -48(%ebp) //Increase the loop counter
L23:
cmpl $999999, -48(%ebp)
jle L24
这些循环做着完全相同的事情,但方式略有不同,请参阅评论了解详细信息。
此asm代码由以下两个C++循环生成:
//FIRST LOOP:
for(;index<size;index++){
*(ptr++) = index;
}
//SECOND LOOP:
ptr = data - 1;
for(index = 0;index<size;index++){
*(++ptr) = index;
}
现在,第一个循环比第二个循环快约18%,无论循环的执行顺序如何,具有ptr++
的循环都比具有++ptr
的循环快。
为了运行我的基准测试,我只收集了不同大小的这些循环的运行时间,并将它们嵌套在其他循环中执行,以频繁重复操作。
ASM分析
从ASM代码来看,第二个循环包含的指令较少,我们有3个movl和2个addl,而在第一个循环中,我们有4个movl-一个addl和一个leal,所以我们多了一个movl和一个leal-而不是addl
计算正确地址的LEA
操作比ADD
(+4)方法快得多,这正确吗?这就是性能差异的原因吗?
据我所知,一旦在引用内存之前计算出一个新地址,就必须经过一些时钟周期,因此addl$4,-12(%ebp)之后的第二个循环需要等待一段时间才能继续,而在第一个循环中,我们可以立即引用内存,同时LEAL将计算下一个地址(这里有某种更好的流水线性能)。
这里正在重新订购吗?我不确定我对这些循环的性能差异的解释,我能有你的意见吗?
首先,对-O0
编译器输出的性能分析通常不是很有趣或有用。
计算正确地址的LEAL操作比ADDL(+4)方法快得多,这正确吗?这就是性能差异的原因吗?
不,add
可以在任何x86 CPU上的每个ALU执行端口上运行。lea
通常具有简单寻址模式的低延迟,但没有那么好的吞吐量。在Atom上,它运行在与普通ALU指令不同的流水线阶段,因为它实际上名副其实,并在有序微体系结构上使用AGU。
请参阅x86标签wiki,了解是什么使不同微体系结构上的代码变慢或变快,特别是Agner Fog的微体系结构pdf和指令表。
add
之所以更糟糕,是因为它让gcc-O0
通过将其与内存目标一起使用,然后从中加载,来生成更糟糕的代码
使用-O0
编译甚至不会尝试使用最佳指令。例如,您将获得mov $0, %eax
,而不是优化代码中始终获得的xor %eax,%eax
。您不应该从未优化的编译器输出中推断出任何关于什么是好的。
-O0
代码总是充满瓶颈,通常是在加载/存储或存储转发时。不幸的是,IACA没有考虑存储转发延迟,所以它没有意识到这些循环实际上是的瓶颈
据我所知,一旦在引用内存之前计算出一个新地址,就必须经过一些时钟周期,因此加法器$4,-12(%ebp)之后的第二个循环需要等待一段时间才能继续,
是的,-12(%ebp)
的mov
加载在作为add
的读取-修改-写入的一部分的加载之后大约6个周期内不会准备好。
而在第一个循环中,我们可以立即引用内存
是
,同时LEAL将计算下一个地址
否。
您的分析很接近,但您忽略了一个事实,即下一次迭代仍然需要将我们存储的值加载到-12(%ebp)
中。因此,循环携带的依赖链是相同的长度,并且下一次迭代的lea
实际上不能比使用add
的循环更早开始
延迟问题可能不是环路吞吐量瓶颈:
需要考虑uop/执行端口吞吐量。在这种情况下,OP的测试表明它实际上是相关的。(或者资源冲突导致的延迟。)
当gcc-O0
实现ptr++
时,它将旧值保留在寄存器中,就像您所说的那样。因此,存储地址会提前知道,并且需要AGU的加载uop会减少一个。
假设Intel SnB系列CPU:
## ptr++: 1st loop
movl -12(%ebp), %eax //1 uop (load)
leal 4(%eax), %edx //1 uop (ALU only)
movl %edx, -12(%ebp) //1 store-address, 1 store-data
// no load from -12(%ebp) into %eax
... rest the same.
## ++ptr: 2nd loop
addl $4, -12(%ebp) // read-modify-write: 2 fused-domain uops. 4 unfused: 1 load + 1 store-address + 1 store-data
movl -12(%ebp), %eax // load: 1 uop. ~6 cycle latency for %eax to be ready
... rest the same
因此,第二个循环的指针增量部分还有一个负载uop。可能是AGU吞吐量(地址生成单元)上的代码瓶颈。IACA表示,arch=SNB就是这样,但HSW在存储数据吞吐量(而不是AGU)方面存在瓶颈。
然而,IACA表示,在不考虑存储转发延迟的情况下,第一个循环可以每3.5个周期运行一次迭代,而第二个循环则是每4个周期运行。这比addl $1, -48(%ebp)
循环计数器的6个循环循环携带的依赖性要快,这表明循环受到延迟的限制,低于最大AGU吞吐量。(资源冲突可能意味着它实际运行速度慢于每6c一次迭代,见下文)。
我们可以检验这个理论:
在lea
版本中添加一个额外的负载uop,离开关键路径,会占用更多的吞吐量,但不会成为循环延迟链的一部分。例如
movl -12(%ebp), %eax //Get the current address
leal 4(%eax), %edx //Calculate the next address
movl %edx, -12(%ebp) //Store the new (next) address
mov -12(%ebp), %edx
%edx
即将被mov
覆盖,因此不依赖于此加载的结果。(mov
的目的地是只读的,因此由于寄存器重命名,它打破了依赖链。)。
因此,此额外负载将使lea
循环达到与add
循环相同的uops数量和风格,但具有不同的延迟。如果额外的负载对速度没有影响,我们知道第一个循环在负载/存储吞吐量方面没有瓶颈。
更新:OP的测试证实,额外的未使用负载将lea
循环减慢到与add
循环大致相同的速度。
当我们没有遇到执行端口吞吐量瓶颈时,为什么额外的uop很重要
uop按最早的第一顺序调度(在已准备好操作数的uop中),而不是按关键路径的第一顺序。本可以在以后的备用循环中完成的额外uop实际上会延迟关键路径上的uop(例如,循环的一部分携带依赖项)。这被称为资源冲突,会增加关键路径的延迟。
即,不是等待关键路径延迟使加载端口无所事事的循环,而是在其加载地址准备就绪的最旧加载时运行未使用的加载。这将延迟其他负载。
类似地,在add
循环中,额外负载是关键路径的一部分,额外负载会导致更多的资源冲突,从而延迟关键路径上的操作。
其他猜测:
因此,也许更快地准备好存储地址就是这样做的,所以内存操作可以更好地进行流水线操作。(例如,当接近页面边界时,TLB漏页遍历可能会更快开始。即使是正常的硬件预取也不会跨越页面边界,即使它们在TLB中很热。循环接触4MiB的内存,这就足够让这种事情发生了。L3延迟足够高,可能会产生管道气泡。或者,如果你的L3很小,那么主内存肯定是。
或者,额外的延迟只会让无序执行更难做好工作。