168

我遇到了一个#define他们使用的__builtin_expect.

文档说：

内置功能：long __builtin_expect (long exp, long c)

您可以使用__builtin_expect为编译器提供分支预测信息。一般来说，您应该更喜欢为此使用实际的配置文件反馈 ( -fprofile-arcs)，因为众所周知，程序员不善于预测他们的程序实际执行情况。但是，有些应用程序很难收集这些数据。

返回值是 的值exp，它应该是一个整数表达式。内置的语义是期望 exp == c. 例如：

      if (__builtin_expect (x, 0))
        foo ();

将表明我们不希望调用foo，因为我们希望x为零。

那么为什么不直接使用：

if (x)
    foo ();

而不是复杂的语法__builtin_expect？

4

7 回答 7

216

想象一下将从以下位置生成的汇编代码：

if (__builtin_expect(x, 0)) {
    foo();
    ...
} else {
    bar();
    ...
}

我想它应该是这样的：

  cmp   $x, 0
  jne   _foo
_bar:
  call  bar
  ...
  jmp   after_if
_foo:
  call  foo
  ...
after_if:

您可以看到指令的排列顺序是bar案例先于案例foo（与 C 代码相反）。这可以更好地利用 CPU 流水线，因为跳转会破坏已经获取的指令。

在执行跳转之前，它下面的指令（bar案例）被推送到管道中。由于这种foo情况不太可能发生，因此跳跃也不太可能，因此不太可能破坏管道。

于 2011-09-08T11:14:34.113 回答
60

让我们反编译看看 GCC 4.8 用它做了什么

Blagovest 提到了分支反转来改进管道，但是当前的编译器真的做到了吗？让我们来了解一下！

没有__builtin_expect

#include "stdio.h"
#include "time.h"

int main() {
    /* Use time to prevent it from being optimized away. */
    int i = !time(NULL);
    if (i)
        puts("a");
    return 0;
}

使用 GCC 4.8.2 x86_64 Linux 编译和反编译：

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

输出：

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       75 0a                   jne    1a <main+0x1a>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1
  15:       e8 00 00 00 00          callq  1a <main+0x1a>
                    16: R_X86_64_PC32       puts-0x4
  1a:       31 c0                   xor    %eax,%eax
  1c:       48 83 c4 08             add    $0x8,%rsp
  20:       c3                      retq

内存中的指令顺序没有改变：首先是puts然后retq返回。

和__builtin_expect

现在替换if (i)为：

if (__builtin_expect(i, 0))

我们得到：

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       74 07                   je     17 <main+0x17>
  10:       31 c0                   xor    %eax,%eax
  12:       48 83 c4 08             add    $0x8,%rsp
  16:       c3                      retq
  17:       bf 00 00 00 00          mov    $0x0,%edi
                    18: R_X86_64_32 .rodata.str1.1
  1c:       e8 00 00 00 00          callq  21 <main+0x21>
                    1d: R_X86_64_PC32       puts-0x4
  21:       eb ed                   jmp    10 <main+0x10>

puts被移到函数的最后，返回retq！

新代码基本相同：

int i = !time(NULL);
if (i)
    goto puts;
ret:
return 0;
puts:
puts("a");
goto ret;

此优化未使用-O0.

但是祝你好运，编写一个运行__builtin_expect比没有运行更快的示例，那些日子 CPU 真的很聪明。我的天真尝试就在这里。

C++20[[likely]]和[[unlikely]]

C++20 已经标准化了那些 C++ 内置函数：如何在 if-else 语句中使用 C++20 的可能/不太可能属性他们很可能（双关语！）做同样的事情。

于 2015-07-21T13:35:00.800 回答
41

的想法__builtin_expect是告诉编译器您通常会发现表达式的计算结果为 c，以便编译器可以针对这种情况进行优化。

我猜有人认为他们很聪明，他们这样做是在加快速度。

不幸的是，除非情况得到很好的理解（他们很可能没有做过这样的事情），否则很可能会让事情变得更糟。文档甚至说：

一般来说，您应该更喜欢为此使用实际的配置文件反馈 ( -fprofile-arcs)，因为众所周知，程序员不善于预测他们的程序实际执行情况。但是，有些应用程序很难收集这些数据。

一般来说，你不应该使用__builtin_expect，除非：

  • 你有一个非常现实的性能问题
  • 您已经适当地优化了系统中的算法
  • 您有性能数据来支持您的断言，即最有可能出现特定情况
于 2011-09-08T11:03:59.067 回答
13

好吧，正如它在描述中所说，第一个版本在构造中添加了一个预测元素，告诉编译器该x == 0分支是更有可能的分支 - 也就是说，它是您的程序将更频繁地采用的分支。

考虑到这一点，编译器可以优化条件，以便在预期条件成立时需要最少的工作量，但在出现意外条件时可能不得不做更多的工作。

看看在编译阶段和生成的程序集中是如何实现条件的，看看一个分支可能比另一个分支的工作量少。

但是，如果所讨论的条件是被大量调用的紧密内部循环的一部分，我只希望这种优化具有显着的效果，因为生成的代码中的差异相对较小。如果你以错误的方式优化它，你很可能会降低你的性能。

于 2011-09-08T11:02:44.873 回答
1

我没有看到任何解决我认为您要问的问题的答案，意译：

是否有更便携的方式向编译器提示分支预测。

你的问题的标题让我想到这样做：

if ( !x ) {} else foo();

如果编译器假设 'true' 更有可能，它可以优化不调用foo().

这里的问题是，您通常不知道编译器会假设什么——因此任何使用这种技术的代码都需要仔细测量（如果上下文发生变化，可能会随着时间的推移进行监控）。

于 2015-05-31T18:25:00.400 回答
0

在大多数情况下，您应该保持分支预测不变，您无需担心它。

一种有益的情况是具有大量分支的 CPU 密集型算法。在某些情况下，跳转可能会导致超出当前 CPU 程序缓存，从而使 CPU 等待软件的下一部分运行。通过在最后推动不太可能的分支，您将保持记忆紧密，只在不太可能的情况下跳转。

于 2020-10-22T11:39:49.980 回答
0

我根据@Blagovest Buyukliev 和@Ciro 在Mac 上测试它。组件看起来很清晰，我添加了评论；

命令是 gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

当我使用 -O3 时，无论 __builtin_expect(i, 0) 是否存在，它看起来都是一样的。 

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp     
0000000000000001    movq    %rsp, %rbp    // open function stack
0000000000000004    xorl    %edi, %edi       // set time args 0 (NULL)
0000000000000006    callq   _time      // call time(NULL)
000000000000000b    testq   %rax, %rax   // check time(NULL)  result
000000000000000e    je  0x14           //  jump 0x14 if testq result = 0， namely jump to puts
0000000000000010    xorl    %eax, %eax   //  return 0   ,  return appear first 
0000000000000012    popq    %rbp    //  return 0
0000000000000013    retq                     //  return 0
0000000000000014    leaq    0x9(%rip), %rdi  ## literal pool for: "a"  // puts  part, afterwards
000000000000001b    callq   _puts
0000000000000020    xorl    %eax, %eax
0000000000000022    popq    %rbp
0000000000000023    retq

使用 -O2 编译时，使用和不使用 __builtin_expect(i, 0) 看起来不同

首先没有

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    jne 0x1c       //   jump to 0x1c if not zero, then return
0000000000000010    leaq    0x9(%rip), %rdi ## literal pool for: "a"   //   put part appear first ,  following   jne 0x1c
0000000000000017    callq   _puts
000000000000001c    xorl    %eax, %eax     // return part appear  afterwards
000000000000001e    popq    %rbp
000000000000001f    retq

现在使用 __builtin_expect(i, 0)

testOpt.o:
(__TEXT,__text) section
_main:
0000000000000000    pushq   %rbp
0000000000000001    movq    %rsp, %rbp
0000000000000004    xorl    %edi, %edi
0000000000000006    callq   _time
000000000000000b    testq   %rax, %rax
000000000000000e    je  0x14   // jump to 0x14 if zero  then put. otherwise return 
0000000000000010    xorl    %eax, %eax   // return appear first 
0000000000000012    popq    %rbp
0000000000000013    retq
0000000000000014    leaq    0x7(%rip), %rdi ## literal pool for: "a"
000000000000001b    callq   _puts
0000000000000020    jmp 0x10

总而言之， __builtin_expect 在最后一种情况下有效。

于 2019-08-21T07:03:13.030 回答