CPU分支预测：代码里隐藏的性能瓶颈
分支预测决定紧凑循环的性能表现。本文解析CPU如何预测分支、误预测为何代价高昂，以及如何写出更快的代码。
James Whitfield
Stack Overflow上有一个非常有名的回答，浏览量超过300万次。问题是：为什么处理排序后的数组比处理无序数组更快？代码完全相同，都是一个带if语句的循环，唯一的区别是输入数组是否有序。有序版本快了6倍。背后的原因就是CPU分支预测，它揭示了现代计算中影响最深远的性能因素之一。
代码里的每个if语句、每个循环条件、每个switch分支，都是一条分支。CPU每秒要遇到数十亿条这样的分支，并且必须在真正得出结果之前预测每一条的走向。预测正确时，执行就能全速进行；预测错误时，CPU会丢弃10到20个周期的工作，然后从头开始。理解这套机制，会改变你对性能关键代码的看法。
为什么CPU需要预测
现代CPU采用流水线设计：它不会等一条指令执行完再开始下一条。典型的CPU流水线有12到20级。在一条指令执行的同时，接下来的大约15条指令已经在被取指、译码和准备中。正是这种流水线让CPU能够在每条指令都需要多个周期才能完成的情况下，大致每个时钟周期执行一条指令。
但遇到分支（if x > 0）时，问题就来了。后续指令取决于分支是否跳转。比较结果需要在流水线中逐级传递，CPU要过好几个周期才能知道答案。它只有两个选择：暂停流水线等待（白白浪费15个以上的周期），或者猜测分支方向并继续工作。
CPU总是选择猜。分支预测器做出预测，CPU随即沿着预测路径取指和执行。预测正确，就没有任何浪费；预测错误，CPU必须清空已错误执行的指令、丢弃它们的结果，然后从正确路径重新开始。这种“流水线清空”在现代x86 CPU上大约要耗费15到20个周期，相当于损失了15到20条指令的工作量。
分支预测器如何工作
现代分支预测器相当精巧。它们本质上是一种模式匹配硬件，能够从每条分支指令的历史记录中学习。
简单情况：有偏向的分支
很多分支都有明显的偏向，几乎总是朝同一个方向走。比如一个99.9%的情况下都会成功的错误检查，或者一个前999次为真、最后一次为假的循环条件。分支预测器很快就能学会这些模式，准确率接近完美。一条99%的情况都走同一方向的分支，误预测率最多也只有1%。
模式识别
现代预测器不止于追踪简单的偏向，它们还能识别重复出现的模式。如果一条分支的走向呈现“跳转-跳转-不跳转-跳转-跳转-不跳转……”这样的周期为3的规律，预测器就能学会并正确预测。现代Intel和AMD CPU所采用的TAGE（TAgged GEometric history length，带标签的几何历史长度）预测器，维护着多张不同历史长度的表，能够捕捉周期从2到数百的各种模式。
相关分支
最先进的预测器还能学习分支之间的相关性。如果分支A被跳转时，代码后面的分支B总是不跳转，预测器就能学到这种关系。这被称为“两级自适应预测”，它能处理这样的代码模式：
// These branches are correlated
if (x > 0) { // Branch A
y = x * 2;
}
// ... some code ...
if (x <= 0) { // Branch B — always opposite of Branch A
y = -x;
}
// The predictor learns: when A is taken, B is not taken, and vice versa
// Both branches are predicted with near-perfect accuracy揭开有序数组之谜
回到那个著名的Stack Overflow问题。代码大致是这样的：
int sum = 0;
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128) // This is the critical branch
sum += data[i];
}
// With SORTED data [0, 1, 2, ..., 127, 128, 129, ..., 255]:
// Branch pattern: NNNNNN...NNNTTTTTT...TTT
// First half: always NOT taken. Second half: always taken.
// Prediction accuracy: ~99.9% (only mispredicts at the transition)
// With UNSORTED data [random values 0-255]:
// Branch pattern: TNNTTNNTTTNNTNNT... (random)
// Prediction accuracy: ~50% (no pattern to learn)
// Every misprediction costs ~15 cycles对于有序数据，这个分支完全可预测：数组前半段始终不跳转，后半段始终跳转。预测器很快就能学会每个阶段，只会在唯一的转折点误预测一次。而对于随机数据，这个分支基本就是抛硬币，预测器的准确率最多只能达到约50%，一半的迭代都会因为流水线清空浪费15个周期。
以10万次迭代、约50%的误预测率计算，就是5万次误预测 × 15个周期 = 75万个浪费的周期。在3 GHz的CPU上，这大约是四分之一毫秒，对于这个简单循环来说，已经占了总运行时间的相当大一部分。
你的CPU能处理多少分支？
分支预测器的存储空间是有限的。它通过一种叫做分支目标缓冲器（BTB）的结构以及相关的历史表，来追踪有限数量的分支位置的历史。现代CPU能追踪数万个分支位置，但大型代码库可能会超出这个范围。
当两条不同的分支指令映射到预测器的同一个条目上时（因为BTB是通过指令地址的哈希值来索引的），它们会相互干扰彼此的预测。这在普通代码中很少见，但在超大函数中，或者当许多小函数各自包含分支时，就变得值得关注了。
Daniel Lemire发表过一些出色的研究，测量了不同CPU上分支预测器的容量。结果显示，现代Intel CPU（Alder Lake及之后的型号）能够有效预测历史深度约200条分支的分支，也就是说，预测当前分支时，预测器会考虑最近约200条分支的结果。AMD CPU的容量与之相近。ARM芯片的差异则更大，其中苹果M系列芯片的分支预测器尤其强劲。
编写对分支预测友好的代码
大多数代码中，分支预测并不重要。预测器已经足够好，而且分支也不在热点循环里。但当你优化性能关键路径（内层循环、数据处理流水线、解析器、编解码器）时，分支行为就可能主导运行时间。
用算术替代分支
最快的分支，就是不存在的分支。很多条件逻辑都可以改写为无分支的算术运算。
// Branching version:
int max_branch(int a, int b) {
if (a > b) return a;
return b;
}
// Branchless version (compiler often does this automatically):
int max_branchless(int a, int b) {
return a ^ ((a ^ b) & -(a < b));
}
// Conditional move — the compiler's favorite trick:
int max_cmov(int a, int b) {
// Most compilers will emit a CMOV instruction for this
return (a > b) ? a : b;
}
// Clamping with branches:
int clamp_branch(int x, int lo, int hi) {
if (x < lo) return lo;
if (x > hi) return hi;
return x;
}
// Clamping branchless:
int clamp_branchless(int x, int lo, int hi) {
// min(max(x, lo), hi)
int t = x > lo ? x : lo; // CMOV
return t < hi ? t : hi; // CMOV
}现代编译器通常很擅长把简单的条件语句转换为CMOV（条件移动）指令，从而完全避免分支。但它们并非总能做到，尤其是当分支有副作用，或者“then”路径开销很大的时候。在编译器没有生成最优代码的热点循环中，显式地编写无分支模式会有所帮助。
处理前先排序
如果你要用分支来过滤数据，先对数据排序可以让分支变得完全可预测。这听起来有悖直觉，排序本身有O(n log n)的开销，但对于大数据集，尤其是处理循环会执行很多次或者分支误预测代价很高的场景，排序的收益足以抵消成本。
使用查找表
复杂的条件逻辑（比如有很多分支的switch语句）可以用查表来替代。不再逐个比较，而是直接用索引访问数组。数组访问可能会导致缓存未命中，但这通常比一连串误预测的分支开销要小。
// Branch-heavy version:
char to_hex(int nibble) {
if (nibble < 10)
return '0' + nibble;
else
return 'a' + nibble - 10;
}
// Lookup table version (no branches):
static const char hex_table[] = "0123456789abcdef";
char to_hex_lut(int nibble) {
return hex_table[nibble];
}给编译器提示
GCC和Clang支持__builtin_expect，可以告诉编译器哪个分支方向更可能发生。它并不能直接控制CPU的分支预测器（预测器是在运行时学习的），但会影响编译器对代码的布局。把可能执行的路径放成直线型、不跳转的形式，由于指令缓存的影响，这样会更快。
// Tell the compiler that errors are unlikely
if (__builtin_expect(result == NULL, 0)) {
handle_error();
}
// C++20 provides cleaner syntax:
if (result == NULL) [[unlikely]] {
handle_error();
}
// Linux kernel defines macros for this:
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
if (unlikely(ptr == NULL)) {
panic("null pointer");
}测量分支行为
你可以直接利用硬件性能计数器来测量分支预测的表现。在Linux上，perf stat可以为任何程序给出误预测率。
# Measure branch prediction statistics
$ perf stat -e branches,branch-misses ./my_program
Performance counter stats for './my_program':
1,482,937,256 branches # 892.7M/sec
3,271,842 branch-misses # 0.22% of all branches
# 0.22% misprediction rate — excellent.
# Anything under 1% is good.
# Over 5% in a hot loop means branch prediction is hurting you.
# Over 10% means you should consider branchless alternatives.对于微基准测试，Google Benchmark等工具可以统计每次迭代的branch-misses，让你精确地了解某次代码改动是否改善了分支行为。相比包含了其他系统活动噪声的实际耗时，这种指标更具指导意义。
什么时候需要关注（以及什么时候不必）
分支预测优化只在一类范围不大、但很重要的代码中有意义：处理海量数据的紧凑内层循环。解析器、压缩器、图像处理、数值计算、数据库查询执行，这些场景中，分支行为往往占据主导。
对于其他大部分代码（业务逻辑、API处理函数、CRUD操作），分支预测根本无关紧要。Web服务器请求路由中的分支并不是你的瓶颈。不要把每个HTTP请求只执行一次的代码，从易读的if/else链改写成难以阅读的无分支算术。应该听从性能分析器的指引进行优化，而不是凭理论猜测哪里可能有问题。
理解分支预测的真正价值，并不在于手动优化，而在于理解代码为什么会表现出现在这样的性能。当性能分析器显示一个带if语句的简单循环比预期慢时，分支误预测往往就是答案。当你对输入数据排序后，处理速度奇迹般地提升时，原因也正是分支预测。拥有这样的思维模型，你就能诊断那些原本令人费解的性能问题。
