2

这是一篇很棒的文章，它讨论了低级优化技术，并展示了一个作者将昂贵的除法转换为便宜的比较的例子。 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 倍的加速。

虽然比较非常便宜，但我一直听说分支非常昂贵，因为它们会导致管道停顿。由于关于分支的传统智慧，我永远不会考虑这样的方法。

为什么在这种情况下分支不是瓶颈？是因为我们在每次比较之后立即返回吗？是因为这里的代码很小，因此处理器不会有太多的错误预测吗？在什么情况下它会成为瓶颈并开始主导部门的成本？作者从不谈论这个。

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

谢谢！

4

3 回答 3

10

分支不一定很昂贵——实际上是错误预测的分支很昂贵1。

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

对于任何给定的输入，只会采用另一个分支。也就是说，你一个接一个地进行测试，直到你达到与输入数的大小相匹配的那个，所有的分支都不被取走（即if条件为假）。

假设（例如）输入数字的随机混合，最多为 16 位数字，我们最终会在循环的 4 次迭代中取大约 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 个时钟用于除法。即使充其量，让我们假设每格只需要 26 个时钟的 2 位数字，所以我们最终总共需要 52 个时钟。

底线：即使在非常接近最好的情况下，除法的结果仍然比几乎最坏的情况要慢。大多数比较最终都被正确预测，所以我们通常只得到一个昂贵（错误预测）的分支。

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

于 2013-08-07T02:32:45.107 回答
1

第一个实现实际上分支更多，即使它只有一个分支点。

虽然，只是作为编码风格的偏好问题，我会使用第一个实现。类似分支的集合可能会表现得更好，但它仍然是更多的代码，并且看起来它是没有考虑过的（事实上，它为什么保留结果？）。如果我想要超过五位数怎么办？:|

于 2013-08-07T03:30:40.730 回答
-1

该算法主要是比较。唯一明确的分支是返回时。

收益主要来自避免昂贵的每位数除法，每个位数可能需要超过 100 个时钟周期。可以假设由于最大 uint64_t 值具有 22 个十进制数字，因此将循环展开为 22 个比较将是最有效的方法。

于 2013-08-07T01:12:23.117 回答