if-branch 比 else 分支快吗？

Is the if-branch faster than the else branch?

提问人：glades 提问时间：10/8/2022 最后编辑：glades 更新时间：10/9/2022 访问量：766

问：

我遇到了这个非常好的信息图，它粗略估计了用于某些操作的 CPU 节。在学习时，我注意到一个条目“如果的右分支”，我假设它是如果满足条件时将要采取的分支“如果”（编辑：正如评论中指出的那样，“右”实际上意味着“正确预测的分支”）。这让我想知道与 else 分支相比，if 分支是否有任何（甚至很小）速度差异。

例如，比较以下非常精简的代码：

演示

#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 缓存中获取。这（理论上）是否会导致在分支预测模式建立之前“正确”分支的小幅加速？

C++ 性能 程序集 x86 分支预测

评论

5赞 Nelfeal 10/8/2022
在同一信息图中向下几行，您可以看到“if 的错误分支（分支错误预测）”。与条件是否满足无关，而是与条件结果是否预测有关。
1赞 463035818_is_not_an_ai 10/8/2022
本文没有正式定义“右分支”的含义，但在关于分支的段落中，您会发现“如果 CPU 正确猜测执行将要去哪里（这是在实际计算 if 的条件之前），那么分支操作的成本约为 1-2 个 CPU 周期。这就是图中“右分支”表示的 1-2 个周期
3赞 Eljay 10/8/2022
if-branch 比 else 分支快吗？ 不，预测的分支比错误预测的分支快。
1赞 Taekahn 10/8/2022
您假设“正确”分支是指真正的分支。这篇文章暗示“正确”的分支是正确预测的分支

答：

3赞 Miles Budnek 10/8/2022 #1

不，和 分支之间没有真正的区别，这不是您链接的图形所说的“正确”分支的意思。“正确”意味着 CPU 的分支预测在比较完成之前正确地猜到了将采用哪个分支。ifelse

现代 CPU 是流水线的。在完成当前指令之前，他们开始处理下一条指令。这可以显着提高性能，因为这意味着 CPU 可以始终保持其所有不同的子组件（指令解码器、ALU 的不同部分、内存控制器等）处于忙碌状态，而不是在 CPU 的另一个组件工作时让它们处于空闲状态。也就是说，它可以同时执行加法、从内存中获取操作数和解码指令。

不过，这种流水线取决于知道接下来将执行什么指令，而条件分支指令会给它带来麻烦。在您的示例中，CPU 不知道需要执行的下一条指令是在指令完成之后还是在指令完成之后执行，因此它会猜测。它开始在其中一个分支上工作，当最后完成时，它会看看它是否猜对了。如果是这样，那就太好了，它按照以下说明完成的部分工作是有效的，并且会像往常一样继续进行。但是，如果它猜错了，那么它之后在指令上所做的所有工作都必须被扔掉，它开始在另一个分支上工作，这需要一些时间。偶尔的错误猜测不会产生明显的性能差异，但如果它经常猜错，它可能会开始累积并产生很大的差异。jle .L2mov edi, OFFSET FLAT:.LC0mov edi, OFFSET FLAT:.LC1cmpcmpjle

另请参阅 StackOverflow 上评分最高的答案。

请注意，在一些较旧的或嵌入式的 CPU 上，分支预测算法本质上只是“总是猜测第一个”，因此在此类 CPU 上，路径会更慢，因为默认情况下分支预测永远不会猜测。在这些 CPU 上，GCC 或 C++20 的属性可用于告诉编译器哪个分支更有可能，以便它将生成汇编代码以使更有可能的路径成为“第一个”，即使它是 .else__builtin_expect[[likely]]else

评论

1赞 Henrique Bucher 10/8/2022
事实并非如此。在较旧的 CPU 中，它有很大的不同，以至于 C++20 中相应的 likely 宏和 probable 属性是在 en.cppreference.com/w/cpp/language/attributes/likely gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html 创建的__builtin_expect
0赞 Miles Budnek 10/8/2022
@HenriqueBucher 我不确定您要纠正的是什么部分？诸如此类的东西是分支预测算法做出的猜测的输入。除非你的意思是在分支预测算法本质上是“总是猜真”的 CPU 上速度较慢？__builtin_expectelse
0赞 Henrique Bucher 10/9/2022
是的，if 分支是通过推测计算的，而不是 else。现代 CPU 虽然使用动态预测，但旧的 CPU 就是这样
0赞 Miles Budnek 10/9/2022
@HenriqueBucher 添加了有关此的注释。
1赞 Peter Cordes 10/9/2022
像 __builtin_expect 这样的东西是分支预测算法做出的猜测的输入——不，根本不是。 影响编译器对分支布局的决策，哪个站点将具有已获取的分支与未获取的分支（这比预测与错误预测的差异要小，但 I 缓存位置和管道效应仍然存在）。如果可能的话，还决定将 if 转换为无分支。编译时分支提示没有任何机制（在大多数 ISA 上）甚至提示运行时预测。（@HenriqueBucher）__builtin_expect
4赞 Jérôme Richard 10/8/2022 #2

简而言之，在主流处理器上没有，但在一些旧/嵌入式处理器上是。

现代主流处理器非常擅长预测条件（假设它们不是第一次执行，或者测试可以提前完成）。当一个分支被正确预测时，几乎没有成本（除了使用在某些特定端口上执行的分支单元）。处理器可以推测性地获取并执行预测的条件块的指令。当分支未正确预测时，处理器必须执行一种非常昂贵的回滚操作（通常为 5-15 个周期）。

一些嵌入式处理器和旧处理器使用静态预测算法。例如，他们可以假设从未采用分支。在此类处理器上，执行块通常比假设编译器不对块重新排序的速度快（这在启用优化时非常频繁）。开发人员可以提供内置提示，以帮助编译器生成代码，该代码可由使用静态分区的处理器更有效地执行。配置文件引导优化可用于自动查找通常为真/假的条件，并相应地重新排序分支以提高性能。ifelse

主流（服务器、桌面和高端移动）处理器主要使用动态预测算法。例如，他们可以跟踪和记忆何时采取分支，以便了解将来采取分支的概率。处理器通常具有一组有限的条件分支跟踪。因此，当代码具有太多（嵌入的）条件分支指令时，可以改用静态分区算法作为回退方法。

值得一提的是，在某些情况下，预测信息可以重置/刷新，例如当进程被抢占时（如@HenriqueBucher所指出的）。这意味着当存在许多上下文切换时，预测的效果可能会低得多。请注意，推测可以部分由某些特定指令集控制，以减轻 Spectre 等漏洞。

跳转到一个远远不可预测的位置可能代价高昂，因为处理器需要获取可能不在指令缓存中的指令。就您而言，这在主流 x86-64 处理器上当然无关紧要，因为最近的 x86-64 处理器预计会很快将程序的所有指令加载到缓存中。例如，Skylake 处理器可以从指令缓存中获取 16 字节/周期，而 Zen 2 处理器达到 32 字节/周期。两者都可以将 64 字节的缓存行加载到指令缓存中。

关于最近英特尔处理器的分支预测算法的公开信息并不多。AMD Zen 2+ 处理器之一有据可查：它使用高效的 TAGE 预测器与感知器相结合，以便根据过去的统计数据预测条件的结果。您可以在此处找到有关其行为的详细信息。

评论

1赞 Henrique Bucher 10/8/2022
有一点是，一旦进程被抢占，动态预测就会被重置。此时，必须重新生成分支预测表，以便静态预测规则在线程重启时仍计算在内。
1赞 Jérôme Richard 10/8/2022
@HenriqueBucher 确实是好点子。我在答案中添加了这个。谢谢。
2赞 Peter Cordes 10/9/2022 #3

我假设的“if的右分支”是满足条件时将要采用的分支“if”。

不，它谈论的是正确的分支预测，而不是降低表中的“if（分支错误预测）的错误分支”条目。无论 C 源代码中是否有，这都是一回事。else

一个条件分支需要由前端预测才能不停顿，但猜错了意味着它必须倒带并丢弃错误推测的指令。无论是否有零件，这都适用。请参阅 Mysticial 的著名答案：为什么处理排序数组比处理未排序数组更快？else

一个 just 要求在一个指令块中有一个额外的无条件分支来不运行另一个指令块。（就您而言，这就是 ）。另一种选择是将一个块放在其他地方（例如，在函数底部的 之后），这样快速路径上就没有已取的分支，但另一条路径有一个 taken 和 a taken 回到 if/else 之后重新连接另一个路径。elsejmp .L3retjccjmp

正如你所看到的，调用 printf 表示“a > 5”的右分支更接近 cmp - 指令。因此，在查看数据缓存时，可能会出现这样一种情况，即调用 printf 的指令已经加载到缓存行中，而 else 分支必须首先从 L2 或 L3 缓存中获取。这（理论上）是否会导致在分支预测模式建立之前“正确”分支的小幅加速？

是的，I-cache 位置的分支布局是一回事，大部分或完全独立于分支预测。

正如你所说，I-cache 局部性是一回事，所以将很少执行的块放在函数的末尾（在 之后）是编译器可以做的事情，如果它知道（或者你用 or 告诉它）if/else 的一侧本质上是“冷”的。ret[[likely]][[unlikely]]

编译器具有各种启发式方法，用于猜测条件是否正常为真，因此即使没有来自训练运行的数据，它们仍然可以进行猜测（用于配置文件引导优化）。它可以先用 if 或 else 部分布置机器代码。if

此外，就前端吞吐量而言，分支的未采用的落通路径通常比采用的路径略便宜。这是假设正确的预测。现代 CPU 在大型连续块中获取机器代码，例如一次 16 或 32 个字节，但在 taken 分支上，它们可能无法使用所有这些字节，并且必须进行另一次获取才能看到更多指令。

一些 ISA 有机器代码分支提示，编译器可以使用这些提示来告诉硬件分支预测器分支可能会走哪条路，但除此之外，没有配置文件引导优化或/或 GNU C 的机制来影响分支预测。除了通过回退到静态预测的 CPU 上的布局进行静态预测;这不包括自 Sandybridge 以来的英特尔：为什么英特尔在这些年里改变了静态分支预测机制？[[likely]][[unlikely]]__builtin_expect

另请参阅：

顺便说一句，海湾合作委员会在这里做得并不好。if/else 的两端都调用 printf 并存储到 a，只是值不同。而且它已经使用推/弹出进行堆栈对齐，因此它可以保存/恢复 RBX，以便在某个地方存储跨 printf 的比较结果。它甚至可以创建无分支代码，用于在两个格式字符串指针之间进行选择。cmov

hand_written_main:
   push    rbx                     # realign the stack and save RBX
   mov     ebx, 2
   mov     edi, OFFSET FLAT:.LC0   # we can set regs unconditionally, no else needed

   cmp dword ptr [RIP+a], 5       # splitting to mov+cmp might be more efficient for macro-fusion of cmp/jcc and maybe micro-fusion
   jle     .L2
   mov     edi, OFFSET FLAT:.LC1   # or RIP-rel LEA in a PIE
   mov     ebx, 3
.L2:

   xor     eax, eax          # number of XMM args in regs for variadic functions
   call    printf
   mov     DWORD PTR a[rip], ebx
   pop     rbx
   ret

有趣的是，这为分支的一侧执行了更多指令，因为 和 无条件执行，然后如果分支没有被占用，我们再次运行它们。这就像 / 而不是 .这是保持分支更简单（无处可去）与运行额外指令的权衡。现代 x86 CPU 非常宽，额外的指令独立于任何内容，因此这里有指令级并行性。mov ebx, imm32mov edi, imm32int ebx = 2;if(a<=5) ebx=3;=2elsejmp

还有一种有趣的无分支方式，将字符串打包在一起，相距 8 个字节，这样我们就可以用单一寻址模式生成一个或另一个的地址。

hand_written_main:
   push    rbx                     # realign the stack and save RBX

   xor     ebx, ebx
   cmp   dword ptr [RIP+a], 5
   setle   bl                       # bl = (a<=5)
   lea     edi, [gt5msg + rbx*8]    # In a PIE, we'd need [rdi + rbx*8] with a separate RIP-relative LEA
   add     bl, 2                    # 2 + (a<=5) = 2 or 3

   xor     eax, eax          # number of XMM args in regs for variadic functions
   call    printf
   mov     DWORD PTR a[rip], ebx
   pop     rbx
   ret

.section .rodata
.p2align 3
 gt5msg: .asciz "a > 5!"       # <= 8 bytes long, in fact 7 so there's an extra 1 byte of padding.
.p2align 3
 le5msg: .asciz "a <= 5!"     # starts exactly 8 bytes after the previous message

评论

0赞 glades 10/11/2022
这是一个很好的答案，非常感谢！另一方面：你可以推荐什么书来学习 x86 汇编？感觉如果我现在不去追求它，我就会错过一些东西。

上一个：致命：./config 中“receive.denycurrentbranch”的配置值错误

下一个：将其他 *.rst - 文件中的全文部分包含到此文件中？