分支预测：赌对了省时间
分支预测：赌对了省时间
高速公路上，前方路口要么向左要么向右。你开车开到路口才看到指示牌，这时候你已经在路口了，还好只是减速一下再拐弯。但如果你是在时速 200 公里的赛车上——你必须提前几百米就决定转向，否则来不及。猜对了，全速通过；猜错了，急刹车、掉头，损失十几秒。
CPU 面临完全相同的困境：流水线很深（20+ 级），取指在解码之前，解码在执行之前。当一条分支指令（if/while/for）进入流水线，CPU 要等很多周期才知道该走哪条路。在等待期间，CPU 只有两个选择：停下来等（浪费流水线），或者猜一个方向继续执行。聪明的 CPU 选择猜——而且猜得极其准。
Level 1：建立直觉
分支预测的必要性
假设 CPU 有 20 级流水线，每级 1 个周期。一条分支指令在第 5 级才能确定跳转目标，在第 10 级才确定是否跳转（条件判断）。
不预测（停流水）：
取指→预解码→解码→...→条件判断→取指→...
├── 分支指令进入：10个周期后才知道结果
└── 在这10个周期里，后续指令全部暂停
→ 损失 10 个周期（= 10 个指令的机会成本）
预测（推测执行）：
取指→预解码→解码→...→条件判断→取指→... （继续执行预测路径）
├── 预测正确：0周期损失
└── 预测错误：10周期惩罚（清空流水线，重新取正确路径）
现代 CPU 分支预测准确率 95-99%，所以：
期望损失 = 错误率 × 惩罚周期
= 2% × 15周期
= 0.3 周期/分支
远好于不预测的 15 周期/分支（条件判断需要多级才能确定）
最简单的预测器：静态预测
静态预测：不看历史，用固定规则：
规则1：总是预测"不跳转"（顺序执行）
→ 适合：大部分 if 条件不满足的场景
规则2：向后跳转总是预测"跳转"（循环大概率会继续）
向前跳转总是预测"不跳转"
→ 准确率约 65%，比乱猜好
早期 CPU（80486 等）就用这种方式。
动态预测：记住历史
动态预测：根据这条分支指令的历史行为来预测：
分支历史表（BHT / PHT）：
每个分支指令地址对应一个 2-bit 计数器
11 → 强跳转（预测跳转）
10 → 弱跳转（预测跳转）
01 → 弱不跳转（预测不跳转）
00 → 强不跳转（预测不跳转）
实际跳转 → 计数器+1（饱和于11）
实际不跳转 → 计数器-1（饱和于00）
典型循环 "for i in 1..100":
T T T T T T T T ... T N
1 1 1 1 1 1 1 1 ... 1 0 ← 结果序列（T=跳转，N=不跳转）
2-bit 计数器变化：
10 → 11 → 11 → 11 → ... 11 → 10 → 01
准确率 98/100 = 98%（只有循环结束的那次预测错）
分支惩罚的量化影响
一个实际程序里分支指令的频率大约是每 5-7 条指令出现一次。以每 6 条出现一次、错误率 2%、惩罚 15 周期来算：
不含分支时 IPC = 4（超标量 CPU）
实际 IPC ≈ 4 / (1 + 分支频率 × 错误率 × 惩罚)
≈ 4 / (1 + 0.167 × 0.02 × 15)
≈ 4 / 1.05
≈ 3.81
如果错误率升到 20%（难以预测的分支）：
实际 IPC ≈ 4 / (1 + 0.167 × 0.20 × 15)
≈ 4 / 1.5
≈ 2.67（相当于损失了 1/3 的性能）
这就是为什么分支密集、随机分支多的代码往往跑得格外慢。
Level 2：原理剖析
分支目标缓冲（BTB）
分支预测要回答两个问题：
- 这条指令是分支吗？（PC 还没解码呢！）
- 如果是分支，跳到哪里？（跳转目标还没算出来）
**BTB（Branch Target Buffer）**缓存了"这个 PC 之前跳到了哪里"：
BTB 结构（类似 cache）：
PC 的低位 → BTB 索引
→ {预测跳转?，预测目标地址}
取指时就查 BTB（不等解码）：
→ 命中 + 预测跳转 → 立刻从预测目标地址取指
→ 命中 + 预测不跳转 → 继续顺序取指
→ 未命中 → 继续顺序取指（待解码后更新 BTB）
对于间接跳转（跳转目标在寄存器里，如虚函数调用）：
// 虚函数调用：跳转目标是运行时确定的
animal->speak(); // 汇编：call [rax]（rax = vtable 中的函数指针）
CPU 用 **间接分支预测器（IBP）**或 虚函数调用缓存（VPC） 预测间接跳转目标。
TAGE 预测器：顶级算法
现代 CPU（Intel Haswell+、AMD Zen+）用的是 TAGE（TAgged GEometric history length predictor）：
TAGE 结构：
一个基础预测器 T0（2-bit 计数器数组）
+ 多个有历史记录的表 T1, T2, T3, T4
T1: 使用最近 5 条分支的历史（2^5=32种模式）
T2: 使用最近 11 条分支的历史（2^11 = 2048种模式）
T3: 使用最近 23 条分支的历史
T4: 使用最近 47 条分支的历史
历史长度按几何级数增长
访问时：同时查所有表，选用历史最长的那个命中的预测
→ 捕捉复杂的长程依赖关系（如：当最近 20 次分支满足某种模式时，这次会怎样）
TAGE 能识别极其复杂的分支模式。例如，代码每隔 17 次循环触发一次特殊分支，TAGE 可以学到这个规律并预测正确。
实际数据（SPEC CPU2017 基准测试）：
- 2-bit 计数器：约 80-85% 准确率
- 现代 TAGE 预测器：约 95-99% 准确率
循环预测器
专门处理循环的特殊预测器：
循环预测器记录：
[PC] → {循环次数, 当前计数}
for (int i = 0; i < 100; i++) { ... }
第一次进入循环：开始计数
循环98次后：预测器知道"还要再循环一次"
循环99次后：预测器知道"下次会退出"→ 预测"不跳转"
精确预测100次循环，只有第一次进入时可能预测错。
返回地址预测（RAS）
函数调用（call）和返回（ret）是特殊的分支：
// 调用：目标地址固定（call 指令中编码了）
// 返回：目标地址是"之前 call 的下一条指令"
C 代码：
A() { B(); /* 这里是返回地址 */ C(); }
B() { ... return; }
RAS（Return Address Stack）：
调用 A 时：RAS 压入"A 的下一条指令"
调用 B 时：RAS 压入"B 的下一条指令"
B 返回时：RAS 弹出"B 的下一条指令"→ 预测正确！
A 返回时：RAS 弹出"A 的下一条指令"→ 预测正确！
RAS 通常有 16-64 个条目，深度递归可能溢出（超出的返回地址用 BTB 预测）。RAS 的准确率几乎是 100%（只有溢出时才失效）。
分支预测失误的汇编级分析
理解分支预测失误需要看汇编层面：
// 源代码
int sum = 0;
for (int i = 0; i < N; i++) {
if (arr[i] > 0) sum += arr[i];
}
; x86-64 汇编（gcc -O2 生成）
; rsi = arr, rcx = N, eax = sum
xor eax, eax ; sum = 0
xor ecx, ecx ; i = 0
.loop:
mov edx, [rsi + rcx*4] ; edx = arr[i]
test edx, edx ; 测试 edx > 0
jle .skip ; 条件跳转（这里是分支预测点）
add eax, edx ; sum += arr[i]
.skip:
inc ecx ; i++
cmp ecx, rdi ; i < N?
jl .loop ; 循环回跳（高度可预测）
; .skip 处的 jle：如果 arr[i] 是随机正负混合，预测准确率约 50%
; .loop 处的 jl：循环 N-1 次跳转，1次退出，准确率约 (N-1)/N ≈ 100%
两条分支的预测难度差距很大。理解哪些是"热"分支（执行频繁）以及它们的可预测性，是优化的关键。
Level 3 · 规范怎么定义的（资深）
分支预测的学术理论与硬件实现
分支预测的理论基础可以追溯到 Jim Smith 1981 年的论文 "A Study of Branch Prediction Strategies"，该论文首次系统地比较了静态预测和动态预测的效果。两位饱和计数器（2-bit saturating counter）是最基本的动态预测器，其状态机有四个状态：强不跳转、弱不跳转、弱跳转、强跳转——需要连续两次预测错误才会切换预测方向，避免了单次异常导致的频繁翻转。
现代 CPU 使用的 TAGE 预测器（TAgged GEometric history length predictor）由 André Seznec 在 2006 年的论文中提出，并在 Championship Branch Prediction（CBP）竞赛中多次获胜。TAGE 使用多个不同历史长度（几何级增长：如 5、10、20、40、80、160 个分支的历史）的预测表，每次预测时查找匹配最长历史的表项。这种"长短历史兼顾"的设计让 TAGE 在各种分支模式上都表现优异——学术界测量的预测准确率通常在 95-98%。
间接分支预测（用于 switch 语句、虚函数调用、函数指针）使用 BTB（Branch Target Buffer） 和 ITTAGE（Indirect Target TAGE）。间接分支的目标地址不固定，预测难度远高于条件分支。Spectre v2 攻击正是利用了间接分支预测器可以被"训练"到攻击者指定的目标地址，从而在推测执行期间跳转到泄露敏感数据的 gadget。
Level 4 · 边界与陷阱（所有人）
陷阱 1：排序后的数组遍历比未排序快——不是因为 Cache
经典面试题：对一个整数数组做条件求和（if value > 128 then sum += value），排序后的数组比未排序的快 5-6 倍。直觉上可能以为是 Cache 友好性的差异，但实际上数组遍历都是顺序访问，Cache 行为完全相同。真正原因是分支预测：排序后，条件分支呈现"前半段全不跳转、后半段全跳转"的规律模式，预测器几乎 100% 准确；未排序时，跳转与否是随机的，预测准确率约 50%，每次错误预测浪费 15-20 个周期。用无分支写法（如 sum += (value > 128) * value 或使用 CMOV 指令）可以完全消除这个差异。
陷阱 2：虚函数调用的隐藏成本是分支预测失败
C++ 的虚函数调用（obj->method()）编译为间接跳转——目标地址存在虚函数表（vtable）中，只有运行时才知道。如果一个循环中处理的对象类型频繁变化（如遍历一个包含多种派生类的 vector<Base*>），间接分支预测器会频繁失败。在 Intel CPU 上，每次间接分支预测失败的惩罚约 20-25 个周期。这就是为什么游戏引擎和高性能代码倾向于使用"数据导向设计"（Data-Oriented Design）——将同类型的对象聚集在一起处理，使间接分支预测器能学习到稳定的模式。
陷阱 3：分支预测器的状态是全局共享的——安全隐患
同一物理核心上运行的不同进程（或同一进程的不同超线程）共享分支预测器的状态（BTB、PHT 等）。Spectre v2 攻击正是利用这一点：攻击者进程先"训练"共享的间接分支预测器，让它学会跳转到攻击者选定的目标地址；然后受害者进程执行间接跳转时，预测器会将其错误引导到攻击者的 gadget，在推测执行期间泄露受害者的数据。缓解措施（IBRS、STIBP、retpoline）通过限制预测器的跨上下文影响来阻止这种攻击，但代价是间接跳转的性能下降——特别是在解释器（如 CPython、JVM）中，每条字节码的 dispatch 都是间接跳转，受影响尤为严重。