跳到主内容
快讯直播
AI智模界
AI 词典

分支预测:CPU 猜错一次,就要空等十几个周期

一句话定义:分支预测(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 类侧信道问题的物理基础,这也是现代浏览器和内核默认开启相关缓解措施的原因。

AI 生成本文由 AI 基于公开信息自动生成,仅供参考。