优化分支预测

到目前为止，我们一直在讨论优化内存访问和计算。然而，还有另一个重要的性能瓶颈类别，我们尚未讨论。它与推测执行有关，这是现代高性能 CPU 核心中普遍存在的一项功能。为了提醒你，可以参考 [@sec:SpeculativeExec] 中我们讨论了如何利用推测执行来提高性能。在本章中，我们将探讨减少分支预测错误次数的技术。

一般来说，现代处理器非常擅长预测分支结果。它们不仅遵循静态预测规则，还检测动态模式。通常，分支预测器保存先前分支结果的历史记录，并尝试猜测下一个结果。然而，当模式变得难以跟踪时，CPU 分支预测器可能会影响性能。

当分支预测错误时，会导致显著的速度惩罚。当这种事件经常发生时，CPU 需要清除所有预测性工作，后来证明是错误的。它还需要清空流水线，并开始填充正确路径的指令。通常，现代 CPU 由于分支预测错误而经历 10 到 20 个周期的惩罚。准确的周期数取决于微架构设计，即流水线的深度和从错误预测中恢复的机制。

分支预测器使用缓存和历史寄存器，因此容易受到与缓存相关的问题的影响，即三个 C：

• 强制缺失: 当使用静态预测并且没有动态历史记录可用时，可能会在分支的第一次动态出现时发生预测错误。
• 容量缺失: 由于程序中分支数量非常高或动态模式过长而导致的预测错误。
• 冲突缺失: 分支被映射到缓存桶（关联集）中，使用它们的虚拟和/或物理地址的组合。如果太多活动分支映射到同一集合，则可能丢失历史记录。另一个冲突缺失的实例是错误共享，当两个独立分支被映射到同一个缓存条目并相互干扰时，可能会降低预测历史记录。

程序总会发生非零数量的分支预测错误。您可以通过查看 TMA 的 Bad Speculation 指标来了解程序受分支预测错误的影响程度。对于通用应用程序来说，Bad Speculation 指标在 5-10\% 的范围内是正常的。我们建议一旦该指标超过 10\%，就要密切关注。

由于分支预测器擅长发现模式，因此以前用于优化分支预测的建议不再适用。过去，开发人员可以通过在分支指令的编码前缀中提供预测提示来为处理器提供选择 (0x2E: Branch Not Taken, 0x3E: Branch Taken)。这可能会提高旧微架构（如 Pentium 4）的性能。虽然在现代处理器上仍然使用这些分支前缀会生成有效的 x86/x64 汇编，但不会在现代处理器上产生性能提升。[TODO]

减少分支预测错误的一种间接方法是使用基于源代码和编译器的技术来简化代码。PGO 和 BOLT 通过提高顺序执行率来减少分支预测错误，从而缓解了分支预测器结构的压力。我们将在下一章中讨论这些技术。

因此，也许唯一直接消除分支预测错误的方法是消除分支本身。在接下来的两个小节中，我们将看看如何用查找表和预测来替代分支。

有一个常规智慧认为，从预测的角度来看，从不被采取的分支对分支预测是透明的，不会影响性能，因此删除它们并没有太多意义。然而，与这种智慧相反的是，BOLT 优化器的作者进行的一项实验表明，在大型代码库应用程序（例如 Clang C++ 编译器）中，将从不被采取的分支替换为相同大小的空操作，可以在现代 Intel CPU 上带来约 5\% 的加速。因此，尽管还是值得尝试消除所有分支。