当尝试了解程序集(启用编译器优化)时,我看到此行为:
这样一个非常基本的循环
outside_loop;
while (condition) {
statements;
}
通常被编译成(伪代码)
; outside_loop
jmp loop_condition ; unconditional
loop_start:
loop_statements
loop_condition:
condition_check
jmp_if_true loop_start
; outside_loop
但是,如果未打开优化,它将编译为通常可以理解的代码:
loop_condition:
condition_check
jmp_if_false loop_end
loop_statements
jmp loop_condition ; unconditional
loop_end:
根据我的理解,编译后的代码与此类似:
goto condition;
do {
statements;
condition:
}
while (condition_check);
我看不到性能的大幅提升或代码可读性的大幅提升,为什么通常会如此?此循环样式是否有名称,例如“跟踪条件检查”?
最佳答案
相关:asm循环基础知识:While, Do While, For loops in Assembly Language (emu8086)
循环内更少的指令/ uops =更好的。在循环之外构造代码以实现此目标通常是一个好主意。
有时这需要“循环旋转”(剥离第一次迭代的一部分,因此实际的循环主体在底部具有条件分支)。因此,您进行了一些第一次迭代,可能会完全跳过循环,然后陷入循环。有时,在循环之后您还需要一些代码来完成上一次迭代。
如果最后一次迭代是特殊情况,例如循环循环有时会特别有用。您需要跳过的商店。这使您可以在执行时实现while(1) {... ; if(x)break; ...; }
循环,或在底部放置多条件循环的条件之一。
其中一些优化与软件流水线相关或启用了软件流水线,例如为下一次迭代加载一些东西。 (x86上的OoO exec如今使软件流水线化不是很重要,但是它对于像许多ARM这样的有序内核仍然很有用。并且使用多个累加器进行展开对于将循环携带的FP延迟隐藏在像点产品那样的简化循环中仍然非常有值(value)。或数组的总和。)
do{}while()
是所有架构上的asm循环的规范/惯用结构,请习惯它。 IDK(如果有名称);我会说这样的循环具有“while结构”。如果需要名称,可以将while()
结构称为“糟糕的未优化代码”或“由新手编写”。 :P底部的循环分支是通用的,甚至不值得作为Loop Optimization提及。你总是那样做。
这种模式的使用如此广泛,以至于对分支预测器缓存中没有条目的分支使用静态分支预测的CPU,可以预测未采用未知的前向条件分支,可以预测为采用未知的后向分支(因为它们很可能是循环分支) )。请参阅Matt Godbolt博客上的Static branch prediction on newer Intel processors,以及他的微结构PDF开头的Agner Fog的分支预测章节。
最终,所有问题都使用了x86示例,但是其中的大部分都适用于所有体系结构。如果其他超标量/无序实现(例如某些ARM或POWER)也具有有限的分支指令吞吐量(无论是否采用),我不会感到惊讶。但是,当您仅有的是底部的条件分支而没有无条件分支时,循环内的指令几乎是通用的。
如果循环可能需要运行零次,则编译器通常将测试分支放在循环外部以跳过该循环,而不是跳转到底部的循环条件。 (即,如果编译器无法在第一次迭代中证明循环条件始终为真)。
顺便说一句,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中的循环一样。
当您知道不允许调用者传递do{}while()
或其他任何保证循环至少运行一次的方法时,可以用C编写size=0
循环,从而帮助编译器制作更紧凑的asm(循环外的指令更少)。
(对于有符号循环边界,实际上为0或为负。有符号与无符号循环计数器是一个棘手的优化问题,尤其是当您选择比指针窄的类型时;请检查编译器的asm输出,以确保它没有对窄循环进行符号扩展。如果您将其用作数组索引,则可以在循环中非常方便地进行计数器操作,但是请注意,有符号实际上是有帮助的,因为编译器可以假定i++ <= bound
最终将变为false,而because signed overflow is UB但无符号则不会,因此,对于无符号,while(i++ <= bound)
是无限的如果没有使用signed和unsigned,我没有明确的建议。 bound = UINT_MAX
通常是循环遍历数组的一个不错的选择,但是,如果您想避免循环开销中的x86-64 REX前缀(以节省代码量),但可以说服编译器不要浪费任何零或符号的指令-扩展,可能会很棘手。
I can't see a huge performance boost
这是一个示例,该优化将使Haswell之前的Intel CPU速度提高2倍,因为P6和SnB / IvB只能在端口5上运行分支,包括未采用的条件分支。
此静态性能分析所需的背景知识:Agner Fog's microarch guide(请参阅Sandybridge部分)。还请阅读他的《优化装配》指南,这非常好。 (但是,有时在某些地方已经过时了。)另请参见x86标签Wiki中的其他x86性能链接。另请参阅Can x86's MOV really be "free"? Why can't I reproduce this at all?,以获取一些使用perf计数器进行的实验支持的静态分析,以及有关融合域和非融合域uops的一些说明。
您还可以使用Intel的IACA software (Intel Architecture Code Analyzer)对这些循环进行静态分析。
; sum(int []) using SSE2 PADDD (dword elements)
; edi = pointer, esi = end_pointer.
; scalar cleanup / unaligned handling / horizontal sum of XMM0 not shown.
; NASM syntax
ALIGN 16 ; not required for max performance for tiny loops on most CPUs
.looptop: ; while (edi<end_pointer) {
cmp edi, esi ; 32-bit code so this can macro-fuse on Core2
jae .done ; 1 uop, port5 only (macro-fused with cmp)
paddd xmm0, [edi] ; 1 micro-fused uop, p1/p5 + a load port
add edi, 16 ; 1 uop, p015
jmp .looptop ; 1 uop, p5 only
; Sandybridge/Ivybridge ports each uop can use
.done: ; }
这是总共4个融合域uops(with macro-fusion of the
size_t
),因此它可以从前端发出到无序内核,每个时钟一次迭代。但是在未融合的域中,有4个ALU主机,而Intel Haswell之前的版本只有3个ALU端口。更重要的是,端口5的压力是瓶颈:该循环只能在每2个周期执行一次迭代,因为cmp / jae和jmp都需要在port5上运行。其他窃取端口5的操作可能会降低实际吞吐量,低于此水平。
惯用地为asm 编写循环,我们得到:
ALIGN 16
.looptop: ; do {
paddd xmm0, [edi] ; 1 micro-fused uop, p1/p5 + a load port
add edi, 16 ; 1 uop, p015
cmp edi, esi ; 1 uop, port5 only (macro-fused with cmp)
jb .looptop ; } while(edi < end_pointer);
立即注意,与其他所有内容无关,这是循环中少一条指令。从简单的非流水线8086到classic RISC(如早期的MIPS),此循环结构至少要好一些,特别是对于长时间运行的循环(假设它们不限制内存带宽)。
Core2和更高版本应该在每个时钟一次迭代中运行此命令,如果内存不是瓶颈(例如,假设L1D命中,或者实际上至少为L2,则为
cmp/jae
结构循环的两倍);这仅是SSE2 16字节每个时钟)。这仅是3个融合域的uops,因此自Core2起,在任何事物上发出的时钟频率均好于每个时钟发出的时钟,如果发出问题的组始终以采用分支结束,则每个时钟发出的频率将优于一个时钟。
但是重要的是,大大降低了port5的压力:只有
while(){}
才需要它。其他uops可能会在某些时间安排到port5并从循环分支吞吐量中窃取周期,但这将是几个百分点,而不是2的倍数。请参见How are x86 uops scheduled, exactly?。通常,分支分支吞吐量为每2个周期1个的大多数CPU仍可以每个时钟1个执行微小的循环。但是,也有一些异常(exception)。 (我忘记了哪个CPU不能以每个时钟1个的频率运行紧密循环;也许是Bulldozer系列产品?还是像VIA Nano这样的低功耗CPU。)Sandybridge和Core2绝对可以每个时钟以1个时钟运行紧密循环。他们甚至有循环缓冲区。 Core2在指令长度解码之后但在常规解码之前具有循环缓冲区。 Nehalem和后来的回收队列在提供问题/重命名阶段的队列中。 (除了在Skylake上进行微代码更新外,由于部分寄存器合并错误,Intel必须禁用循环缓冲区。)
但是,
cmp/jb
上有一个循环承载的依赖项链:英特尔CPU具有1周期延迟xmm0
,因此我们也正面临这一瓶颈。 paddd
也是1个周期的延迟。在Bulldozer系列上,即使整数 vector 运算也有2c的延迟,因此每次迭代2c时都会使循环成为瓶颈。 (AMD从K8开始,AMD从SnB开始,每个时钟可以运行两个负载,因此无论如何我们都需要展开以实现最大吞吐量。)对于浮点数,您肯定要使用多个累加器进行展开。 Why does mulss take only 3 cycles on Haswell, different from Agner's instruction tables? (Unrolling FP loops with multiple accumulators)。如果我使用了索引寻址模式(例如
add esi, 16
),则可以在循环条件下使用paddd xmm0, [edi + eax]
/ sub eax, 16
。 SUB / JNC可以在Sandybridge系列上进行宏熔断,但是索引加载为would un-laminate on SnB/IvB(但在Haswell及更高版本上保持融合,除非您使用AVX形式)。 ; index relative to the end of the array, with an index counting up towards zero
add rdi, rsi ; edi = end_pointer
xor eax, eax
sub eax, esi ; eax = -length, so [rdi+rax] = first element
.looptop: ; do {
paddd xmm0, [rdi + rax]
add eax, 16
jl .looptop ; } while(idx+=16 < 0); // or JNC still works
(通常最好展开一些操作以隐藏指针增量的开销,而不是使用索引寻址模式,特别是对于商店而言,部分原因是因为索引商店无法在Haswell +上使用port7商店AGU。)
在Core2 / Nehalem上,
jnc
不要使用宏融合,因此即使在64位模式下,这也是3个融合域uops,而不依赖于宏融合。与AMD K8 / K10 / Bulldozer-family / Ryzen相同:循环条件不融合,但带有内存操作数的PADDD为1 m-op / uop。在SnB上,
add/jl
从负载中取消分层,但是添加/ jl宏 fuse ,因此又添加了3个融合域uops。 (但是在未融合的域中,只有2个ALU uo + 1个负载,因此可能更少的资源冲突减少了循环的吞吐量。)在HSW及更高版本上,这是2个融合域uops,因为索引负载可以与PADDD和
paddd
宏 fuse 保持微融合。 (预测分支在端口6上运行,因此永远不会发生资源冲突。)当然,由于即使是很小的循环,分支占用的吞吐量也会受到限制,因此每个时钟循环最多只能运行1次迭代。如果您还需要在循环中执行其他操作,则此索引技巧可能很有用。
但是所有这些循环都没有展开
是的,这会夸大循环开销的影响。但是默认情况下,即使在
add/jl
上,gcc也不会展开(除非它决定完全展开)。它仅在配置文件引导的优化下展开,以告知哪些循环很热。 (-O3
)。您可以启用-fprofile-use
,但是我只建议针对您知道其中有一个需要它的热循环的编译单元在每个文件的基础上这样做。或者,甚至在每种功能的基础上加上-funroll-all-loops
,如果有这样的优化选项。因此,这与编译器生成的代码高度相关。 (但是
__attribute__
确实默认将微小循环展开4或将微小循环展开2,并且非常重要的是,使用多个累加器来隐藏延迟。)迭代次数极少的好处:
考虑一下循环主体运行一次或两次时会发生什么:除了
clang
以外,还有更多的跳跃 Action 。do{}while
,执行是一条直线,底部没有任何分支,一个没有分支。太好了do{}while
,这是两个未使用的分支。那还是很好。 (对于前端而言,未摄取要比正确预测两者时要便宜一些)。 if() { do{}while; }
,它是一个采用了无条件分支,一个采用了循环条件,然后不采用该循环分支。这有点笨拙,但是现代分支预测器非常好... jmp; do{}while()
结构,这是一个未采用的循环导出,一个在底部采用一个while(){}
,然后在顶部是一个采用循环退出的分支。 随着迭代次数的增加,每个循环结构都会执行一个分支。
jmp
在每次迭代中还会做一个未采用的分支,因此它很快变得更糟。后两个循环结构在较小的行程数时有更多的跳跃。
跳转到底部对于非微小的循环也有一个缺点,即如果一段时间没有运行,则循环的底部在L1I缓存中可能很冷。代码获取/预取擅长将代码直线地带到前端,但是如果预测没有足够早地预测分支,则可能会错过跳到底部的代码。同样,并行解码可能已经(或可能已经)对循环顶部的某些内容进行了解码,同时将
while(){}
解码至底部。有条件地跳过
jmp
循环可以避免所有这些情况:只有在根本不应该运行要跳过的代码的情况下,您才可以跳入尚未运行的代码。由于许多代码实际上从未在循环中进行0次跳闸,因此通常可以很好地预测。 (即可能是do{}while
,编译器只是未能证明这一点。)跳到最底端也意味着核心要在前端追逐两个分支后才能开始在真正的循环体上工作。
在某些情况下,复杂的循环条件最容易以这种方式编写,并且对性能的影响很小,但编译器通常会避免使用它。
具有多个退出条件的循环:
考虑一个
do{}while
循环或memchr
循环:它们必须停在缓冲区的末尾(基于计数)或隐式长度字符串的末尾(0字节)。但是,如果他们在结束之前找到匹配项,还必须将strchr
跳出循环。所以您经常会看到类似的结构
do {
if () break;
blah blah;
} while(condition);
或者只是底部附近的两个条件。理想情况下,您可以使用同一条实际指令(例如,使用
break
/ 5 < x && x < 25
/ sub eax, 5
的cmp eax, 20
,用于范围检查的无符号比较技巧或将其与ja .outside_range
结合到check for alphabetic characters of either case in 4 instructions)来测试多个逻辑条件,但有时您不能,仅需要使用OR
样式循环退出分支以及普通的向后采用分支。进一步阅读:
主题外排序:
关于performance - 为什么循环总是编译成 “do…while”样式(尾跳)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47783926/