我偶然发现了这个very nice infographic,它给出了用于某些操作的CPU周期的粗略估计。在学习时,我注意到一个条目“如果的右分支”,我假设它是如果满足条件将采用的分支“如果”(EDIT:正如在注解中指出的那样,“Right”实际上意味着“正确预测的分支”)。这让我怀疑if分支与else分支相比是否有任何(即使是如此微小的)速度差异。
例如,比较以下非常精简的代码:
演示
#include <cstdio>
volatile int a = 2;
int main()
{
if (a > 5) {
printf("a > 5!");
a = 2;
} else {
printf("a <= 5!");
a = 3;
}
}
它在x86 64位中生成此程序集:
.LC0:
.string "a > 5!"
.LC1:
.string "a <= 5!"
main:
push rcx
mov eax, DWORD PTR a[rip]
cmp eax, 5
jle .L2
mov edi, OFFSET FLAT:.LC0
xor eax, eax
call printf
mov DWORD PTR a[rip], 2
jmp .L3
.L2:
mov edi, OFFSET FLAT:.LC1
xor eax, eax
call printf
mov DWORD PTR a[rip], 3
.L3:
xor eax, eax
pop rdx
ret
a:
.long 2
正如你所看到的,右边的分支调用printf来获取“a〉5”,它的位置离cmp -指令更近。看看数据缓存,可能会出现这样的情况:调用printf的指令已经被加载到缓存行中,而else分支必须首先从L2或L3缓存中获取。这会不会(理论上)在分支预测模式建立之前导致“右”分支的速度略微加快?
3条答案
按热度按时间cngwdvgl1#
简单地说,主流处理器上没有,但一些旧的/嵌入式处理器上有。
现代主流处理器非常擅长预测条件(假设它们不是第一次执行,或者测试可以提前完成)。当分支被正确预测时,几乎没有成本(除了使用在某些特定端口上执行的分支单元之外)。处理器可以推测性地获取并执行预测的条件块的指令。当分支未被正确预测时,处理器必须执行一种相当昂贵的回滚操作(通常为5-15个周期)。
一些嵌入式处理器和旧的处理器使用静态预测算法。例如,它们可以假设分支永远不会被执行。在这样的处理器上,执行
if
块通常比else
块快,前提是编译器不对块进行重新排序(在启用优化时,这种情况非常频繁)。* 内置提示 * 可以由开发人员提供,以帮助编译器生成代码,使处理器使用静态分区更有效地执行代码。* 档案导引优化 * 可用于自动查找通常为真/假的条件,并相应地对分支重新排序以提高性能。主流(服务器、台式机和高端移动的)处理器主要使用动态预测算法。例如,它们可以跟踪和记忆何时执行分支,以便了解将来执行分支的概率。处理器通常只跟踪有限的一组条件分支。因此,当代码中有太多(叠瓦状)条件分支指令,静态分区算法可用作回退方法。
值得一提的是,在某些情况下,预测信息可以被重置/刷新,比如进程被抢占时(如@HenriqueBucher所指出的)。这意味着当有许多上下文切换时,预测的有效性会大大降低。请注意,推测可以部分地由some specific instruction set控制,以缓解Spectre等漏洞。
由于处理器需要获取指令,而这些指令可能不在指令高速缓存中,因此跳转到远距离的未预测位置的开销可能会很大。在您的情况下,这在主流x86 - 64处理器上当然没有关系,因为最新的x86-64处理器预计会非常快地将程序的所有指令加载该高速缓存中。例如,Skylake处理器每周期可以从指令缓存中取16字节,而Zen 2处理器每周期可以取32字节。2两者都可以将64字节的缓存线加载到指令缓存中。
关于最新英特尔处理器的分支预测算法,没有太多公开信息。AMD Zen 2+处理器的分支预测算法有很好的记录:它使用一个高效的TAGE predictor和一个Perceptron来根据过去的统计数据预测一个条件的结果。你可以找到关于它的行为here的详细信息。
7vhp5slm2#
不,
if
和else
分支之间没有真实的的区别,这不是你链接的图形中“右”分支的意思。“右”分支意味着CPU的分支预测在比较之前正确地猜测了哪个分支将被执行。现代的CPU是流水线式的。它们在处理完当前指令之前就开始处理下一条指令。这可以显著提高性能,因为这意味着CPU可以保留所有不同的子组件(指令解码器、ALU的不同部分、存储器控制器等)一直忙碌,而不是在CPU的另一个组件工作时让它们空闲,即,它可以执行加法、从存储器取出操作数,和解码指令。
这种流水线操作依赖于知道下一条指令将被执行,而条件分支指令会对流水线操作造成影响。在你的例子中,CPU在
cmp
指令执行完之前,并不知道jle .L2
之后的下一条指令是mov edi, OFFSET FLAT:.LC0
还是mov edi, OFFSET FLAT:.LC1
,所以它会猜测。它开始在其中一条分支上工作,当cmp
最后完成时,它会检查它是否猜对了。如果猜对了,很好,它在后面的指令上所做的部分工作是有效的,它会继续正常运行。如果猜错了,它在jle
之后的指令上所做的所有工作都必须扔掉,它会开始在另一个分支上工作。这需要一些时间。偶尔的错误猜测不会产生明显的性能差异,但如果经常猜测错误,则会开始累积并产生很大的差异。另请参阅StackOverflow上评分最高的答案。
注意,在一些较老的或嵌入式CPU上,分支预测算法本质上只是“总是猜测第一个”,所以在这样的CPU上
else
路径 * 会 * 比较慢,因为默认情况下分支预测永远不会猜到它。的[[likely]]
属性对于告诉编译器哪个分支更可能是有用的,这样编译器将生成汇编代码以使更可能的路径成为“第一个”,即使它是else
。hmmo2u0o3#
“if的右分支,”我假设它是如果条件满足,“if”要执行的分支。
不,它是关于正确的分支预测,与表中“if的错误分支(分支误预测)”项的比较。这是一个问题,无论C源代码中是否存在
else
。一个条件分支需要由前端来预测才不会停止,但是猜测错误意味着它必须回退并丢弃推测错误的指令。无论是否存在
else
部分,这都适用。请参阅Mysticial的著名答案 * 为什么处理排序数组比处理未排序数组快?*else
只需要在一个指令块中有一个额外的无条件分支,就可以不运行另一个指令块。(在您的例子中,就是jmp .L3
)。(例如在函数底部的X1 M4 N1 X之后),但是另一条路径具有占用的X1 M5 N1 X和占用的X1 M6 N1 X,返回到在IF/ELSE之后重新加入另一条路径。正如你所看到的,右边的分支调用printf来获取“a〉5”,它的位置离cmp -指令更近。看看数据缓存,可能会出现这样的情况:调用printf的指令已经被加载到缓存行中,而else分支必须首先从L2或L3缓存中获取。这会不会(理论上)在分支预测模式建立之前导致“右”分支的速度略微加快?
是的,指令缓存局部性的分支布局与分支 * 预测 * 几乎或完全分离。
正如您所说,指令缓存局部性是一个问题,因此,如果编译器知道(或者您使用
[[likely]]
或[[unlikely]]
告诉它)if/else的一侧本质上是“冷”的,那么就可以将很少执行的块放在函数的末尾(在ret
之后)。编译器有各种启发式方法来猜测
if
条件通常是否为真,因此即使没有来自定型运行得数据,编译器仍然可以进行猜测(对于档案导引优化).它可以首先使用if
或else
部分来布局机器代码.此外,就前端吞吐量而言,分支的非执行穿越路径通常比执行路径的成本要低一些。这是在正确预测的前提下。现代CPU在大的连续块中获取机器代码,比如一次16或32字节,但在执行分支上,它们可能无法使用所有这些字节,并且必须在看到更多指令之前进行另一次获取。
一些ISA具有机器代码分支提示,编译器可以使用这些机器代码分支提示来告诉硬件分支预测器一个分支可能走哪条路,但除此之外,没有用于档案导引优化或
[[likely]]
/[[unlikely]]
或GNU C__builtin_expect
的机制来影响分支预测。不包括英特尔,因为Sandybridge:Why did Intel change the static branch prediction mechanism over these years?.另请参阅:
顺便说一句,GCC在这方面做得不太好。**if/else的两边都是
call printf
和store toa
,只是值不同。**它已经在使用push/pop进行堆栈对齐,所以它可以保存/恢复RBX,以便有地方存储printf中的比较结果。它甚至可以生成无分支代码,使用cmov
在两个格式字符串指针之间进行选择。值得注意的是,由于
mov ebx, imm32
和mov edi, imm32
是无条件执行的,因此分支的一端执行了更多的指令,然后如果分支没有被执行,我们再运行一次,这就像int ebx = 2;
/if(a<=5) ebx=3;
而不是else
中的=2
,这是保持分支更简单的折衷(任何地方都没有jmp
)与运行额外的指令。现代x86 CPU非常宽,额外的指令独立于任何东西,因此这里有指令级并行。有趣的无分支方式是,将字符串以8个字节的间隔打包在一起,这样我们就可以使用单个寻址模式生成其中一个的地址。