现有大部分的cpu的指令都是流水线的，比较标准的如五级流水。即一条指令还没有执行完毕，把下一条指令加载进来，这样可以充分提高cpu的性能。

流水线的效率很高，但是对分支现象非常敏感。因为流水是顺序执行的，碰到分支的时候，不知道如何选取下一条指令加载进来，必须等上一条分支指令执行完毕才能确定下一条指令到底是哪一条。

所以分支预测非常重要；如果分支预测成功，就可以保证流水继续执行，不被中断；实际上，cpu本身有了大量的工作就是提高分支预测的准确率。这里不做详细叙述。

今天看masstree的代码的时候，发现还可以做到软件层面的分支预测。跟钊神交流了一下，他们在平时工作的时候加入了这一特性，还是有一定的效果的。

编译器优化

软件层面的分支预测主要是在编译器上。主要流程就是程序员告诉编译器，我这段分支判断的结果是真还是假的概率大。我们定义如下两个宏：

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

其中likely意思为x为真概率较大，unlikely意为x为假的概率较大。为啥取两次非，这个问题我没想明白

举一个很简单的例子，

int s = rand()%100;
if (unlikely(s > 96)){
    s = s+1;
}else{
    s = s-1;
}

0-100的随机数肯定是大于96的概率较小。下面是likely的用法。

int s = rand()%100;
if (likely(s < 96)){
    s = s+1;
}else{
    s = s-1;
}

接下来我们看看编译器做了什么事情，首先看原始代码的情况：（这里我们为了说明问题，原始代码用-O0的优化，
因为加了-O2优化的时候，编译器会用一条cmovl指令把这个分支消掉。）

.L1:
    movl    %eax, -4(%rbp)
    cmpl    $96, -4(%rbp)    // 没做任何优化，直接判断是否小于96；小于的话跳到L2, 
    jle    .L2
    addl    $12, -4(%rbp)    // s = s+1 ，然后跳到L3
    jmp    .L3
.L2:
    subl    $12, -4(%rbp)
.L3:
    movl    -4(%rbp), %eax
    movl    %eax, %esi
    movl    $.LC0, %edi
    movl    $0, %eax
    call    printf
    movl    $0, %eax
    leave

然后看看在加了likely之后的效果，

L1:
    subl    %edx, %ecx  // 这里的%ecx就是获取的随机数
    cmpl    $95, %ecx
    movl    %ecx, %edx
    /* 这里编译器调整了一下顺序，如果%ecx > 96, 即判断失败，跳到 L2；
        否则直接执行，保证流水线的成功
    */
    jg    .L2
    addl    $1, %edx   // s = s+1
.L3:
    movl    $.LC0, %esi
    movl    $1, %edi
    xorl    %eax, %eax
    call    __printf_chk
    xorl    %eax, %eax
    addq    $8, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret
    /* 有意思的是，编译器把else代码段里的东西扔到了最后，实际上L3才是if-else之后的代码，这样的好处是，
    一旦预测成功，执行if代码段里的东西，可以继续往下执行了，不用再进行跳转 */
.L2:
    .cfi_restore_state
    subl    $1, %edx
    jmp    .L3
    .cfi_endproc

最后看看加入unlikely的效果，

L1:
    subl    %edx, %ecx
    cmpl    $96, %ecx     
    movl    %ecx, %edx   
    jg    .L6                    // 这里直接进行比较，明显不信任s会大于96，这样如果预测成功，一路执行到底。
    subl    $1, %edx        // s = s-1
.L3:                        // if-else结构体之后的代码
    movl    $.LC0, %esi
    movl    $1, %edi
    xorl    %eax, %eax
    call    __printf_chk
    xorl    %eax, %eax
    addq    $8, %rsp
    .cfi_remember_state
    .cfi_def_cfa_offset 8
    ret
.L6:                    //  这里是if代码段里的东西，只有预测失败才会跳到这里，之后再跳到L3执行后面指令
    .cfi_restore_state
    addl    $1, %edx
    jmp    .L3
    .cfi_endproc

总结

上面看了好多汇编代码，其实我们大概知道了编译器在分支预测方面到底做了些什么事情：

• likely: 把if{}代码段里的内容和if-else后面的代码段连起来，保证这样一路没有任何跳转
• unlikely: 把else{}代码段的内容和后面的连起来。

其实总共就做了这两件事，是不是很简单？

还有一个有趣的事情，就是我本来想写一个没有分支预测的代码例子，然而O2的编译器，直接把分支给去掉了。看了很长时间后发现，其实人家用一个cmovl的指令就解决了（该指令是如果cmpl为真就mov）。因为本例太简单了，s只有两种值，s+1或者s-1。提前算好这两个数，然后调用cmovl指令即可。是不是很机智。

所以我们还是要相信编译器的智商。如果一个代码段不复杂，不建议使用分支预测。

性能测试

听品爷说实际系统里的性能能提高大概10% -20% 。我试了几个例子都太简单了，所以编译器已经把我打败了。
所以挖一个坑在此，之后有机会在复杂系统测试一下。