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

Question

我读到一个完美预测的分支的开销为零/几乎为零。（例如：https : //stackoverflow.com/a/289860/8038490）我不太明白人们的意思。至少必须评估分支条件，这可以是一个简单的 bool 或函数调用，这需要时间。

Answer 1

概括

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

细节

我认为部分混乱在于许多人对 CPU 指令执行的心理性能模型。是的，每条指令都需要一些工作，所以这意味着每条指令都有一定的成本，无论多小，以执行时间衡量，对吗？

好吧，如果执行的总成本只是添加到每个指令的工作中，那将是正确的 - 您只需将所有工作加在一起并获得最终成本。由于现代 CPU 中的大量并行性，它不会像那样工作。

把它想象成组织一个生日派对。您可能需要购买需要 10 分钟的面粉，然后需要 60 分钟的时间烘烤一个蛋糕，然后在 30 分钟后去挑选一份特殊的礼物。这些时间是活动所需的所有“工作”。但是，有人可以在拿起面粉和烤蛋糕的同时去取礼物。然而，没有面粉你不能烤蛋糕。所以你有两个依赖链：70 分钟购买面粉 -> 烘焙蛋糕链，以及 30 分钟领取礼品链。无限并行，只有 70 分钟蛋糕相关链有助于一切准备就绪的时间。拿起礼物 30 分钟的工作但它最终花费 没有时间（不延迟完成所有任务），因为其他工作需要更长的时间（也就是关键路径）并且并行发生。

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

有关这些内容如何直接应用于 CPU 的不那么抽象和更实用的外观，请参阅数据流图的旋风介绍。

一旦我们有了这个新的思维模型，其中指令序列的成本通常由通过序列的某个关键路径主导，我们就可以开始了解为什么预测良好的分支通常成本非常低或为零：

• 分支指令没有输出寄存器，也没有内存输出¹。这意味着除了作为最终节点之外，它们不能参与典型的依赖链——它们总是结束依赖链。所以分支不参与长依赖链的形成，因此在某种意义上是“不合时宜的”并且可以自由地与其他结果并行计算。
• 分支指令的实际执行通常只需要很少的工作：在现代 x86 上，它们可以在两个端口上执行，具有 1 个周期的延迟。此外，分支指令可以与先前的 ALU 操作融合，结果操作仍会在 1 个周期内执行 - 因此在某种意义上，分支有时可以折叠到先前的操作中，而无需在执行^{2 时}进行额外的工作。这显然有助于“接近零成本”的论点，但也有助于“真正零成本”的论点，因为需要更少的资源意味着不太可能触发会干扰零成本执行计划的吞吐量瓶颈。

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

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

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

    return x;
}

给定 acount和一个起始值x，它乘以x111count次并返回结果。循环汇编为 3 条指令，一个用于乘法，一个用于乘法，一个用于--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 op 具有相同的延迟，但它在可以执行的端口方面不太灵活，因此根据端口压力，融合指令可能会产生一些成本与裸 ALU 操作相比。

³事实上，如果您转到“无限”有效数字并查看原始循环计数，您会发现此循环的额外迭代在这两种情况下都恰好花费了3 个循环。无分支情况通常最终会缩短 1 个周期（随着迭代次数的增加，差异在相对意义上变为 0），这可能是因为初始非稳态迭代需要一个额外的周期，或者错误预测恢复需要最后一次迭代的额外循环。