优化:昂贵的分支与廉价的比较

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

分支机构不一定昂贵 - 它真的是错误预测的分支机构,价格昂贵¹.

那么,让我们从循环开始吧.它是无限的,所以它总是被采用.由于它总是被采用,它也总是被预测为采取,所以它便宜.

对于任何给定的输入,只有一个其他分支被采用.也就是说,你做一个接一个的测试,直到你到达与输入数量的大小匹配的那个,所有的分支都不被采用(即,if条件将是假的).

假设(例如)输入数字的随机混合,例如最多16位,我们最终在循环的4次迭代中取出四个分支中的大约一个.我们只采取了一个分支(平均)大约16个测试中的一个,并且一个体面的分支预测器可能会预测它们几乎所有时间都没有.结果是我们可能在整个计算中最终只有一个错误预测的分支.

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

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

结论:即使在非常接近最佳情况下,除了比较差的最差情况之外,除法仍然要慢.大多数比较最终都是正确预测的,因此我们通常最终只得到一个昂贵的(错误预测的)分支.

_{当然,这是一个现代的,相对高端的处理器.在一个非常古老的处理器(或低端嵌入式处理器)上,您可能根本没有分支预测器,因此所有分支都非常昂贵.同时,这样的处理器可能根本没有除法指令,如果有,它可能很慢.简而言之,分支和分区比现代处理器需要更多的时钟,但是分支通常比分区快得多.}