分支预测对性能的影响？

Question

当我编写一些需要快速处理的紧凑循环时，我经常会考虑处理器的分支预测是如何运作的。例如，我尽力避免在最内层循环中使用if语句，特别是那些结果不太均匀的if语句(比如随机评估为true或false)。

我这样做，是因为有一个比较普遍的观点，即处理器预取指令，如果它预测错误分支，那么预取就是无用的。

我的问题是：这真的是现代处理器的问题吗？分支预测能有多好呢？
什么编码模式可以使其更好？

(为了讨论的方便，假设我已经超越了“过早优化是万恶之源”的阶段)

- Shy

---

当我终于有机会亲自测试时，我有一个有趣的惊喜：http://codereview.stackexchange.com/questions/6502/fastest-way-to-clamp-an-integer-to-the-range-0-255 - Mark Ransom

请参考https://dev59.com/iWgu5IYBdhLWcg3wkH6P，这是一个非常具体的例子。 - David d C e Freitas

Answer 1

分支预测现在相当不错。但这并不意味着可以消除分支的惩罚。

在典型代码中，您可能会得到超过99%的正确预测，但性能损失仍然可能很大。其中有几个因素起作用。

一个因素是简单的分支延迟。在普通PC CPU上，错误预测的成本可能在12个周期左右，而正确预测的分支只需要1个周期。为了论证问题，假设所有分支都被正确预测，那么就成功了吗？不完全是。

有分支的简单存在会抑制很多优化。编译器无法在分支之间有效地重组代码。在基本块（即按顺序执行、没有分支、有一个入口点和一个出口点的代码块）内，它可以随意重新排列指令，只要代码的含义得以保留，因为所有指令最终都会被执行。在跨越分支时，情况就变得棘手了。我们可以将这些指令移动到此分支之后执行，但是如何保证它们被执行呢？将它们放在两个分支中？这增加了代码大小，也很混乱，并且如果我们想在多个分支之间重新排序，它就不可扩展了。

即使使用最佳的分支预测，分支仍然可能很昂贵。这不仅是因为错误预测，还因为指令调度变得更加困难。

这也意味着重要的因素不是分支的数量，而是它们之间的代码量。每隔一行就有一个分支是不好的，但如果你能在分支之间放入一打行代码，可能可以将这些指令合理地安排到调度中，使得分支不会过于限制CPU或编译器。

但在典型代码中，分支基本上是免费的。在典型代码中，没有那么多紧密聚集在性能关键代码中的分支。

- jalf

---

关于CPU的部分是错误的。CPU不在乎指令是否在分支之后。它只是获取并执行预测将要采取的路径，就像分支之前的“确定”部分一样。唯一的区别是，在预测分支之后的指令被标记为推测性的（以便CPU可以清除它们，如果预测结果是错误的），并且在退役阶段之前执行后保留，直到确认预测是正确的。因此，最重要的是，正确预测的分支在大多数情况下基本上是免费的。 - slacker

请查看这本书，或者英特尔(Intel)和AMD的优化手册（以PDF形式免费提供）。我敢打赌，在这里也会提到它。当然，任何计算机体系结构的计算机科学课程都会提到它。虽然在某些体系结构上，它更像是25比1。 - jalf

我的调查论文关于分支预测器表明，分支错误预测需要14到25个周期。 - user984260

@slacker: 已经执行的分支对于超标量CPU仍然是一个障碍，因为它们可以在每个时钟周期中获取/解码/执行多个指令（例如Intel Core 2及更高版本中每个时钟周期最多可达4个）。 在已执行分支后的获取块中的指令是无用的。 处理L1i缓存中连续指令块的前端早期部分通常在被执行的分支上损失一些吞吐量。 通常，这些阶段的吞吐量比流水线最窄的部分（通常是进入OoO后端的问题/重命名）要大，因此阶段之间的队列可以吸收气泡。 - Peter Cordes

但是一般来说，布置代码以便常见的快速路径通过一个小函数时不包含任何分支是胜利的。（对于I-cache占用空间以及获取/解码。而且，Intel Haswell及更高版本可以在两个执行端口中执行预测未取的分支，但是只能在端口6上执行预测取的分支。因此，只要其中至少有一个分支未被取，则正确预测的分支吞吐量为每个时钟2个，uop-cache行也由无条件取出的分支结束。请参阅Agner Fog的微架构PDF（https://agner.org/optimize/） - Peter Cordes

Answer 2

"(为了讨论起见，假设我已经超越了“过度优化是万恶之源”的阶段)"

很好。然后你可以对应用程序的性能进行分析，使用gcc的标签进行预测和再次分析，使用gcc的标签进行相反的预测和再次分析。

现在想象一下理论上预取两个分支路径的CPU。对于两条路径中的后续if语句，它将预取四条路径，以此类推。CPU并没有神奇地增加四倍的缓存空间，因此它将预取每条路径的较短部分。

如果你发现你的一半预取被浪费了，损失了5%的CPU时间，那么你确实需要寻找一个不需要分支的解决方案。

- Windows programmer

---

坚果。那些写了更短答案的人得到了更快的答案。 - Windows programmer

Answer 3

如果我们已经超过了“早期优化”阶段，那么我们肯定也超过了“我可以测量它”的阶段吧？由于现代CPU架构的复杂性，唯一确定的方法就是尝试并测量。当然不可能有很多情况下你会有两种实现方式的选择，其中一种需要分支而另一种不需要。

- Mark Ransom

Answer 4

不完全是一个答案，但你可以在这里找到一个 演示现代微处理器中常用的基于表的分支预测有限状态机的小程序。

它说明了使用额外逻辑来生成分支条件和目标地址的快速（但可能错误的）估计的方法。处理器以全速获取和执行预测指令，但当预测结果错误时需要撤消所有中间结果。

- VonC

Answer 5

是的，分支预测确实可能会成为性能问题。

这个问题（目前 StackOverflow 上得票最高的问题）给出了一个例子。

- user541686

Answer 6

我的答案是：

AMD在过去有时比英特尔更快或更好的原因很简单，那就是他们拥有更好的分支预测。

如果您的代码没有分支预测（即它没有分支），则可以预期其运行速度更快。

因此，结论是：如果不必要，请避免使用分支。如果需要，请尝试使一个分支评估95％的时间。

- Claudiu

Answer 7

我最近在TI DSP上发现的一件事是，尝试避免分支有时会生成比分支预测成本更多的代码。

我在一个紧密循环中有类似以下的东西：

if (var >= limit) { otherVar = 0;}

我想要消除潜在的分支，并尝试将其更改为：

otherVar *= (var<limit)&1;

但是“优化”生成的汇编代码是原来的两倍，并且实际上更慢。

- AShelly

---

我知道我晚了8年，但是var<limit包含一个隐含的分支，而&1是无用的。 - Matteo Italia