一句话定义:分支预测(Branch Prediction)是 CPU 内部的一个硬件小机制,它在 if 的条件还没算出来之前,就先猜程序会走哪条分支,然后沿着猜的那条路继续干活。
为什么需要它:CPU 停不下来
现代 CPU 采用流水线(Pipeline)工作,像一条不能停的装配线:取指、译码、执行、访存、写回,每一站只负责一小步,同一时刻线上挤着几十条指令。问题在于,遇到条件跳转时,CPU 根本不知道下一条该从哪儿取。如果严格等条件算完再取指,就等于让整条装配线停下来等待,代价极大。
于是 CPU 采取分支预测:根据这段代码的历史表现,先猜“这次跳不跳”,然后直接沿着猜的方向取指、译码,甚至提前执行。猜对时,流水线全程不中断,几乎零成本;猜错时,就得把已经进入流水线、做了一半的工作全部作废(Flush),再从正确地址重新取指。
猜错的代价有多大
浪费的周期数,大致等于“分支指令在流水线中被真正解析出来”之前已经走过的级数。主流处理器的流水线有十几到二十几级,所以一次预测失败的惩罚通常在十几个到二十几个周期量级,具体取决于微架构,以厂商文档为准。这种惩罚听起来不大,但要乘以分支出现的频率:热点循环里可能每几条指令就有一个分支,几十亿次累加下来,就相当可观。
现代预测器(结合历史记录、全局分支历史等)在常规代码上命中率很高,通常在 95% 以上。麻烦的是剩下的那部分,尤其是结果真正随机的分支。
排序为什么能让代码变快
经典例子是这个循环:
```c
for (i = 0; i < n; i++)
if (data[i] >= 128) sum += data[i];
```
如果 data 是随机数组,这个条件有一半概率为真、一半为假,没有任何规律可循,预测器只能靠猜,错误率接近 50%。但把 data 先排序再跑同一个循环:前半段条件全为假,后半段全为真,分支变得高度可预测,预测器几乎不犯错。同一份代码、同样多的数据,只因为内存里的顺序不同,耗时可能相差好几倍。
有两个重要补充:一是编译器如果把分支改写成条件传送(CMOV)或做了向量化,这个差距会消失,因为它根本不再“跳”;二是这也是“数据布局比算法微调更值钱”的典型例证。
与相邻概念的区别
| 概念 | 赌的是什么 | 赌错/赌输的后果 |
|---|---|---|
| 分支预测 | 这次跳不跳、跳去哪儿 | 清空流水线,浪费十几个周期 |
| 推测执行(Speculative Execution) | 更大范围的“先做再说”,分支预测是它的一种 | 同上,回滚 |
| 缓存(Cache) | 这块数据/指令还会不会再用到 | 去内存取,浪费几十到几百周期 |
| 乱序执行(Out-of-Order) | 后面的指令能不能先做 | 不涉及赌,只是调度 |
对从业者的实际意义
写热点代码时,问一句“这个分支可预测吗”:把输入排序、分桶、先过滤再进循环,往往比换算法更快。能无分支就无分支(查表、位运算、min/max)。做 AI 系统时同理:数据预处理、tokenizer、量化 kernel 里的分支常是瓶颈;而 GPU 上根本没有分支预测,一个 warp 内部分叉要两条路都走一遍(Warp Divergence),所以 GPU 代码更强调“按同样路径组织数据”。另外,分支预测加推测执行正是 Spectre 类侧信道问题的物理基础,这也是现代浏览器和内核默认开启相关缓解措施的原因。
