branch-prediction-and-speculation

分支预测与推测执行

目的

说明现代 CPU 如何预测分支、推测执行、在预测错误时恢复，以及推测执行为何会产生侧信道（Spectre/Meltdown），将性能调优与注重安全的底层编码联系起来。

适用场景

• 热循环中的多分支代码性能不如预期
• 评估 likely/unlikely 或无分支重构
• 理解内核的 retpoline、IBRS 及类似缓解措施
• 围绕依赖机密信息的分支进行安全编码

工作流

1. 分支预测器基础

Fetch sees conditional branch
├── Predict direction (taken / not-taken)
├── Speculatively execute predicted path
└── On resolve:
    ├── Correct → commit, ~0 penalty (deep pipelines still cost on mispredict)
    └── Wrong → squash, refill from correct PC (10–20+ cycles typical)

模式：向后分支通常预测为跳转（循环）；向前分支预测为不跳转。

2. 性能模式

/* Predictable — tight loop backward branch */
for (int i = 0; i < n; i++)
    sum += a[i];

/* Unpredictable — data-dependent */
if (data[i] > threshold)  /* hard to predict */
    rare_path();

技巧：使用无分支的 cmov/select、查找表、对数据排序以减少分支，以及拆分热路径和冷路径。

/* Branchless min (integer) */
int m = a < b ? a : b;  /* compiler may lower to cmov */

3. 编译器提示（谨慎使用）

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

if (unlikely(ptr == NULL))
    return -EINVAL;

使用 perf 进行测量——在现代预测器上，提示并非万能。

4. 推测执行与侧信道

CPU 可能会在分支结果确定之前执行指令。如果推测执行的路径访问了依赖机密信息的内存，缓存状态就可能泄露信息（Spectre 变体 1）。

缓解措施（概述）：

• 内核：retpoline、IBRS/IBPB、STIBP（参见内核 cpu_show_mitigations）
• 编译器：推测加载加固（Clang 中的 -mspeculative-load-hardening）
• 代码：常量时间加密——不使用依赖机密信息的分支或索引

Meltdown（Intel）：用户态从内核映射中读取数据——通过 KPTI（独立页表）修复。

5. 测量

perf stat -e branches,branch-misses ./app

branch-misses 比率较高 → 排查热分支。

6. Agent 用法

/branch-prediction-and-speculation Make this comparison function constant-time against Spectre-style leakage

常见问题

症状	原因	修复方法
循环比预期慢	退出分支预测错误	展开迭代；使用无分支的尾部处理
likely 没有帮助	预测器本来就预测得很好	先进行性能分析
加密中泄露机密信息	对机密字节进行分支判断	使用常量时间算法
缓解措施导致性能回退	KPTI/retpoline 开销	接受开销或隔离机密信息
“无分支”反而更慢	CMOV 仍会执行两边的操作	在目标 CPU 上进行基准测试

相关技能

• skills/computer-architecture/cpu-pipelines-and-hazards — 控制冒险
• skills/security/kernel-security — KPTI、CET、推测执行缓解措施
• skills/low-level-programming/cpu-cache-opt — 缓存时序信道
• skills/profilers/hardware-counters — branch-misses 事件
• skills/runtimes/binary-hardening — 用户空间加固的交集