优化分支预测（Optimizing Branch Prediction）

到目前为止，我们一直在讨论如何优化内存访问和计算。然而，还有一类重要的性能瓶颈尚未涉及，它与投机执行（speculative execution）有关——这是所有现代高性能 CPU 核心都具备的特性。如需回顾相关内容，请参阅 [SpeculativeExec] 章节，其中讨论了投机执行如何提升性能。本章将探讨减少分支预测失误（branch misprediction）数量的技术。

总体而言，现代处理器在预测分支结果方面表现出色。它们不仅遵循静态预测规则，还能识别动态模式。通常，分支预测器会保存分支的历史执行结果，并据此猜测下一次的结果。然而，当模式变得难以跟踪时，可能会损害性能。

频繁发生分支预测失误时，会带来显著的惩罚开销。每当这种情况发生，CPU 必须清除所有提前完成的投机性工作（事后证明这些工作是错误的），还需要刷新流水线（pipeline），并从正确路径重新填充指令。通常，现代 CPU 因分支预测失误会承受 10 到 25 个时钟周期的惩罚。确切的周期数取决于微架构设计，即流水线深度以及从预测失误中恢复所使用的机制。

导致分支预测失误最常见的原因，往往是分支结果具有复杂的模式（例如表现出伪随机行为），处理器无法有效预测。为完整起见，下面列出其他较少见的分支预测失误原因。分支预测器使用缓存（cache）和历史寄存器，因此也会受到与缓存相关问题的影响：

• 冷缺失（Cold misses）：当分支首次动态出现、无历史记录可用而只能采用静态预测时，可能发生预测失误。
• 容量缺失（Capacity misses）：由于程序中分支数量极多或动态模式过长，导致历史记录丢失而引发的预测失误。
• 冲突缺失（Conflict misses）：分支通过虚拟地址和/或物理地址的组合映射到缓存桶（关联集合）中。若过多活跃分支映射到同一集合，历史记录可能丢失。冲突缺失的另一种情形是别名（aliasing），即两个独立的分支映射到同一缓存条目并相互干扰，可能导致预测历史质量下降。

程序始终会出现非零次的分支预测失误。可以通过 TMA 的 Bad Speculation 指标来评估程序受分支预测失误影响的程度。对于通用应用程序，Bad Speculation 指标在 5--10\% 范围内属于正常。建议当该指标超过 10\% 时给予重点关注。

过去，开发者可以通过为 x86 处理器的分支指令添加前缀（0x2E: Branch Not Taken，0x3E: Branch Taken）来提供预测提示。这在 Pentium 4 等旧微架构上可能有所改善。然而，现代 x86 处理器曾经忽略这些提示，直到 Intel 的 RedwoodCove 重新启用了这一机制。其分支预测器仍然擅长发现动态模式，但现在它会为从未遇到过的分支（即没有存储信息的分支）使用编码的预测提示。[IntelOptimizationManual]

还有一些间接方式可以通过减少动态分支指令数量来降低分支预测失误率。这种方法有效是因为它减轻了分支预测器结构的压力。当程序执行的分支指令减少时，可能会间接改善之前因容量缺失和冲突缺失而受影响的分支的预测效果。编译器的循环展开（loop unrolling）和向量化（vectorization）等变换有助于减少动态分支数量，尽管它们并非专门针对某个条件语句的预测率进行优化。配置文件引导优化（Profile-Guided Optimizations，PGO）和链接后优化器（post-link optimizers，如 BOLT）也能通过提高直通率（fallthrough rate）来有效减少分支预测失误（即代码直线化）。我们将在下一章讨论这些技术。¹

消除分支预测失误的唯一直接方式是去掉分支指令本身。在后续章节中，我们将同时介绍直接和间接改善分支预测的方法。具体而言，将探讨以下技术：用查找表（lookup tables）、算术运算、条件选择以及 SIMD 指令替换分支。

¹. 传统观点认为，从未被执行的分支（never-taken branches）对分支预测是透明的，不会影响性能，因此从预测角度来看，删除它们意义不大。然而，与此相反，BOLT 优化器作者进行的实验表明：在 Clang C++ 编译器这类代码占用大的应用程序中，将从未被执行的分支替换为等长的空操作（no-ops），在现代 Intel CPU 上可带来约 5\% 的性能提升。因此，尝试消除所有分支仍然值得。 ↩