这是一篇很棒的文章，它讨论了低级优化技术，并展示了作者将昂贵的除法转换为便宜的比较的示例。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倍的速度。
虽然比较非常便宜，但我总是听说分支非常昂贵，因为它们可能导致管道停滞。由于关于分支的传统智慧，我从来没有考虑过这样的方法。
为什么在这种情况下分支不是瓶颈?是因为我们在每次比较之后都返回吗?是因为这里的代码大小很小，因此处理器不会有太多的错误预测吗?在什么情况下，它会成为一个瓶颈，并开始主导部门的成本?作者从来没有提到过这个。
谁能解决廉价比较和昂贵分支之间明显的争论?当然，优化的黄金法则是必须始终进行测量。然而，至少对这个问题有一些直觉是好的，这样当人们试图想出新的方法来使代码更快时，就可以明智地使用比较。
谢谢!
分支并不一定是昂贵的——这真的是错误的预测分支是昂贵的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个时钟。
<标题>选择取决于你为什么需要这样做，你可以使用一个更快的近似值。例如，如果您计数数字以便分配足够的内存来保存结果，那么您可以更快地计数八进制(以8为基数)数字的数量。这将给你的结果有点太长，所以你偶尔分配一个额外的字节。
我们也可以欺骗一点点。我们知道，对于64位数字，十进制表示永远不会超过18位，因此我们只能查看输入的18*3 = 54位。
但是这个近似可以真的快。例如:
input &= 0777777777777777777;
while (input != 0) {
++digits;
input >>= 3;
}
它最多有18次迭代——但由于(如链接文章中所述)"大多数数字都很小"，我们期望它在大多数情况下执行的次数要少得多。但是这个循环的主体只使用非常基本的操作，所以即使在最坏的情况下，我们也只期望每次迭代大约4个时钟(这将是在像Pentium 4这样的东西上，一次只能移动1位，所以3位移位需要3个连续的移位指令)。对于最新的处理器，即使是最坏的情况也可能在单个divide指令的速度附近(我们通常期望的速度要小得多)。
如果我们确实期望大量的数字很大，我们可以使用(某种程度上)二分查找来代替。例如，让我们考虑一个32位数字。我们将从与上面相同的作弊开始，只查看足够的位数来给出最大十进制数所需的计数(9位，所以27位)。
那么让我们先把它分成15位在上面的"half"下半部分有12位:
input &= 0777777777; // keep only the bottom 27 bits
if (input & 0777770000) {
digits += 5;
input >>= 12;
}
然后我们基本上只是重复这个模式15位，以此类推到3位。
if (input & 077700) {
digits += 2;
input >>= 6;
}
if (input & 0770) {
++digits;
input >> = 3;
}
if (input & 070) {
input >>= 3;
++digits;
}
if (input != 0) {
++digits;
}
if语句体中的两个指令可以在超标量处理器上并行执行，如果我们有谓词指令(例如，ARM)，我们可以避免任何错误预测的分支。作为一个大胆的猜测，整个序列可以与单个div指令具有相同的一般顺序。
事实上，在这一点上，速度可能主要受到我们从内存中读取数据的速度的限制，所以如果我们想进一步优化，我们可能希望主要关注提高缓存命中率。
但正如前面所指出的:这确实取决于能够使用可能在部分时间略有错误的近似值。如果我们不能容忍这一点，那就不是一个选择。
<标题>总结即使在非常接近最好的情况下，除法仍然比几乎最坏的比较情况慢。大多数比较最终预测正确，所以我们通常只得到一个昂贵的(错误预测的)分支。
如果一个合理的近似(对于"合理"的某些定义)是足够的，那么就很容易大大提高速度。
<子>1。当然，这是假设一个现代的，相对高端的处理器。在非常老的处理器(或低端嵌入式处理器)上，您可能根本没有分支预测器，因此所有的分支都非常昂贵。同时，这样的处理器可能根本没有除法指令，即使有，也可能相当慢。简而言之，分支和除法都比现代处理器占用更多的时钟，但分支通常比除法快得多。
第一个实现实际上分支更多，即使它只有一个分支点。
，不过，出于对编码风格的偏好，我将使用第一个实现。类似分支的集合可能会更好地执行，但它仍然是更多的代码，并且看起来像是未经深思熟虑编写的(事实上，为什么要保留结果?)如果我想要多于5位数呢?: |
算法主要是比较。唯一显式的分支是在返回时。
收益主要来自于避免了每个数字可能占用100多个时钟周期的昂贵除法。可以这样说，因为最大uint64_t值有22位十进制数字，所以将循环展开为22次比较将是最有效的方法。