if分支比else分支快吗？

Question

我看到了这张非常漂亮的信息图，它大致估计了用于某些操作的CPU周期。在学习的时候，我注意到了一个条目“如果的右分支”，我假设如果满足条件，“如果”将要分支（编辑：正如评论中指出的，“右”实际上意味着“正确预测的分支”）。这让我怀疑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 64bit中生成此程序集：

.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

如您所见，右边的分支为“a”调用printf

Answer 1

匿名用户

如果满足条件，我假设“if的右分支”是“if”的分支。

不，这是关于正确的分支预测，而不是降低表中的“if的错误分支（分支预测失误）”条目。这是一个问题，无论C源代码中是否存在else。

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

另一个选项是将一个块放在其他地方（例如，在函数底部的ret之后），因此在快速路径上没有已获取的分支，但另一条路径有已获取的jcc和已获取的jmp返回到if/否则之后重新加入另一条路径。

如您所见，右边的分支为“a”调用printf

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

正如您所说，I-ache局部性是一件事，因此如果编译器知道（或者您使用[[可能]]或[[不可能]]告诉它）if/的一侧本质上是“冷的”，那么将很少执行的块放在函数的末尾（在ret之后）是编译器可以做的事情。

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

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

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

另请参阅：

• 是否可以告诉分支预测器跟随分支的可能性有多大
• 在if-else语句中，GCC的__builtin_expect有什么优势
• 当skylake CPU错误预测分支时会发生什么？-早期分支恢复可以在预测失误的分支uop到达失效之前开始，因此它可以与在发现预测失误的之前处理独立指令的无序执行程序并行进行
• 为什么这些年来英特尔改变了静态分支预测机制？-即使动态预测器碰巧很冷，静态预测（向后执行，向前不执行）也不再是现代英特尔CPU所做的事情。IDK，如果英特尔现在可能已经改变了什么，那么刷新BPU历史记录以缓解幽灵是一件更常见的事情，这会使寒冷的情况变得更常见，因此更值得担心和优化

顺便说一句，海湾合作委员会在这里做得并不好。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

有趣的是，这会为分支的一侧执行更多的指令，因为movebx、imm32和movedi、imm32无条件执行，如果分支没有执行，我们会再次运行它们。这就像＜code＞int ebx＝2/如果（a

还有有趣的无分支方式，将字符串打包在一起，相隔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

Answer 2

不，if 和 else 分支之间没有真正的区别，这不是您链接的“正确”分支的图形的含义。通过“正确”，这意味着 CPU 的分支预测在进行比较之前正确猜测了将采用哪个分支。

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

这种流水线操作依赖于知道接下来将执行什么指令，而条件分支指令则是一个难题。在您的示例中，在< code>cmp指令完成之前，CPU不知道< code>jle .L2之后需要执行的下一条指令是< code>mov edi，OFFSET FLAT:.LC0还是< code>mov edi，OFFSET FLAT:.LC1，因此它会猜测。它开始处理其中一个分支，当< code>cmp最终完成时，它会查看自己是否猜对了。如果是的话，很好，它按照下面的指令所做的部分工作是有效的，它会像正常一样继续运行。如果它猜错了，那么它在< code>jle之后对指令所做的所有工作都必须丢弃，并且它开始处理另一个分支，这需要一些时间。偶尔不正确的猜测不会产生明显的性能差异，但如果它经常猜测错误，它就会开始累积并产生很大的差异。

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

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

Answer 3

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

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

一些嵌入式处理器和旧处理器使用静态预测算法。例如，他们可以假设该分支从未被采用。在这样的处理器上，执行< code>if块通常比执行< code>else块要快，前提是编译器不对块进行重新排序(这在启用优化时非常常见)。开发人员可以提供内置提示，以便帮助编译器生成代码，该代码可以由使用静态分区的处理器更有效地执行。性能分析优化可用于自动查找常为真/假的条件，并根据性能对分支进行相应的重新排序。

主流（服务器、台式机和高端移动）处理器主要使用动态预测算法。例如，它们可以跟踪和记忆何时采取分支或不采取分支，以了解未来采取分支的概率。处理器通常跟踪有限的条件分支集。因此，当代码有太多（覆瓦）条件分支指令时，可以使用静态划分算法作为回退方法。

值得一提的是，在某些情况下，预测信息可以被重置/刷新，比如当进程被抢占时（正如@HenriqueBucher所指出的）。这意味着当有许多上下文切换时，预测的有效性会大大降低。请注意，猜测可以部分由一些特定的指令集控制，以减轻像幽灵这样的漏洞。

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

最近英特尔处理器的分支预测算法没有太多公开信息。AMD Zen 2处理器之一有很好的记录：它使用高效的TAGE预测器和感知器相结合，以便根据过去的统计数据预测条件的结果。你可以在这里找到关于它的行为的详细信息。