本文发自 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然而发现汇编没啥变化，可能是因为代码太简单的原因。
