相关文章: 汇编循环基础: 汇编语言中的While、Do While、For循环 (emu8086)
术语: 维基百科称 "循环反转" 是将 while(x)
转换为 if(x) do{}while(x)
,将条件放在循环底部的名称。
循环内的指令/微操作越少,性能越好。因此,在循环外部结构化代码通常是个好主意。
有时需要进行“循环旋转”(将第一次迭代的部分剥离出来,使实际的循环体在底部具有条件分支)。因此,您可以执行第一次迭代的某些操作,甚至跳过整个循环,然后进入循环。有时候你还需要在循环后添加一些代码来完成最后一次迭代。
如果最后一次迭代是一个特殊情况(例如需要跳过的存储),那么有时循环旋转会更加有用。这样就可以将while(1) {... ; if(x)break; ...; }
循环实现为do-while,或者将多条件循环的其中一个条件放在底部。
其中一些优化与软件流水线相关或启用了软件流水线,例如为下一次迭代加载内容。(x86上的OoO执行使得SW流水线在今天不太重要,但对于像许多ARM这样的顺序核心仍然很有用。在像点积或数组求和这样的约简循环中,使用多个累加器展开仍然非常有价值。)
< p >
do{}while()
是所有架构上汇编循环的规范/惯用结构,请习惯它。 我不知道是否有一个名字; 我会说这样的循环具有“do while结构”。如果你想要名称,你可以称
while()
结构为“糟糕的未优化代码”或“由新手编写”。:P 在底部循环分支是普遍存在的,并且不值得作为
Loop Optimization提及。你总是这样做。
这种模式如此广泛使用,以至于在使用静态分支预测器缓存中没有条目的分支的CPU上,未知的向前条件分支被预测为未采取,未知的向后分支被预测为已采取(因为它们可能是循环分支)。请参见Matt Godbolt博客上的Static branch prediction on newer Intel processors和Agner Fog的分支预测章节,该章节位于他的microarch PDF的开头。
这个答案最终使用了x86的例子,但大部分内容都适用于所有架构。我不会感到惊讶如果其他超标量/乱序执行的实现(例如一些ARM或POWER)也有限制的分支指令吞吐量无论它们是否被采取。但是,在底部只有一个条件分支和没有无条件分支的情况下,循环内的指令数量减少几乎是普遍的。请保留HTML标签。
如果循环可能需要零次运行,编译器更倾向于在循环外部放置一个测试和分支来跳过它,而不是在底部跳转到循环条件。(即,如果编译器无法证明循环条件在第一次迭代中始终为真)。
顺便提一下,this paper 将将 while()
转换为 if(){ do{}while; }
称为“反转”,但循环反转通常指反转嵌套循环。(例如,如果源代码以错误的顺序遍历行主多维数组,则聪明的编译器可以将 for(i) for(j) a[j][i]++;
更改为 for(j) for(i) a[j][i]++;
如果它可以证明它是正确的。)但我想你可以将 if()
看作是零次或一次迭代循环。有趣的事实是,编译器开发人员教他们的编译器如何反转循环(以允许自动向量化)针对(非常)特定的情况,这就是 why SPECint2006's libquantum benchmark is "broken"。大多数编译器不能在一般情况下反转循环,只能反转与 SPECint2006 中的循环几乎完全相同的循环...
当你知道调用者不允许传递 `size=0` 或其他保证循环至少运行一次的条件时,在 C 中编写 `do{}while()` 循环可以帮助编译器使汇编更加紧凑(循环外的指令更少)。请保留 HTML 标签。
实际上,对于有符号循环边界,可以为0或负数。有符号和无符号循环计数器是一个棘手的优化问题,特别是如果您选择比指针更窄的类型;检查编译器的汇编输出以确保它不会在循环内部非常时间内将窄循环计数器进行符号扩展并将其用作数组索引。但请注意,有符号实际上可能是有帮助的,因为编译器可以假设
i++ <= bound最终会变为false,因为有符号溢出是未定义行为,但无符号不是。因此,对于无符号,如果
bound = UINT_MAX
,则
while(i++ <= bound)
是无限的。我没有关于何时使用有符号还是无符号的全面建议;
size_t
通常是循环遍历数组的好选择,但是如果您想避免在循环开销中使用x86-64 REX前缀(以节省代码大小),同时使编译器不浪费任何指令进行零扩展或符号扩展,则可能会比较棘手。
我看不到巨大的性能提升
以下是一个例子,该优化将在Haswell之前的Intel CPU上加速2倍,因为P6和SnB/IvB只能在端口5上运行分支,包括未采取条件分支。
进行此静态性能分析所需的背景知识:Agner Fog的微架构指南(阅读Sandybridge部分)。还要阅读他的优化汇编指南,它非常好。 (有时在某些地方过时。)请参见x86标签wiki中的其他x86性能链接。另请参见 x86的MOV真的可以“免费”吗?为什么我根本无法复制这个?,其中包含一些由perf计数器支持的静态分析,并解释了融合和未融合域uop。
您还可以使用英特尔的 IACA软件(英特尔架构代码分析器) 对这些循环进行静态分析。
ALIGN 16
.looptop:
cmp edi, esi
jae .done
paddd xmm0, [edi]
add edi, 16
jmp .looptop
.done:
这是4个融合域uops(
带有cmp/jae
的宏融合),因此它可以以每个时钟周期一次的速度从前端发出到乱序核心。但在未融合的域中,有4个ALU uops,而Intel pre-Haswell只有3个ALU端口。
更重要的是,port5压力是瓶颈:由于cmp/jae和jmp都需要在port5上运行,所以
此循环每2个周期只能执行一次。其他窃取port5的uops可能会将实际吞吐量降低到以下水平。
按照汇编语言的惯用方式编写循环,我们得到:
ALIGN 16
.looptop:
paddd xmm0, [edi]
add edi, 16
cmp edi, esi
jb .looptop
请立即注意,独立于其他任何事物,这是循环中少了一条指令。对于从简单的非流水线8086到
经典RISC(如早期MIPS)的所有内容,尤其是对于长时间运行的循环(假设它们不会在内存带宽上成为瓶颈),此循环结构至少略微更好。
Core2
和之后的处理器应该以每个时钟周期一次的速度运行这个循环,比使用
while(){}
结构的循环快两倍,如果内存不是瓶颈(即假定L1D命中,或者至少实际上是L2;这只有SSE2每个时钟周期16字节)。
这只有3个融合域uop,因此可以在Core2之后的任何处理器上以每个时钟周期更好地发出,或者如果发出组总是以一个taken分支结束,则每个时钟周期只能发出一个。
重要的是port5压力大大降低:只有cmp/jb
需要它。其他uop可能会被安排到port5,从循环分支吞吐量中窃取周期,但这只会少数几个百分点,而不是2倍。请参见How are x86 uops scheduled, exactly?。
大多数通常每2个周期具有taken-branch吞吐量的CPU仍然可以以每个时钟周期执行微小的循环。但也有一些例外。 (我忘记了哪些CPU不能以1个时钟周期运行紧密循环;也许是Bulldozer系列?或者只是一些低功率CPU,例如VIA Nano。) Sandybridge和Core2绝对可以以每个时钟周期运行紧密循环。它们甚至有循环缓冲区;Core2在指令长度解码之后但在常规解码之前有一个循环缓冲区。 Nehalem及更高版本将uop回收到馈送问题/重命名阶段的队列中。(除了Skylake的微代码更新;因为局部寄存器合并错误,Intel不得不禁用循环缓冲区。)
然而,在xmm0上有一条循环依赖链:Intel CPU具有1个周期的latency paddd,因此我们也面临着这个瓶颈。add esi, 16也是1个周期的延迟。在Bulldozer家族中,即使是整数向量操作也有2个周期的延迟,因此每次迭代都会以2c为瓶颈。 (自K8以来的AMD和自SnB以来的英特尔可以每个时钟运行两个负载,因此我们需要展开以获得最大吞吐量。)对于浮点数,您绝对希望使用多个累加器展开。 请参见
Why does mulss take only 3 cycles on Haswell, different from Agner's instruction tables? (Unrolling FP loops with multiple accumulators)。
如果我使用索引寻址模式,例如
paddd xmm0,[edi + eax]
,我可以在循环条件处使用
sub eax,16
/
jnc
。 SUB / JNC 可以在Sandy Bridge系列上进行宏融合,但索引加载
将在SnB / IvB上解压缩(但除非使用AVX形式,否则仍会在Haswell及更高版本上保持融合)。
add rdi, rsi
xor eax, eax
sub eax, esi
.looptop:
paddd xmm0, [rdi + rax]
add eax, 16
jl .looptop
通常最好展开一些循环以隐藏指针增量的开销,而不是使用索引寻址模式,特别是对于存储操作,部分原因是索引存储无法使用Haswell+上的port7存储AGU。在Core2/Nehalem上,add/jl不会宏合并,因此即使在64位模式下,这也是3个融合域uops,而不依赖于宏合并。AMD K8/K10/Bulldozer家族/Ryzen同样如此:没有循环条件的合并,但带有内存操作数的PADDD是1个m-op/uop。在SnB上,paddd从加载中解离,但add/jl宏合并,因此再次是3个融合域uops。(但在未融合域中,仅有2个ALU uops + 1个加载,因此可能减少资源冲突,从而降低循环的吞吐量。)在HSW及更高版本上,这是2个融合域uops,因为索引加载可以与PADDD保持微合并,而add/jl宏合并。(预测采取的分支在端口6上运行,因此永远不会出现资源冲突。)
当然,由于分支限制,即使是小型循环,循环每个时钟周期只能运行最多1次迭代。如果您在循环内部还有其他事情要做,这种索引技巧可能会有用。
但所有这些循环都没有展开
是的,这夸大了循环开销的影响。但是,即使在-O3
下,gcc默认情况下也不会展开循环(除非它决定完全展开)。它只有在使用基于配置文件的优化(-fprofile-use
)时才会展开以让它知道哪些循环是热点循环。您可以启用-funroll-all-loops
,但我只建议在编译单元中为已知需要它的热点循环的文件上执行此操作。或者甚至可以使用__attribute__
进行每个函数的基础优化选项,如果存在这样的选项。
因此,这对于编译器生成的代码非常相关。(但是,clang
默认情况下将微小的循环展开4次,或将小循环展开2次,并且非常重要的是,使用多个累加器来隐藏延迟。)
迭代次数极少的好处:
考虑当循环体运行一次或两次时会发生什么:任何与do{}while
不同的跳转都会导致更多的跳转。
对于do{}while
,执行是一个直线,没有跳转,底部有一个未跳转的分支。这非常好。
对于可能零次运行循环体的if() { do{}while; }
,它是两个未跳转的分支。这仍然非常好。(正确预测时,未跳转比跳转稍微便宜,对于前端来说)。
对于跳转到底部jmp; do{}while()
,它是一个被执行的无条件跳转,一个被执行的循环条件分支,然后循环分支未被执行。这有点笨拙,但现代分支预测器非常好...
对于while(){}
结构,这是一个未执行的循环退出,底部有一个被执行的jmp
,然后顶部有一个被执行的循环退出分支。
随着迭代次数的增加,每个循环结构都会有一个更多的taken分支。
while(){}
每次迭代还会有一个更多的not-taken分支,因此它很快就变得明显更差了。
后两种循环结构在小trip计数时跳来跳去的次数更多。
跳到循环底部对于非微小的循环来说也有一个劣势,即如果它已经运行了一段时间,则循环底部可能在L1I缓存中处于冷态。代码提取/预取在直线上将代码带到前端是很好的,但是如果预测没有足够早地预测分支,您可能会因跳到底部而出现代码丢失。此外,同时解码可能已经(或可能已经)在解码jmp到底部时解码了一些循环顶部的内容。
有条件地跳过do {} while循环可以避免所有这些问题:仅在您要跳过的代码根本不应该运行的情况下向前跳转到尚未运行的代码中。它通常预测得非常好,因为很多代码实际上从未通过循环进行0次行程。(即它可能是一个do {} while,但编译器没有成功证明它。)
跳到底部还意味着内核不能在前端追踪两个已接受的分支之后立即开始处理真正的循环体。
在循环条件复杂的情况下,编写这种方式最容易,并且性能影响很小,但编译器通常会避免使用它。
多个退出条件的循环:
考虑一个memchr
循环或一个strchr
循环:它们必须在缓冲区的末尾(根据计数)或隐式长度字符串的末尾(0字节)停止。但如果在结束之前找到匹配项,它们还必须从循环中break
出来。
因此,您经常会看到这样的结构:
do {
if () break;
blah blah;
} while(condition);
或者只有在底部附近有两个条件。理想情况下,您可以使用相同的实际指令测试多个逻辑条件(例如,5 < x && x < 25
使用sub eax,5
/ cmp eax,20
/ ja .outside_range
,无符号比较技巧进行范围检查,或将其与OR
结合起来以检查4条指令中任意大小写字母字符),但有时您不能,只需要使用if()break
样式的循环退出分支以及正常的向后跳转分支。
进一步阅读:
有点跑题:
loop_start:
也可以对齐而不执行jmp
后面的填充nops
。虽然这几乎不是关键卖点,在循环重复足够多次的情况下,1-2个nop
来对齐未经优化的代码不会对测量结果产生太大影响。 - Ped7g