利用分支预测优化代码

     linux中有likely 和unlikely的宏定义

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

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

       

        __builtin_expect 宏的含义是通知编译器，对相应的分支预测进行优化。

       我们知道顺序执行的代码CPU比较喜欢，因为不需要跳转。对于存在大量跳转或者说是分支的代码，

CPU比较抓狂，因为CPU一般会提前 取指令 译码，甚至提前计算一些结果。如果分支预测错了，就会丢弃

之前的指令，这样会影响效率。

       如果我们提前知道代码 不同分支的执行概率，我们应该尽量让高概率的分支作为条件转移指令的下一

条指令，这样prefetch 和decode 就会选择条件 转移指令的下一条指令，从而预测成功，这正是我们期望的

       __builtin_expect 就是通知编译器哪个分支出现的概率更高的。

__builtin_expect(!!(x),1)表示，告诉编译器，条件x为真的可能性非常高。

__builtin_expect(!!(x),0)表示，告诉编译器，条件x为假的可能性非常高。

#include #include #include #include #define TIMES (10000000) #define BILLION (1000000000) #define MILLION 1000000 #define likely(x) __builtin_expect(x,1) #define unlikely(x) __builtin_expect(x, 0) int main(int argc,char *argv[]) { int i; int j; int *array = NULL; struct timespec tpstart; struct timespec tpend; unsigned long long timeif; unsigned long long timeif_func; struct timeval tv; if(argc != 2) { printf("usage: ./test times\n"); return -1; } int times = atoi(argv[1]); if(clock_gettime(CLOCK_MONOTONIC,&tpstart)) { fprintf(stderr,"Fail to get start time for NULL\n"); return -1; } for(i = 0;i

(tpend.tv_nsec-tpstart.tv_nsec)/1000; printf("%d BLANK OP 's total time is %llu us\n",times,(timeif)); if(clock_gettime(CLOCK_MONOTONIC,&tpstart)) { fprintf(stderr,"Fail to get start time for branch \n"); return -1; } for(i = 0;i if(likely(j >1)) { array = malloc(1000*sizeof(int)); if(array) free(array); } else { gettimeofday(&tv,NULL); } } if(clock_gettime(CLOCK_MONOTONIC,&tpend)) { fprintf(stderr,"Fail to get start time for branch\n"); return -1; } timeif_func =MILLION*(tpend.tv_sec - tpstart.tv_sec)+

(tpend.tv_nsec-tpstart.tv_nsec)/1000; printf("%d FUNCTION's with right prediction cost time is %llu us\n",

times,(timeif_func)); }

注意粗体部分，j>1的概率几乎是100%，所以我们预测j>1,所以这是正确的预测。我们期待，malloc分支作为条件转移指令的下一条指令，这样，我们就能顺序取指令，无须跳转

。

看下生成的汇编出来的代码。

gcc -o test_ok test.c -lrt -O2

objdump -d test_ok >objdump_ok

--------------------------objdump_ok---------------------------------------

8048728: e8 1b fe ff ff call 8048548 804872d: 83 f8 01 cmp $0x1,%eax 8048730: 0f 8e ac 00 00 00 jle 80487e2 8048736: c7 04 24 a0 0f 00 00 movl $0xfa0,(%esp) 804873d: e8 f6 fd ff ff call 8048538 8048742: 85 c0 test %eax,%eax 8048744: 74 08 je 804874e 8048746: 89 04 24 mov %eax,(%esp) 8048749: e8 ca fd ff ff call 8048518

.............................................................

80487e2: 8d 44 24 38 lea 0x38(%esp),%eax 80487e6: c7 44 24 04 00 00 00 movl $0x0,0x4(%esp) 80487ed: 00 80487ee: 89 04 24 mov %eax,(%esp) 80487f1: e8 02 fd ff ff call 80484f8 80487f6: e9 53 ff ff ff jmp 804874e

------------------------------------------------------------------------------------

相反，我们如果预测j<1,即将代码中的likely，改成unlikely，那么我们就做出了错误的预测，那么编译器

生成的汇编代码如下。

gcc -o test_err test.c -lrt -O2

objdump -d test_err >objdump_err

-------------------objdump_err-------------------------------------------

8048738: e8 0b fe ff ff call 8048548 804873d: 83 f8 01 cmp $0x1,%eax 8048740: 0f 8f ac 00 00 00 jg 80487f2 8048746: 8d 44 24 38 lea 0x38(%esp),%eax 804874a: c7 44 24 04 00 00 00 movl $0x0,0x4(%esp) 8048751: 00 8048752: 89 04 24 mov %eax,(%esp) 8048755: e8 9e fd ff ff call 80484f8

.................................

80487f2: c7 04 24 a0 0f 00 00 movl $0xfa0,(%esp) 80487f9: e8 3a fd ff ff call 8048538 80487fe: 85 c0 test %eax,%eax 8048800: 0f 84 54 ff ff ff je 804875a 8048806: 89 04 24 mov %eax,(%esp) 8048809: e8 0a fd ff ff call 8048518

------------------------------------------------------------------------------

从上面可以看出，由于我们的预测错误，gettimeofday放到了下一条指令，如果预取指令 译码，甚至执行，会发现，分支预测错了，丢弃之，然后跳转到malloc那条分支。

我们可以预测，由于分支预测出现了错误，test_ok 执行的速度应该比test_err执行的要快。当然，由于CPU还有Branch Target Buffer，这个BTB可以根据上次执行的转移，来预测本次转移。所以下面的两个程序，执行时间差的并不多。

root@libin:~/program/C/function_call# cat do.sh 

 ./test_err 100000000  &

 ./test_ok  100000000  &

root@libin:~/program/C/function_call# ./do.sh 100000000 BLANK OP 's total time is 1 us root@libin:~/program/C/function_call# 100000000 BLANK OP 's total time is 1 us 100000000 FUNCTION's with right prediction cost time is 9472328 us 100000000 FUNCTION's with wrong prediction cost time is 9751683 us

参考文献：1