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