第5章分支预测与优化

课程目录第5章分支预测与优化

分支预测与优化：让CPU少走弯路

分支预测，说白了就是CPU在猜你下一步要往哪走。你想想看，流水线里指令哗哗地流，突然遇到一个if-else，CPU得停下来等结果——这多浪费啊。所以现代CPU干脆先猜一个方向，赌一把。

我刚开始做性能优化时，压根没把分支当回事。直到有一次，一个排序算法在特定数据集上慢得离谱，用perf一查，分支预测失败率高达30%。嗯，从那以后我再也不敢小看分支了。

分支预测的工作原理

CPU内部有个分支目标缓冲器（BTB），记录着每条分支指令的历史行为。比如一个循环，前99次都走true分支，BTB就记住了这个模式。第100次时，CPU直接预测走true，流水线继续推进。

但如果你写了个随机跳转的分支，比如：

if (rand() % 2) {
    // 分支A
} else {
    // 分支B
}

CPU就彻底懵了。预测正确率只有50%，跟抛硬币没区别。每次预测失败，流水线都要冲刷掉已经预取的指令，重新加载——这代价可不小，通常要浪费10-20个时钟周期。

核心要点：分支预测失败的成本，远高于分支本身。优化的目标不是消除分支，而是让分支变得可预测。

likely/unlikely宏：给编译器递小抄

GCC和Clang提供了两个宏：likely()和unlikely()。它们告诉编译器哪个分支更常走，编译器会据此调整代码布局。

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

// 使用示例
if (unlikely(ptr == nullptr)) {
    // 错误处理，很少执行
    return -1;
}
// 正常路径，经常执行
return ptr->value;

我个人习惯在错误检查、边界条件上用unlikely()，在正常路径上用likely()。这样编译器会把热路径的代码放在一起，冷路径的代码挪到远处，提高指令缓存的命中率。

小技巧：我在项目中遇到过，用unlikely()标记一个几乎从不触发的错误分支后，热点函数的性能提升了约5%。虽然不多，但零成本改动，何乐而不为？

减少分支的常用技巧

有些分支是可以直接消除的。我总结了几个实战中常用的方法：

1. 逻辑运算替代分支

// 分支版本
int abs_val = (x < 0) ? -x : x;

// 无分支版本
int abs_val = (x ^ (x >> 31)) - (x >> 31);

这个技巧利用了补码的特性。虽然可读性差了点，但在热点路径上值得一试。

2. 条件移动指令

现代CPU支持条件移动指令（如x86的CMOV），它不改变控制流，只是根据条件选择值：

// 编译器可能生成分支
int min = (a < b) ? a : b;

// 强制使用条件移动（GCC扩展）
int min = a < b ? a : b;  // 加个volatile有时能影响编译器决策

我曾经在数据库的索引查找函数里，把几个if-else改成了三元运算符+条件移动，分支预测失败率从12%降到了2%以下。

3. 循环展开与分支消除

// 有分支的循环
for (int i = 0; i < n; ++i) {
    if (i < 4) {
        // 特殊处理
    } else {
        // 正常处理
    }
}

// 展开后无分支
for (int i = 0; i < 4 && i < n; ++i) {
    // 特殊处理
}
for (int i = 4; i < n; ++i) {
    // 正常处理
}

注意：不要盲目消除所有分支。有些分支消除后代码变得难以维护，而且编译器可能已经帮你优化了。先测量，再动手。

查表法替代分支：空间换时间

查表法是我最喜欢的优化手段之一。说白了，就是把条件判断变成数组索引。

// 分支版本
char to_upper(char c) {
    if (c >= 'a' && c <= 'z') {
        return c - 32;
    }
    return c;
}

// 查表版本
static const char upper_table[256] = {
    // 0-96: 原值
    // 97-122: 减32
    // 123-255: 原值
    // 具体初始化略...
};
char to_upper(char c) {
    return upper_table[(unsigned char)c];
}

查表法特别适合以下场景：

输入范围有限（如字节、枚举值）
分支逻辑复杂，但结果可预计算
对延迟敏感，能接受额外内存访问

我记得在做一个网络协议解析器时，需要根据报文类型做几十种不同的处理。最初是一串if-else，后来改成函数指针表，性能提升了将近一倍。

知识体系总览

下面这张图概括了分支预测优化的核心思路：

实战建议

说了这么多，我最后给几条实在的建议：

先测量，再优化。用perf stat看分支预测失败率，低于5%就别折腾了。
优先保证可预测性。让数据有序（比如排序后遍历），比任何技巧都管用。
查表法虽好，但别滥用。表太大导致缓存miss，反而得不偿失。
编译器比你想象中聪明。先写清晰的代码，让编译器优化，不行再手动干预。

避坑指南：我曾经在一个热路径上用了查表法，结果表太大，每次查表都触发L2缓存miss，性能反而下降了。后来把表拆成两级，小表放热数据，大表放冷数据，才解决问题。记住：查表法不是银弹，要结合缓存层级来设计。

分支优化是个细活，需要你对CPU微架构有一定了解。但掌握了这些技巧，你写出来的代码就能让CPU跑得更顺畅——说白了，就是让硬件少做无用功。

📚 课程目录

分支预测与优化：让CPU少走弯路

分支预测的工作原理

likely/unlikely宏：给编译器递小抄

减少分支的常用技巧

1. 逻辑运算替代分支

2. 条件移动指令

3. 循环展开与分支消除

查表法替代分支：空间换时间

知识体系总览

实战建议