处理器中的分支预测器

为什么需要分支预测？

CPU 的流水线（Pipeline）需要连续不断地执行指令。但当遇到 if-else、循环 这样的分支语句时，CPU 不知道下一步该执行哪个分支（就像走到岔路口不知道该左转还是右转）。如果等条件计算完再决定，会浪费几个时钟周期。

分支预测器的作用：猜一猜哪个分支更可能被执行，提前把指令加载到流水线中。如果猜对了，性能提升；猜错了就清空流水线（惩罚约 10-20 个周期）。

常见的分支预测方法

静态预测（Simple Static Prediction）

固定策略：比如总是预测「不跳转」，或者让编译器提示大概率路径（如 C++ 的 [[likely]]）。
例子：

if (condition) { // 静态预测：假设 condition 通常为 false
    // 冷门路径
}

动态预测（Dynamic Prediction）

局部历史表（Branch History Table, BHT）：记录最近几次该分支的结果（比如用 2-bit 状态机：00→01→11→10）。
例子：一个循环的退出条件在最后一次迭代前总是 true。
全局历史表（GShare）：考虑其他分支的历史记录（比如多个 if 之间有相关性）。
锦标赛预测器（Tournament Predictor）：混合多种策略，动态选择最优。

编译器中的分支优化

编译器虽然没有硬件级的预测器，但可以通过以下方法帮助 CPU：

(1) 概率提示

C++20 的 [[likely]]/[[unlikely]]：

if (x > 0) [[likely]] { 
    // 编译器会优先优化这条路径
}

(2) 代码重排

将更可能执行的分支放在前面，减少跳转：

// Bad: 
if (rare_condition) {
    handle_error();
} else {
    normal_case();
}

// Good: 
if (!rare_condition) {
    normal_case();
} else {
    handle_error();
}

(3) 循环优化

循环展开（Loop Unrolling）：减少分支次数。

for (int i = 0; i < N; i += 4) { // N=100 → i=0,4,8,...96
    sum += arr[i]; sum += arr[i+1]; sum += arr[i+2]; sum += arr[i+3];
}

条件替换为算术运算：避免分支。

// Bad: if-else 
int x = (a > b) ? a : b;

// Good: CMOV指令或无分支写法
int x = a ^ ((a ^ b) & -(a > b));

实际例子对比

未优化的代码（频繁分支惩罚）

for (int i = 0; i < N; i++) {
    if (data[i] > threshold) { // CPU可能频繁预测错误
        count++;
    }
}

优化后（减少分支）

for (int i = 0; i < N; i++) {
    count += (data[i] > threshold); // true=1, false=0
}

总结

硬件和软件协作的核心目标：尽量减少流水线停顿！