完全预测分支的分支预测开销

Question

我看到有人说完美预测的分支几乎没有开销。（例如在分支预测对性能的影响？的回答中）

我不太明白人们是什么意思。至少分支条件必须被评估，这可能是一个简单的布尔值或一个函数调用，需要时间。

- AdyAdy

---

分支预测允许CPU在它知道条件是否为真之前就开始处理分支目标上的代码。如果它猜对了，那么将大大加快代码的速度。 - Bo Persson

此外，评估是1）几乎免费的，2）不能合理地被视为开销。#2是我的观点，但我认为他们认为这是CPU停顿，否则不会发生的开销。 - zzxyz

@zzxyz：是的，即使是一个完美预测的已占用分支，也会让前端更难跟上（以最大速率向后端提供指令）。从连续内存中获取/解码指令比跳来跳去容易得多。请参见http://agner.org/optimize/，以及https://stackoverflow.com/tags/x86/info中的其他性能链接。 - Peter Cordes

@PhilipRoman 如果你正在编辑任何被错误标记的[branch]问题，有一个[branch-prediction]标签可以替换它，而不是仅仅删除它（如果适用的话）。虽然由于你的编辑需要经过审核队列，直到你有更多的声望，我不建议你主动寻找更多问题来编辑。 - Peter Cordes

Answer 1

摘要

即使是完美预测，评估分支条件也总是需要一些工作的，但由于现代CPU内部的并行性，额外的工作并不一定会增加特定指令序列的成本。

详情

我认为部分混淆是因为许多人对CPU指令执行的心理表现模型。是的，每个指令都需要一些工作，这应该意味着每个指令在执行时间上都有一些成本，即使很小，对吗？

如果执行的总成本只是每个指令的工作量相加，那么这就是真的了-您只需将所有工作量相加即可获得最终成本。但由于现代CPU中的大量并行处理，它并不像那样工作。

想象一下组织生日派对的情景。你可能需要购买面粉，需要10分钟，然后烤蛋糕需要60分钟，再去拿一个特别的礼物需要30分钟。这些时间都是活动所需的“工作”。但是，当面粉被取走和蛋糕正在被烤制时，有人可以去拿礼物。然而，没有面粉就无法烤蛋糕。因此，你有两个依赖链：70分钟的购买面粉->烤蛋糕链和30分钟的拿礼物链。在无限并行的情况下，只有70分钟与蛋糕相关的链条对所有任务完成的时间做出贡献。拿礼物需要30分钟的“工作”，但由于其他需要更长时间（即关键路径）并且同时进行的工作，它不会耗费时间（不会延迟所有任务的完成）。

更多的额外任务可以并行完成，直到没有人可分配给它们为止。在这一点上，执行吞吐量限制开始增加延迟，这被称为资源冲突。如果资源冲突延迟了关键路径，而不是较短的依赖链之一，则会导致问题。CPU不知道哪个依赖链是/将成为关键路径，因此它们的调度不像聪明的人类在这个计划类比中那样优先考虑它。

---

如果您想更加具体地了解这些内容如何直接应用于CPU，请参阅数据流图的风暴式介绍。

一旦我们拥有了这种新的心理模型，其中指令序列的成本往往由某个关键路径主导，我们就可以开始看到为什么预测良好的分支通常非常低廉甚至没有成本：

• 分支指令没有输出寄存器和内存输出¹，这意味着它们不能像典型依赖链一样参与除最终节点外的依赖链。因此，分支不参与形成长依赖链，从某种意义上说是“超出常规”，可以与其他结果并行计算。
• 分支指令的实际执行通常需要很少的工作量：在现代x86上，它们可以在两个端口上执行，具有1个周期的延迟。此外，分支指令可以与之前的ALU操作“融合”，导致的操作仍然在1个周期内执行，因此从某种意义上说，分支有时可以折叠到先前的操作中，而不需要额外的工作量²。这显然有助于“近乎零成本”的论点，也有助于“真正的零成本”论点，因为需要更少的资源意味着更少可能触发吞吐量瓶颈，从而干扰零成本执行调度。

这些因素结合起来使得大多数预测的分支指令成本为零或几乎为零。

你不必相信我的话，让我们看一个真实的例子：

int mul1(int count, int x) {
    do {
        x *= 111;
    } while (--count);

    return x;
}

给定一个计数器 count 和一个起始值 x，它将 x 乘以 111 count 次并返回结果。循环组装三条指令：一条用于乘法，一条用于 --count，另一条用于检查 count 的值：

.L2:
  imul eax, eax, 111
  sub edi, 1
  jne .L2

现在这里有同样的循环，但是加了一个额外的分支：

int mul2(int count, int x) {
    do {
        x *= 111;
        if (x == 0) {
            abort();
        }
    } while (--count);

    return x;
}

这组装成了5条指令。多余的两条是用于测试x和分支，测试显示x为零：

.L7:
  imul eax, eax, 111
  test eax, eax
  je .L12  ; ends up calling abort
  sub edi, 1
  jne .L7

那么增加60%的指令成本是多少，包括分支？至少到4个有效数字为止，成本为零³。

Running benchmarks groups using timer libpfc

** Running benchmark group stackoverflow tests **
                     Benchmark    Cycles
                     No branch     3.000
             Added test-branch     3.000

外观每次迭代需要3个周期，因为它受到涉及3个周期乘法的依赖链的限制。附加指令和分支并不会增加这个依赖链的成本，并且能够“离线”执行，隐藏在关键路径的延迟背后。

---

¹ 从概念上讲，分支指令会写入“rip”寄存器，但它与其他寄存器的处理方式不同: 它的进展是预测的，因此预测器会打破依赖。

² 当然，要解码和融合指令仍需要额外工作，但这通常不是瓶颈，因此在成本方面可能是“免费”的，而像uop缓存这样的东西意味着它甚至可能不经常执行。此外，在x86上，虽然融合的分支指令具有与ALU操作相同的延迟，但在可执行的端口方面却不太灵活，因此根据端口压力的情况，与裸露的ALU操作相比，一条融合指令可能具有一些成本。

³ 实际上，如果你去看“无限”有效数字并查看原始周期计数，你会发现这个循环的额外迭代在两种情况下都需要恰好 3个周期。无分支的情况通常会以整体较短的1个周期结束（随着迭代次数的增加，这个差异相对于整体趋近于0），可能是因为初始的非稳定状态迭代需要额外一个周期，或者误预测恢复在最后一次迭代上需要额外一个周期。

- BeeOnRope

Answer 2

分支预测是在指令级别上预测条件的结果，这是C或C++条件的实际结果——如果那是一百万个字符比较的结果，它可能不是特别有用，因为那个比较将花费很多时间。如果它是迭代两个每个有一百万个字符的字符串的for循环的结束条件，那么它就非常有用，因为它在该循环中发生多次（假设字符串相等）。

对于比较两个长字符串，它并不是免费的。猜对字符串比较将继续进行是免费的（直到我们找到字符串的结尾或者出现差异，此时分支预测就会失败）。

一个“不可预测”的分支会导致处理器不知道代码将继续执行到哪里。现代CPU具有相当长的流水线（15-30步），因此如果流水线没有填充“正确”的代码，处理器将不得不等待“正确”的代码通过流水线。

所以回答实际问题：

当分支本身被很好地预测时，处理器已经在流水线中获得了正确的指令，而且在执行程序的正确指令之前，没有“流水线泡沫”需要通过流水线。请参见下面的类比。如果预测错误，则流水线中会有其他不正确的指令，处理器必须消耗这些指令并将它们丢弃。

把它想象成一个汽车工厂，制造A型和B型车，在一个生产线上先将车身安装到底盘上，喷漆（魔法油漆，几乎瞬间干燥），然后安装发动机和变速箱，接着安装轮子，安装灯光，最后安装玻璃，就是一辆完整的车。每个步骤需要20分钟完成，并且汽车的传送带将在每20分钟向前移动到下一个位置[在这个练习中，我们忽略了移动本身需要时间的事实]。

你负责生产线，你有一堆A型汽车在生产线上。突然，大老板说：“我们刚刚收到了B型车的订单，请立即切换到制造B型车。”于是，你开始将B型车零件投入生产线。但是在下一个B型车从另一端出来之前，还需要相当长的时间。

分支预测的工作原理是“猜测”代码是否会改变方向或跳转到下一条指令。如果它猜对了，就像在“大老板”下来告诉你要在A型和B型车之间切换时猜对了，这样当老板需要时，你就可以准备好正确的车，而不必等待整个生产线运行完毕。

当它工作时，它很棒，因为预期的东西已经准备好了。如果你猜错了，你仍然需要等待整个生产线运行完当前的设置，并将它们存放在“我们没有客户需要这些”的角落（或者以CPU指令为单位，“丢弃指令”）。

现代大多数CPU还支持“预测执行”。这意味着处理器会在实际确定条件之前开始执行指令。因此，处理器将在老板说之前从A车转换到B车上进行工作。如果此时老板说“不，你应该继续处理A车”，那么你就必须放弃一堆已经开始工作的汽车。你不一定要建造所有的汽车，但是你必须按照每20分钟一个步骤的生产线移动它们。

- Mats Petersson

---

这是一个很好的分支预测类比，但我认为它实际上并没有回答所提出的问题。 - prl

“不是特别有用”的部分让我感到困惑。难道有一种情况，百万字符比较不会简化为一个紧凑的比较循环，迭代大量比较...每个比较都是近乎瞬间的寄存器比较吗？将其简化为一个缓慢的比较似乎并不特别...准确...当讨论性能时。但也许我错过了一些微妙之处。 - zzxyz

我想这取决于你如何看待它。我想就应用程序代码本身而言，也许“一个缓慢的比较”就足够公平了... - zzxyz

@zzxyz的意思是，在循环中比较这些字符串时，分支预测是无意义的，因为比较本身所需的时间比错误预测的惩罚要多得多。与逐个字符比较不同。这暗示了我的问题的答案： “零开销”意味着“零开销 - 除了评估分支条件”。 - AdyAdy

@AdyAdy - 在这种情况下，“比较本身”实际上是成千上万次的比较，这使得分支预测远非毫无意义。这就是我的意思。（尽管“外部”的分支预测只发生一次...是的...在那时相对不重要。） - zzxyz

这是一个很好的解释分支预测如何工作以及为什么它很重要，但似乎并没有回答OP的问题。据我理解，问题已经假定分支已经被很好地预测了：那么问题就是，既然评估分支的指令仍然必须被执行，这可能涉及一些“工作”和因此的“成本”，那么为什么它是免费或几乎免费的？ - BeeOnRope