0.简介

在现代的CPU架构中，影响性能的两大很关键的要素就是cache和分支预测（指令级并行），cache相关在前面文章介绍过，分支预测将在本文进行说明。主要从分支预测的概念，原理，优化技巧和实际案例等方面进行分析。

1.概念

1.1 什么是分支预测

在现代CPU中指令流水线技术（取指、解码、执行、访存、写回）允许处理器同时去执行多条指令的不同阶段。但遇到条件分支时，CPU需要预测分支走向以避免流水线停顿，错误的预测需要回撤，会导致性能下降，所以在高性能的计算领域，我们需要对其进行有效控制。

1.2 分支预测类型

1）静态分支预测：静态分支预测是指的编译器或者CPU总是采取固定的策略（比如‘总是预测不跳转’），其适用于较为简单的场景，准确率较低。

2）动态分支预测：CPU基于之前执行的分支信息对于当前正在运行中的程序做的预测，最为简单的就是1-bit动态预测（如果上次跳转，本次也跳转，上次没有跳转，本次也不跳转），当然现代CPU有着更为良好的预测算法。

1.3 分支预测错误的代价

分支预测错误代价可以通过一个实际的经典例子来看，初始代码如下：

#include <algorithm>
#include <ctime>
#include <iostream>
int main() {
    const unsigned ARRAY_SIZE = 50000;
    int data[ARRAY_SIZE];
    const unsigned DATA_STRIDE = 256;
    for (unsigned c = 0; c < ARRAY_SIZE; ++c) data[c] = std::rand() % DATA_STRIDE;
    std::sort(data, data + ARRAY_SIZE);
    {  // 测试部分
        clock_t start = clock();
        long long sum = 0;
        for (unsigned i = 0; i < 100000; ++i) {
            for (unsigned c = 0; c < ARRAY_SIZE; ++c) {
                if (data[c] >= 128) sum += data[c];
            }
        }
        double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
        std::cout << elapsedTime << "\n";
        std::cout << "sum = " << sum << "\n";
    }
    return 0;
}

直接编译执行结果如下：

如果注释掉sort排序语句，结果如下：

其原因就是sort后可以大幅提升分支预测成功率，从而提上效率。

2.原理

通过上面介绍可以了解分支预测主要分为静态分支预测和动态分支预测，静态分支预测较为简单，本节主要描述动态分支预测，我们从较为经典的饱和计数方式来看，当然，现代的cpu都进行了更多的优化。

饱和计数其主要依靠两个表，即分支历史表（Branch History Table）和目标缓冲器（Branch-Target Buffer）。

1）分支历史表：记录历史信息首先应该考虑的是使用多少位来进行记录，根据研究结果表明，两位的分支预测性能和n（n>2）位的分支预测性能差不多，两位分支预测的状态转换如下图；存储的大小确定了接下来就要看存储的实现，常见的实现方式又和分支指令一起存储到指令cache，取址阶段读出，另外一种就是使用专门的硬件去实现。

2）目标缓冲器：目标缓冲器的目标是将分支开销进一步降低，其通过记录分支成功的分支指令地址和分支目标地址，让其下次可以直接获取地址，两者结合后整体流程如下：

3.优化技巧

3.1 减少分支预测

1）使用查表法替代 if-else 或 switch，这个比较常用，像代码中大量if-else都可以使用这种方式，不仅优化性能，更能让代码简洁。

// 多个分支
int getValue(int type) {
    if (type == 1) return 10;
    else if (type == 2) return 20;
    else return 0;
}
// 查表
int getValue(int type) {
    static const int table[] = {0, 10, 20};
    return table[type];
}

2）使用位运算替代简单条件，要求高性能运算时使用，比如取绝对值。

// 低效：分支
int abs(int x) {
    return (x < 0) ? -x : x;
}
// 高效：无分支（仅适用于整数）
int abs(int x) {
    int mask = x >> (sizeof(int) * 8 - 1); // 取符号位
    return (x + mask) ^ mask;
}

3.2 提高分支预测命中率

1）确保分支可预测（排序数据），可以看1.3节的例子。

2）使用 likely/unlikely 提示编译器。

#define unlikely(x)  (__builtin_expect(!!(x), 0))
#define likely(x)    (__builtin_expect(!!(x), 1))
struct Data
{
    int m_oData;
};
int getId(Data* pData)
{
    if(unlikely(nullptr == pData))
    {
        return -1;
    }
    return pData->m_oData;
}

3.3 使用无分支（Branchless）编程

1）条件移动（CMOV）替代分支:其是通过将条件判断转化为数据依赖来消除分支预测，分为编译器可能优化和强制优化（直接使用汇编）。

2）掩码运算，和位运算类似，可以参考下面例子。

// 计算绝对值（无分支）
float abs(float x) {
    uint32_t mask = 0x7FFFFFFF;
    uint32_t bits;
    memcpy(&bits, &x, sizeof(float));  // 避免类型双关UB
    bits &= mask;
    memcpy(&x, &bits, sizeof(float));
    return x;
}