分支预测

发表于 |

GCC 扩展 __builtin_expect

C 语言的标准从最开始的 K&R C演变到目前的 ANSI C，在各操作系统平台已经有很多编译器支持了，如 MSVC、GCC、CLANG 等。而 linux 平台的 GCC 除了支持ANSI C 标准之外，还有自己的编译器扩展特性。

其中一个特性就是GCC 支持的编译器分支预测 __builtin_expect 宏，作为编译分支时候的暗示。这个特性在 linux 的内核代码中很常用，用来提升代码执行速度。

具体的，是有 likely 和 unlikely 这两个宏定义

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

实际使用时，我们可以在很大可能执行的分支前面加上 likely。例如下例中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

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

int main()
{
    int a;
    scanf("%d", &a);
    if (likely(a))
    {
        printf("Hula!\n");
    }
    else
    {
        printf("Woo~\n");
    }
    return 0;
}

这样，如果 likely 所在的分支如果有非常大可能执行，则程序运行效率要比普通的分支判断高。具体原因是什么呢？这就涉及到 CPU 流水线作业的相关知识。

CPU 流水线

这里我们以 Intel 发明的 X86结构的 CPU 为例来大致讲述下 CPU 流水线技术的演进。

CPU 在执行程序的时候依赖于很多寄存器，例如通用寄存器、段寄存器、索引寄存器等。此外还有一个很重要的寄存器：指令指针(IP)。指令指针寄存器是一个拥有特殊功能的指针。指令指针的功能是指向将要运行的下一条指令。

所有的X86处理器都按照相同的模式运行。首先，根据指令指针指向的地址取得下一条即将运行的指令并解析该指令（译码）。在译码完成后，会有一个指令的执行阶段。有些指令用来从内存读取数据或者向内存写数据，有些指令用来执行计算或者比较等工作。当指令执行完成后，这条指令会通过退出(retire)阶段并将指令指针修改为下一条指令。

译码，执行和退出的分阶段模式组成了X86处理器指令执行的基本模式。从最初的8086处理器到新的酷睿i7处理器都基本遵循了这样的过程。

1989年 i486引入了五级流水线模式，分别是：取指(Fetch)，译码(D1, main decode)，转址(D2, translate)，执行(EX, execute)，写回(WB)。之前的三级模式，并不是流水线，每一条指令必须等待前一条指令执行完退出之后才能继续执行。而这种新引入的五级流水线模式，可以同时运行多条指令，每一级流水线在同一时刻都运行着不同的指令。这个设计使得i486比同频率的386处理器性能提升了不止一倍。五级流水线中的取指阶段(F)将指令从指令缓存中取出；第二级为译码阶段(D1)，将取出的指令翻译为具体的功能操作；第三级为转址阶段(D2)，用来将内存地址和偏移进行转换；第四级为执行阶段(EX)，指令在该阶段真正执行运算；第五级为退出阶段(WB)，运算的结果被写回寄存器或者内存。由于处理器同时运行了多条指令，大大提升了程序运行的性能。

image-20180820190943347

流水线化通过同时执行一系列操作增加了吞吐量(throughput)，但是她并没有减少延迟，即并没有减少一条指令从执行开始到执行结束的时间，仍要等到这一系列指令完成。实际上,流水线化由于将一条指令拆分成了几个步骤从而可能会增加延迟。

CPU 分支猜测

流水线技术的主要目的就是通过重叠连续指令的步骤来提高吞吐量从而获得性能，要做到这一点，就必须能够实现确定要执行指令的序列和先后顺序，这样才能使流水线中充满了待执行的指令。当处理器遇到分支条件跳转时，通常不能确定执行那个分支，因此处理器采用分支预测器来猜测每条跳转指令是否会执行。如果猜测比较可靠，那么流水线中就会充满指令。但是，如果对跳转的指令猜测错误，那么就要要求处理器丢掉它这个跳转指令后的所有已做的操作，然后再开始用从正确位置处起始的指令去填充流水线，可以看到这种预测错误会导致很严重的性能惩罚，会导致大约20-40个时钟周期的浪费，从而导致性能的严重下降。

一个很直观的说明 CPU 的分支预测器的例子是 stackoverflow 上的提问： Why is processing a sorted array faster than an unsorted array?

一段排序和未排序过的代码执行速度差别很大，具体代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
    // generate data
    const unsigned arraySize = 32768;
    int data[arraySize];
    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;
    
    //排序这行不注释掉下面的for循环会快得多
    std::sort(data, data + arraySize); 
    
    // test
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i) {
        // primary loop
        for (unsigned c = 0; c < arraySize; ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

我在我的 Mac 上运行的结果分别是

1
2
3
# 未排序
21.3109
sum = 312426300000
1
2
3
# 排序后
6.30532
sum = 312426300000

这里影响代码执行的主要片段是

1
2
if (data[c] >= 128)
    sum += data[c];

对于这段分支代码的执行，CPU 会启用分支预测(branch prediction)，排序和未排序的不同正是分支预测是否有大概率命中。对于命中的情况，CPU 指令可以一路顺畅的执行；而对于预测失败的情况，处理器要flush掉pipelines，回滚到之前的分支，然后重新热启动，选择另一条路径，这里的性能损失非常大。

那么一般怎么做分支预测呢？答案就是根据历史结果来做决定。对于排序的情况，很容易根据历史结果做出决策:

1
2
3
4
5
6
7
T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

而如果未排序的数组，则其取到的结果完全随机，分支预测基本无效

1
2
3
4
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

代码优化

上面说的 CPU 分支预测是属于硬件层面，其实从上层的软件或者程序员角度也是可以协助做好分支预测的。还是回到我们最开始提到的__builtin_expect 宏，示例代码反汇编得到的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.LC1:
    .string "Hula!"
.LC2:
    .string "Woo~"
 
    call    __isoc99_scanf
    movl    28(%esp), %eax
    testl   %eax, %eax
    je  .L2
    movl    $.LC1, (%esp)
    call    puts
.L3:
    xorl    %eax, %eax
    leave
    ret
.L2:
    movl    $.LC2, (%esp)
    call    puts
    jmp .L3

对于使用了 likely 的分支，其指令将更靠近 testl 分支判断，CPU 在执行分支判断指令的同时，将预先取出后续指令进行执行，而另一个分支指令则需要进行跳转(je .L2)。其本质是优化 CPU 的指令顺序，提高流水线的执行效率。

此外，编写代码时，我们也要注意分支的先后顺序，尽量将概率大的分支放在前面，尽量合并分支，尽量使用排序后的数据来判断，适当使用 goto 和 do while 来优化代码组织等。

参考资料

CPU流水线的探秘之旅

深入理解CPU的分支预测(Branch Prediction)模型

如何在 C++ 代码中提示编译器某个分支的执行概率高？