c++ - 完美预测分支的分支预测开销

Question

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

Answer 1

概括

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

细节

我认为困惑的部分原因是许多人为执行CPU指令而拥有的心理表现模型。是的，每条指令都需要做一些工作，因此这意味着每条指令在执行时间上的成本是多么小，对吗？

如果将总执行成本简单地加到每条指令的工作中，那将是正确的-您只需将所有工作加在一起并得到最终成本。由于现代CPU中的并行性问题很大，因此它并不是那样工作的。

认为这就像组织生日聚会。您可能需要购买耗时10分钟的面粉，然后烤制一个需60分钟的蛋糕，然后拿起30分钟外的特殊礼物。这些时间是 Activity 所需的所有“工作”。但是，有人可以在拿起面粉和烘烤蛋糕时去拿礼物。但是，如果没有面粉，就无法烘烤蛋糕。因此，您有两个依赖链:70分钟的购买面粉->烤蛋糕链和30分钟的提货礼品链。通过无限的并行性，只有70分钟的蛋糕相关链有助于一切准备就绪的时间。拿礼物需要30分钟的工作时间，但最终却不花时间(不会延迟所有任务的完成)，这是因为其他工作需要更长的时间(也就是关键路径)并且是并行进行的。

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

有关如何将这些内容直接应用于CPU的较抽象和更实际的了解，请参见A Whirlwind Introduction to Dataflow Graphs。

一旦有了这种新的思维模型，其中指令序列的成本通常由该序列中的一些关键路径决定，那么我们就可以开始理解为什么预测良好的分支通常成本很低或为零:

分支指令没有输出寄存器，也没有内存输出1。这意味着他们不能参与典型的依赖链，除非作为最后一个节点-他们总是结束依赖链。因此，分支不参与长依赖性链的形成，因此在某种意义上是“脱节的”，并且可以与其他结果并行地进行计算。

分支指令的实际执行通常只需要很少的工作:在现代的x86上，它们可以在两个端口上执行，周期延迟为1。此外，可以将分支指令与先前的ALU操作融合在一起，并且所得到的操作仍将在1个周期内执行-因此在某种意义上，有时可以将分支折叠为先前的操作，而无需执行额外的工作2。这显然有助于“接近零成本”参数，但也有助于“真正零成本”参数，因为需要更少的资源意味着它不太可能触发会干扰零成本执行计划的吞吐量瓶颈。

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

您不必相信我，让我们看一个真实的例子:

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

    return x;
}

给定一个 count和一个起始值 x，它将 x乘以111 count次并返回结果。循环 assembles到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;
}

这是 assembles的5条指令。额外的两个用于 x的测试，而分支的测试表明 x为零:

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

那么，增加60％的指令(包括分支)的成本是多少？零，至少4个有效数字3:

Running benchmarks groups using timer libpfc

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

该外观每次迭代需要3个周期，因为它受到涉及3周期乘法的依赖链的限制。附加的指令和分支不花任何钱，因为它们没有添加到该依赖链中，并且能够“脱节”执行，从而隐藏了关键路径的延迟。

1从概念上讲，分支指令编写了“rip”寄存器，但根本没有像其他寄存器那样对待:它的进程是提前预测的，因此依赖项被预测器破坏了。

2当然，首先还有很多工作需要对指令进行解码和融合，但这通常不是瓶颈，因此在成本方面可能是“免费的”，并且类似uop缓存的事情意味着甚至可能无法执行频繁地。同样，在x86上，虽然融合分支指令的延迟与ALU op相同，但是它在执行哪些端口方面的灵活性较差，因此取决于端口压力，融合指令可能会花费一些成本与裸露的ALU操作相比。

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