C 语言分支预测友好的代码
更新时间：2026-08-26。本文是
languages/c/主题专家层文档。CPU 里有个"预言家"叫分支预测器，它提前猜if走哪条路。猜对了流水线畅通，猜错了要冲刷流水线、推倒重来，代价几十个周期。本文用"排序后快 6 倍"的实测，讲清怎么写对分支预测器友好的代码。
本文要回答的问题
- 为什么"把数据排序后，同样的 if 判断快 6 倍"？
- 分支预测失败到底贵在哪？流水线冲刷是什么？
- 怎么写"无分支"的代码？
likely/unlikely有用吗？
一、实测：排序后快 6 倍
对 1 亿个随机整数，累加所有 < 128 的值：
c
for (int i = 0; i < N; i++)
if (a[i] < 128) sum += a[i];实测（gcc -O2，N=1 亿）：
text
随机数据（分支难预测）: 460 ms, sum=3175537176
排序数据（分支可预测）: 70 ms, sum=3175537176同样的代码、同样的结果（sum 一致），只是把数据排了序，快 6.5 倍！
二、为什么？分支预测器
2.1 流水线与分支
现代 CPU 是流水线执行——同一时刻有多条指令在"排队"处理。遇到 if 时，CPU 不知道走哪条路，但不能停（停下就浪费流水线），于是猜一条路先执行。
- 猜对了 → 流水线无缝衔接，零损失
- 猜错了 → 冲刷流水线（丢弃已做的一半工作），损失约 10-20 个周期
2.2 排序为什么有用
- 随机数据：
a[i] < 128的真假随机分布，预测器只有 50% 命中率，一半时间在冲刷流水线。 - 排序数据：前半段全
< 128（恒真）、后半段全>= 128（恒假），预测器能完美预测（几乎 100% 命中），几乎不冲刷。
三、无分支编程
既然分支预测失败这么贵，能不能去掉分支？用条件移动（cmov）等技巧：
c
// 有分支
if (a < b) min = a; else min = b;
// 无分支（编译器可能生成 cmov）
min = (a < b) ? a : b;对于数据随机、分支难预测的场景，无分支写法能避免流水线冲刷：
c
// 分支版（随机数据慢）
if (x > 0) y += x;
// 无分支版（用位运算/算术技巧）
int mask = (x > 0) ? -1 : 0; // 全 1 或全 0
y += x & mask;注意：无分支不是银弹——它牺牲了可读性，且对可预测的分支反而更慢（多算了无效工作）。只有确认"分支难预测且是热点"时才用。
四、likely / unlikely
GCC 提供 __builtin_expect，提示编译器"这个分支更可能走哪边"：
c
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(err)) { // 告诉编译器：err 通常为假
handle_error();
}作用：让编译器把"更可能走的分支"放在顺序路径（热路径），减少跳转、改善指令缓存。主要用于内核/热点代码，普通业务代码收益很小。
五、什么时候该关心分支预测
| 场景 | 是否值得优化 |
|---|---|
| 循环内、数据随机、判断频繁 | ✅ 重点优化 |
| 热点函数里的 if 链 | ✅ 考虑无分支 |
| 循环外的判断 | ❌ 无所谓 |
| 数据本身有序/可预测 | ❌ 分支预测已很好 |
先用 perf 剖析 定位 branch-misses 高、且是热点的分支，再考虑优化。
六、与本站主线衔接
- 分支预测器机制：动态分支预测、BTB、模式历史表，见 L4 分支预测。
- 流水线：乱序执行、流水线冲刷，见 L4 CPU 微架构。
- 缓存：排序还改善了数据局部性，见 缓存与 C 程序性能。
- perf 剖析：branch-misses 指标判读，见 perf 剖析 C 程序。
一句话总结
分支预测失败要冲刷流水线（损失十几周期），所以"排序后同样的 if 快 6.5 倍"；热点处难预测的分支可用无分支写法（cmov/位运算）或 likely/unlikely 优化，但先 perf 定位、别盲目优化。