旭穹の陋室

分支的代价

当CPU遇到条件跳转或任何其他类型的分支时，在计算出跳转条件之前，CPU不会一直处于空闲状态，而是开始推测性地执行（speculatively executing）似乎更可能立即执行的分支。在执行过程中，CPU会统计每条分支执行的概率，一段时间后，它们开始通过识别常见模式来预测它们。

因此，分支的真正“代价”很大程度上取决于CPU对它的预测能力。如果这是一个纯粹的50/50掷硬币的随机过程，你必须承受控制冒险，并丢弃整个流水线，再花15-20个周期才能重新建立起来。如果分支总是被执行或从未被执行，除了检查条件外，你几乎不付出任何代价。

作为一个案例，我们将创建一个0到99之间的随机整数数组：

for (int i = 0; i < N; i++)
    a[i] = rand() % 100;

然后我们创建一个循环，将其中所有小于50的元素加起来：

volatile int s;

for (int i = 0; i < N; i++)
    if (a[i] < 50)
        s += a[i];

我们设置N=106N = 10^6N=106并多次执行此循环，从而避免**冷缓存效应**（cold cache effect）干扰我们的结果。我们将累加变量标记为volatile，从而编译器不会对循环进行矢量化，交织迭代（interleave iterations，即循环展开），或其他任何“作弊”的手段进行优化。

在Clang上，这将生成如下所示的汇编：

    mov  rcx, -4000000
    jmp  body
counter:
    add  rcx, 4
    jz   finished   ; "jump if rcx became zero"
body:
    mov  edx, dword ptr [rcx + a + 4000000]
    cmp  edx, 49
    jg   counter
    add  dword ptr [rsp + 12], edx
    jmp  counter

我们的目标是模拟一个完全不可预测的分支，并成功地实现了这一目标：（实测）对每个元素的处理平均需要大约14个CPU周期。我们可以做一个非常粗略的理论估计，假设分支在<和>=之间交替，并且每隔一次迭代就会对流水线进行错误预测。然后，每两次迭代：

• 在Zen 2上，会丢弃19个时钟周期的流水线；
• 需要访存和比较操作，这需要大约5个周期。我们可以同时检查偶数次和奇数次的迭代条件，所以假设我们每2次迭代会承担一次访存和比较操作的代价。
• 在<分支下，我们需要额外大概4个周期来将a[i]累加到内存中的volatile变量s。

因此，平均而言，我们需要为每个元素的处理花费(4+5+19)/2=14(4 + 5 + 19) / 2 = 14(4+5+19)/2=14，与我们测试的结果一致。

我们可以将硬编码的50替换为可调整的参数P，该参数可以有效地设置<分支的执行概率：

for (int i = 0; i < N; i++)
    if (a[i] < P)
        s += a[i];

现在，如果我们对不同的P值进行基准测试，我们会得到一张有趣的图：

正如预期的那样，其峰值在50-55%之间，在这里分支预测失败的代价最高。这个图是不对称的：检查分支从不成立的条件（P = 0）只需要~1个循环，如果分支总是成立，则需要~7个循环才能完成求和（P = 100）。

这张图不是单峰的：在85-90%左右还有另一个局部极小值。我们在那里每个元素花费~6.15个周期，比我们总是执行分支时快约10-15%，这说明我们需要执行更少的添加。分支预测失败此时不再影响性能，因为发生这种情况时，不会丢弃整个指令缓冲区，而是只丢弃预测调度的操作。从本质上讲，10-15%的预测失败率是一个平衡点，在这个平衡点上，我们即可以做到在足够长的时间上流水线不会停滞，又可以在执行更"便宜"的>=分支时节省10-15%计算周期。

需要注意的是，检查从未发生或几乎从未发生过的条件几乎不需要任何代价。这就是为什么程序员可以如此频繁地使用运行时异常和基本情况检查的原因：如果它们确实很罕见，那么它们实际上并不需要任何代价。

在我们的示例中，高效地分支预测是通过硬件计数器实现的。如果我们过去更频繁地使用分支A而不是分支B，那么预测性地执行分支A是有意义的。但现代CPU上的分支预测器比这种先进得多，可以检测更复杂的模式。

让我们将P固定回50，然后在求和主循环之前先对数组进行排序：

for (int i = 0; i < N; i++)
    a[i] = rand() % 100;

std::sort(a, a + n);

我们仍在处理相同的元素，但顺序不同，现在运行的周期不是14个，而是4个多一点，这正是完全<分支和完全>=分支耗时的平均值。

分支预测器可以检测到比“总是向左，然后总是向右”或“左-右-左-右”更复杂的模式。如果我们只是将数组的大小从N减少至1000（且不进行排序），然后让分支预测器记住整个比较序列，再次进行基准测试，测得大约4个周期——事实上，这时甚至比对数组进行排序的测试用例消耗周期数更少，因为在排序测试用例中，分支预测器需要花费一些时间在“总是执行”和“总是不执行”状态之间切换。

分支可能性的提示

如果事先知道哪个分支更有可能，那么将该信息传递给编译器可能是有益的：

for (int i = 0; i < N; i++)
    if (a[i] < P) [[likely]]
        s += a[i];

当P = 75时，每次迭代的周期约为7.3，而没有提示的原始版本需要约8.3个周期。

这个提示不会消除分支或向分支预测器传递任何信息，但它改变了机器代码布局，使CPU前端处理更可能的分支的速度稍快（尽管通常不超过一个周期）。

只有当你在编译阶段之前就知道更可能采用哪个分支时，这种优化才是有益的。当分支从根本上不可预测时，我们可以尝试使用预测（predication）来完全移除它——这是我们将在下一节中将要探讨的一项非常重要的技术。

这个案例研究的灵感来自有史以来投票最多的Stack Overflow问题。