c++ - 优化:昂贵的分支与便宜的比较

Question

这是一篇很棒的文章，讨论了低级优化技术，并显示了一个示例，其中作者将昂贵的除法转换为廉价的比较。
https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920

对于那些不想单击的人，他基本上将其转换为:

uint32_t digits10(uint64_t v) {
    uint32_t result = 0;
    do {
        ++result;
         v /= 10;
    } while (v);
     return result;
}

变成这个:

uint32_t digits10(uint64_t v) {
  uint32_t result = 1;
  for (;;) {
    if (v < 10) return result;
    if (v < 100) return result + 1;
    if (v < 1000) return result + 2;
    if (v < 10000) return result + 3;
    // Skip ahead by 4 orders of magnitude
    v /= 10000U;
    result += 4;
  }
}

结果导致速度提高了6倍。

尽管比较非常便宜，但我一直听说分支机构非常昂贵，因为它们会导致管道停顿。由于有关分支的常规知识，我从来没有考虑过这样的方法。

为什么在这种情况下分支不是瓶颈？是因为我们在每次比较之后都返回了吗？是因为这里的代码大小很小，因此处理器不会过多地预测错误？在什么情况下会成为瓶颈并开始支配部门的成本？作者从未谈论过这一点。

谁能解决廉价比较与昂贵分支之间的明显争执？当然，优化的黄金法则是必须始终衡量。但是，至少对这一问题有一定的直觉，这样一来，当人们想出新的方法来使代码更快时，就可以明智地使用比较。

谢谢!

Answer 1

分支不一定昂贵-确实是错误预测的分支，价格昂贵1。

因此，让我们从循环开始。它是无限的，因此总是被采用。由于它总是被使用，所以它也总是被预测为被使用，因此它很便宜。

对于任何给定的输入，仅采用另一个分支。就是说，您接连进行一项测试，直到达到与输入数字大小相匹配的一项为止，所有分支都不会被采用(即if条件为假)。

假设(例如)输入数字的随机混合，例如最多16个数字，我们最终会从循环的4个迭代中选取大约四个分支之一。我们只在16个测试中平均只选择一个分支，而一个体面的分支预测变量可能会几乎所有时间都将其预测为未采用。结果是，我们可能在整个计算中最终只得到了一个错误预测的分支。

根据经验，正确预测的分支大约需要1个时钟，而错误预测的分支大约需要20-30个时钟。因此，对于16位数字，我们最终得到大约15位数字+ 4个循环迭代= 19个正确预测的分支+ 1个错误预测的分支，总计大约39-49个时钟。例如，对于一个2位数的数字，我们最终得到1 + 20 = 21个时钟。

显而易见的替代方法是除以10，并在每次迭代时检查其余部分。除法相对昂贵-例如，在i7上，64位除法可能需要大约26-86个周期。为了简单起见，我们假设平均值为40。因此，对于16位数字，我们可以预期单独的除法运算大约为16 * 40 =〜640个时钟。即使充其量，我们也假设2位数字每格仅需要26个时钟，因此最终总共有52个时钟。

底线:即使在非常接近最佳情况下，除法结果仍然比几乎最差情况下的比较结果慢。大多数比较最终都得到正确的预测，因此我们通常最终只会得到一个昂贵的(错误预测)分支。


1.当然，这是在假设现代，相对高端的处理器。在真的很旧的处理器(或低端嵌入式处理器)上，您可能根本没有分支预测器，因此所有分支往往都非常昂贵。同时，这样的处理器可能根本没有除法指令，如果有，可能很慢。简而言之，分支和除法都比现代处理器花费更多的时钟，但是分支通常仍然比除法要快得多。