由于很偶然的原因，这两天瞄了几眼”ZeroMQ”项目，发现项目中使用了’likely/unlikely’这种暗示编译器做分支预测优化的宏（这些宏只是gcc内建函数__builtin_expect的别名)。
其实早在看linux kernel源码时，就不止一次看到这组宏。但是，对此并没有放在心上。仅仅粗略搜了一下，得知‘likely/unlikely这组宏可以向编译器提供分支预测信息，以便编译器可以更好的安排指令顺序来提高效率’就没有再深入下去了。
因为我觉得，这种级别的优化估计能提高个千分之几就已经算很不错了，内核可能是为了把CPU性能压榨到极致所以才使用的。而应用层远没有达到需要这种优化的极限。
然而今天这组宏出现在一个应用级的程序代码里面，让我意识到事情可能与我的想当然相差甚远。
于是写了段代码测了一下：
//make 'gcc -g -O2 -o a a.c b.c'
//b.c
//之所以把foo1、foo2函数放在b.c文件里，是为了防止编译器把foo函数调用给优化掉
void foo1 {}
void foo1 {}
//a.c
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
void foo1();
void foo2();
void bar()
{
foo2();foo2();foo2();foo2();foo2();foo2();foo2();foo2();
}
int main(int argc)
{
int i;
for (i = 0; i < 1024 * 1024 * 640; i++) {
if (likely(argc == 1)) {
foo1();
} else {
bar();
}
}
return 0;
}
测试平台：
Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
测试结束：
不使用likely宏(即直接使用if(argc == 1))的前提下，使用‘time ./a’测试结果如下：
./a 2.01s user 0.03s system 97% cpu 2.100 total
使用likely宏之后，再次使用’time ./a’测试结果下如：
./a 1.63s user 0.03s system 99% cpu 1.672 total
从上面结果可以得出，性能相差了将近20%。
下面反汇编两种不同的情况，看看__builtin_expect到底让编译器做了什么，会让效果这么明显。
需要注意的是，只有使用了gcc -O2，__builtin_expect函数才会让编译器产生优化效果。
先来看不使用likely宏的a.c反汇编代码如下:
_bar: ## @bar
.cfi_startproc
## 此处省略无关代码
Ltmp2:
.cfi_def_cfa_register %rbp
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
popq %rbp
jmp _foo2 ## TAILCALL
.cfi_endproc
## 此处省略无关代码
_main: ## @main
.cfi_startproc
## 此处省略无关代码
movl %edi, %r14d
movl $671088640, %ebx ## imm = 0x28000000
.p2align 4, 0x90
LBB1_1: ## =>This Inner Loop Header: Depth=1
xorl %eax, %eax
cmpl $1, %r14d
jne LBB1_3
## BB#2: ## in Loop: Header=BB1_1 Depth=1
callq _foo1
jmp LBB1_4
.p2align 4, 0x90
LBB1_3: ## in Loop: Header=BB1_1 Depth=1
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
LBB1_4: ## in Loop: Header=BB1_1 Depth=1
decl %ebx
jne LBB1_1
## BB#5:
xorl %eax, %eax
popq %rbx
popq %r14
popq %rbp
retq
.cfi_endproc
由于测试代码实现太简单了，以致于连编译器都没什么可优化的了，所以它惟一能做的就是把bar函数内联了。
从标号BB#2到LBB1_3之间即为if(cond == true)时调用的代码，即调用foo1函数，从标号LBB1_3到LBB1_4之间即为else执行的代码即调用了bar函数，编译器认为bar函数内联效率更高，所以这里是bar函数的内联形式。
可以看到，基本上汇编指令的排布就是我们C语言中的书写排布。
下面再来看一下使用likely之后，汇编指令是如何排布的。
_bar: ## @bar
.cfi_startproc
## 省略无关代码
Ltmp2:
.cfi_def_cfa_register %rbp
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
popq %rbp
jmp _foo2 ## TAILCALL
.cfi_endproc
.globl _main
.p2align 4, 0x90
_main: ## @main
.cfi_startproc
## 省略无关代码
movl %edi, %r14d
movl $671088640, %ebx ## imm = 0x28000000
jmp LBB1_1
LBB1_3: ## in Loop: Header=BB1_1 Depth=1
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
xorl %eax, %eax
callq _foo2
jmp LBB1_4
.p2align 4, 0x90
LBB1_1: ## =>This Inner Loop Header: Depth=1
xorl %eax, %eax
cmpl $1, %r14d
jne LBB1_3
## BB#2: ## in Loop: Header=BB1_1 Depth=1
callq _foo1
LBB1_4: ## in Loop: Header=BB1_1 Depth=1
decl %ebx
jne LBB1_1
## BB#5:
## 省略无关代码
.cfi_endproc
与未使用likely宏之前的代码相比，相同的是bar函数依被内联了，不同的是，for, if, esle 代码块的布局发生了根本性的变化。
将上面的汇编代码翻译成C代码之后会更加明显。
goto label_start;
label_else:
bar();
goto label_for:
label_start:
for (i = 0; i < 1024 * 1024 * 640; i++) {
if (argc != 1)
goto label_else;
foo1();
label_for:
}
从上面的C代码看出，编译器将高概率指执的代码(for语句逻辑、调用foo1函数)安排在了一起，而将低概率执行的代码块挪到其他地方，以获得更高的效率。
Intel的优化手册中’3.4.1.3节静态预测’指出：
predict backward conditional branches to be taken; rule is suitable for loops
predict forward conditional branches to be NOT taken
Assembly/Compiler Coding Rule 3. (M impact, H generality) Arrange code to be consistent with the static branch prediction algorithm: make the fall-through code following a conditional branch be the likely target for a branch with a forward target, and make the fall-through code following a conditional branch be the unlikely target for a branch with a backward target.
当cpu第一次执行此分支时，由于cpu的BTB(Branch target buffers）还没有历史数据，因此部分CPU会采用静态预测算法。Intel的静态预测算法为：在条件分支预测中，预测所有向前跳转的都不执行，所有向后跳转都会执行。
因此，Intel手册指出，如果条件分支生成的是向前跳转代码，则应该将likely执行的代码紧跟着j*(jmp的条件形式)之后，如果条件分支生成的是向后跳转代码，则应该将likely执行的代码放在要跳转的标号处。
在’3.4.1.5节代码对齐’指出：
Careful arrangement of code can enhance cache and memory locality. Likely sequences of basic blocks should be laid out contiguously in memory. This may involve removing unlikely code, such as code to handle error conditions, from the sequence.See Section 3.7, “Prefetching,” on optimizing the instruction prefetcher.
Assembly/Compiler Coding Rule 12. (M impact, H generality) All branch targets should be 16-byte aligned.
Assembly/Compiler Coding Rule 13. (M impact, H generality) If the body of a conditional is not likely to be executed, it should be placed in another part of the program. If it is highly unlikely to be executed and code locality is an issue, it should be placed on a different code page.
代码对齐一节指出，所有likely执行的代码应该在内存中尽可能连续的存放，而那些unlikely的代码，比如异常处理代码，应该被从这段连续的代码中去除，放到其他地方。
对比上面的汇编发现，GCC的优化与文档描述不完合相同。
GCC确实将unlikely的代码单独拿出来，而让likely的代码尽可能连续。但是对于unlikely的代码却使用了向后跳转条件分支。
让代码更简单一些，然后重新反汇编看一看，C代码如下：
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
void foo1();
void foo2();
int main(int argc, char *argv[])
{
if (likely(argc == 1))
foo1();
else
foo2();
return 0;
}
反汇编代码如下：
## 省略部分无关代码
_main: ## @main
.cfi_startproc
## 省略部分无关代码
xorl %eax, %eax
cmpl $1, %edi
jne LBB0_2
## BB#1:
callq _foo1
LBB0_3:
xorl %eax, %eax
popq %rbp
retq
LBB0_2:
callq _foo2
jmp LBB0_3
.cfi_endproc
可以看出，在编译上面代码时，GCC严格尊守了Intel手册的‘静态预测算法’和‘代码对齐规则’。
但是在编译有for语句的代码时，似乎有其他的规则，让GCC觉得违反静态分支预测会活的更好的性能。
再对比一下两个使用likely宏的代码（一个使用for语句，一个不使用for语句)反汇编之后的代码发现, 带有for语句的代码中有一句伪码‘.p2align 4, 0x90’。
这句代码把unlikely的代码和likely的代码使用nop分开了，猜测这里可能会使这两面代码分别处在不同的cache line上，符合’代码对齐’标准，而由于‘分支静态预测’仅在分支第一次执行时才会使用。而且面都会使用动态预测法。
因此，猜测可能‘代码对齐’带来的好处高于满足‘静态预测’算法，而让GCC选项这么做的原因就是‘代码对齐’规则。
另，在阅读Intel手册时发现，‘3.4.1.2 Spin-Wait and Idle Loops’提到，在实现spinlock时，插入PAUSE指令可以显著提高性能。我又去查阅了linux源码，发现kernel源码中的spinlock也有插入PAUSE指令。
而我之前都是使用while (__sync_test_and_set(lock, 1))来简单实现spinlock，这可能是一种错误的使用形式。
