本文发自 http://www.binss.me/blog/learning-branch-prediction-opt/,转载请注明出处。

最近在优化一个模块,算法上已经遇到瓶颈,于是开始钻研一些奇技淫巧。恰逢看 folly 库中发现在分支处有大量的 FOLLY_LIKELY / FOLLY_UNLIKELY ,其实际上是对 __builtin_expect 的包装,用于告知编译器更倾向于走哪种分支。

一个典型的示例是:

#include <cstdlib>
#include <cstdio>

#define likely(x)    __builtin_expect(!!(x), 1)
#define unlikely(x)  __builtin_expect(!!(x), 0)

int main(int argc, char *argv[]) {
  auto a = atoi(argv[1]);
  auto b = atoi(argv[2]);
  if (likely((a + b) == 2)) {
     a += 100;
  }
  else {
     a -= 100;
  }
  printf ("%d\n", a);
  return 0;
}

按照网上文章的说法,likely 可以提示编译器生存的汇编代码默认走 if 分支,如果不满足再发生跳转,产生类似这样的语句:

cmp a + b, 2
jne x
lea temp, a + 100
...
x:
lea temp, a - 100

如果使用的是 unlikely ,则改为:

cmp a + b, 2
je x
lea temp, a - 100
...
x:
lea temp, a + 100

如果代码实际运行时和设计一致(比如认为大多数情况下会走到 if 分支,所以用了 likely),则可以提升分支预测的命中率,减少预测失败时的跳转。

出于意料的是,当我使用编译器编译上述代码时,无论使用 likely 还是 unlikely ,都产生了以下指令:

lea    esi,[rbx+0x64]
mov    edi,0x40069c
add    eax,ebx
sub    ebx,0x64
cmp    eax,0x2
cmovne esi,ebx
xor    eax,eax
call   4004b0 <printf@plt>

我尝试了多个版本的 gcc ,发现从 gcc 4.9 开始,编译器就开始产生上述代码:它提前对两个分支都进行了评估,将值存入不同的寄存器中,最后再根据比较结果选择相应寄存器的值。相比 4.9 之前产生的代码,最大的特点是避免了跳转语句,取而代之的是一个 cmove 。

cmove

cmove 是 x86 引入的条件赋值指令。我们知道 CPU 分支预测失败后,需要清空流水线并跳转到目标分支代码继续运行,这极大地影响了性能。利用 cmove ,可以在某些场景下消除跳转指令,从而避免了分支预测失败。

但由于 cmove 的结果依然依赖于前面的 cmp 语句(依赖于 rflags 寄存器的值),若后续有指令依赖于 cmove 要修改的寄存器,则这些指令难以提前评估。有趣的是,上述代码却提前评估了两个分支,猜测是编译器认为这两个分支都太简单了,提前算代价不高、性能更好。

我们尝试把分支写的更复杂:

if (likely((a + b) == 2)) {
  for (int i = c; i < d; ++i) {
      a += i;
  }
}
else {
   a -= 100;
}
printf ("%d\n", a);

这下编译器老老实实用跳转了:

add    r13d,r14d
mov    edx,0xa
mov    r15,rax
mov    ebx,eax
call   4004c0 <strtol@plt>
cmp    r13d,0x2
jne    400570 <main+0xa0>
mov    edx,eax
cmp    eax,r15d
jle    400551 <main+0x81>
nop    DWORD PTR [rax+0x0]
add    ebp,ebx
add    ebx,0x1
cmp    ebx,edx
jne    400548 <main+0x78>
mov    esi,ebp
mov    edi,0x4006fc
xor    eax,eax
call   4004b0 <printf@plt>
...
400570:
lea    ebp,[r14-0x64]
jmp    400551 <main+0x81>

Gcov

那么什么时候应该加 likely / unlikely 呢?虽然某些分支从业务逻辑上,我们能够确定其偏好,但更多的代码往往需要真正跑起来才能知道。这时可以借助 Gcov 来统计代码的执行情况。

Gcov 是 GCC 套件中包含的代码覆盖率分析工具。只需在编译时加上 -fprofile-arcs -ftest-coverage ,链接时加上 -fprofile-arcs

比如对于代码:

#include <cstdlib>
#include <cstdio>

#define likely(x)    __builtin_expect(!!(x), 1)
#define unlikely(x)  __builtin_expect(!!(x), 0)

int main(int argc, char *argv[]) {
  auto a = atoi(argv[1]);
  auto b = atoi(argv[2]);
  auto c = atoi(argv[3]);
  int result = 0;
  for (int i = 0; i < c; ++i) {
    if (likely((a + b) == 2)) {
      result += 100;
    } else {
      result -= 100;
    }
  }
  printf("%d\n", result);
  return 0;
}

编译之:

g++ -o test test.cpp -fprofile-arcs -ftest-coverage

可以发现目录下产生了 test.gcno 。然后多次运行 test ,输入不同的参数,生成了 test.gcda

gcno 是 note,描述了 GCC 版本、函数基本信息(名称、行列号等)。

gcda 是 data ,描述程序执行情况(次数等)。

对编译后的程序 test 进行反编译,发现里面插了一堆计数代码:

我们可以通过 gcov 工具对代码生成运行情况:

gcov test.cpp
File 'test.cpp'
Lines executed:90.91% of 11
Creating 'test.cpp.gcov'

会读取 test.gcno 和 test.gcda (多次运行的统计结果) 在同目录下生成 test.cpp.gcov

        -:    0:Source:test.cpp
        -:    0:Graph:test.gcno
        -:    0:Data:test.gcda
        -:    0:Runs:8
        -:    0:Programs:1
        -:    1:#include <cstdlib>
        -:    2:#include <cstdio>
        -:    3:
        -:    4:#define likely(x)    __builtin_expect(!!(x), 1)
        -:    5:#define unlikely(x)  __builtin_expect(!!(x), 0)
        -:    6:
        8:    7:int main(int argc, char *argv[]) {
        8:    8:  auto a = atoi(argv[1]);
        8:    9:  auto b = atoi(argv[2]);
        8:   10:  auto c = atoi(argv[3]);
        8:   11:  int result = 0;
      808:   12:  for (int i = 0; i < c; ++i) {
      800:   13:    if (likely((a + b) == 2)) {
      800:   14:      result += 100;
        -:   15:    } else {
    #####:   16:      result -= 100;
        -:   17:    }
        -:   18:  }
        8:   19:  printf("%d\n", result);
        8:   20:  return 0;
        -:   21:}

数字表示该行运行到的次数。 ##### 表示从来没运行过。

可以通过 lcov 进一步生成可视化的运行情况报告:

lcov -d . -o test.info -b . -c
genhtml -o result test.info

会生成 result 文件夹,可以用浏览器打开其中的 test.cpp.gcov.html 。可以发现一目了然:

第 14 行的分支走的次数最多,而第 16 行的分支一次都没走到过。这个信息可以指导我们为分支加上 likely 。

更进一步地,直接使用编译器的 PGO (Profile Guided Optimization),根据运行结果来 "训练" 编译过程。

PGO

简单来说,PGO 即根据程序真实的运行情况,生成一份 profile ,来指导下次编译,以产生更加贴近真实运行情况、性能更好的代码。

g++ -o test test.cpp -fprofile-generate

编译后,运行代码会发现同样产生了 test.gcda 文件,随后可以用它来指导编译:

g++ -o test test.cpp -fprofile-use

然而发现汇编没啥变化,可能是因为代码太简单的原因。