优化：昂贵的分支与便宜的比较

这是一篇很好的文章，讲述了低级优化技术，并展示了一个例子，作者将昂贵的部门转换为便宜的比较。 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倍加速所致。

虽然比较非常便宜，但我一直听说分支机构非常昂贵，因为它们可能会导致管道堵塞。由于关于分支的传统观点，我从来不会考虑这种方法。

为什么在这种情况下分支不是瓶颈？是因为我们在每次比较之后都会返回吗？是否因为这里的代码大小很小，因此处理器没有太多预测误差？在什么情况下它会成为瓶颈，并开始主宰分裂的成本？作者从来没有谈论过这件事。

任何人都可以解决便宜的比较和昂贵的分支机构之间的明显争用？当然，优化的黄金法则是必须始终衡量。然而，至少对这个问题有一些直觉是很好的，以便在尝试提出更快速地制作代码的新方法时可以智能地进行比较。

谢谢！

来源

2013-08-07 Matthew Fioravante

呃。它正在减少分支。 'if'是一个分支，但'while'也有一个分支。现在这些人数减少了4倍。在简单的情况下，它只是重新排序分支，并减少div /增量操作。在实际情况下（使用分支预测？）它将允许管道保持填充状态，因为条件不是_actually_分支，而“while”总是分支 – sehe

“条件实际上并不分支”是什么意思？ “ if（v <10）确实看起来像一个分支给我。 –

根据生成的程序集，其中一个“分支”不会实际分支（EIP只会像增加一个noop一样增加） – sehe

分行不一定是昂贵的 - 它真的预测失误分支是昂贵。

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

对于任何给定的输入，只有其他分支被采用。也就是说，你需要做一个接一个的测试，并且直到你达到与输入数量的大小相匹配的那个分支，所有的分支都不被采用（即if条件将是错误的）。假设（例如）输入数字的随机混合，例如16位数的最大值，我们最终在循环的4次迭代中取一个四个分支中的一个。在16次测试中，我们只需要一个分支（平均而言）就可以完成一次，而一个体面的分支预测器可能几乎将所有时间都视为未被采用。其结果是，我们可能最终在整个计算中完全错误预测分支一个。根据经验法则，正确预测的分支需要大约1个时钟，而错误预测的分支需要大约20-30个时钟。因此，对于一个16位数的数字，我们最终会得到类似15位数字+4个循环迭代= 19个正确预测的分支+ 1个错误预测分支，总共总计39-49个时钟。比如说，一个2位数的数字，我们最终会达到1 + 20 = 21个钟左右。

明显的选择是除以10并在每次迭代中检查余数。分区相对昂贵 - 例如，一个64位的分区可能需要大约26-86个周期。为了简单起见，我们假设平均值为40.因此，对于一个16位数字，我们可以预计大约16 * 40 =〜640个时钟。即使在最好的情况下，我们假设每个分区只需要26个时钟的2位数字，所以我们最终总计为52个时钟。底线：即使在非常接近它的最佳情况下，划分仍然比几乎最差的比较结果慢。大部分比较最终都能正确预测，所以我们通常只会得到一个昂贵的（错误预测）分支。

_{1.本，当然，是假设一个现代的，相对高端处理器。在一个非常旧的处理器（或低端嵌入式处理器）上，您可能根本没有分支预测器，所以所有分支往往都相当昂贵。同时，这样的处理器可能根本就没有分割指令，如果是这样，它可能非常慢。总之，分支和分支比现代处理器需要更多的时钟，但分支通常还是比分区快得多。}

来源

2013-08-07 02:32:45

[通过常数除法]（http://stackoverflow.com/q/5558492/995714）可以通过乘以其乘法逆来进行优化。所以它比简单的部门便宜很多。然而，乘法比比较和加法还要昂贵，所以减少乘法的次数也可能导致更快的执行 –

-1

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

收益主要来自避免每个数字的昂贵的划分，每个数字可能花费超过100个时钟周期。可以这样说，由于max uint64_t值有22个十进制数字，所以将循环展开为22个比较将是最有效的方式。

来源

2013-08-07 01:12:23 edwinc

“唯一明确的分支是在返回时”。你是否建议你在实际采取时只为分支付钱，而不是在他们不采取时付钱？ –

你总是支付条件评估。但是，除非采用分支，否则指令流水线不需要刷新。（请注意，现代CPU可以进行分支预测，这可能会使情况复杂一点，但基本依然存在：流水线要么被刷新，要么保持饱和） – sehe

如果相信作者，为条件付钱便宜，几乎免费即使这样也没有问题。所以我们理解了一切。我们试图避免的分支实际性能问题是冲洗管道。冲洗是唯一潜在的放缓还是会出现分支的其他后果？一般情况下，高速缓存局部性为 –

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

虽然，就编码风格偏好而言，我会使用第一个实现。一组类似的分支很可能会表现得更好，但它仍然是更多的代码，看起来它是不经意地写的（事实上，它为什么保留结果？）。如果我想要五位以上的数字呢？：|

来源

2013-08-07 03:30:40 nfries88

优化：昂贵的分支与便宜的比较

回答

相关问题