关于除数为常量时的快速取余的更多乐趣

在编程中，编译器经常会把除法优化掉，取而代之的是耗时更低的指令，尤其当除数为常量时。我最近写了一些关于除数为常量时的快速取余的内容（译注：翻译内容在这里）。我有提到如果直接算出余于是非常有效的，而不需要先计算商（就像是除数为常量时编译器做的那样）。

为了得到好的结果，我们使用了很重要的一点，但没有在任何地方说明：我们使用了 64 位的处理器指令去做 32 位的运算。这很公平，因为编译器也会这样做，但是他们没有系统地做到这一点。如果算法问题恰到好处，单独使用这个技巧就足以在某些情况下获得实质性收益。

因此这还是有点小复杂的。针对 32 位运算使用 64 位指令有时候是有用的。此外，直接计算余数，而不是先算出商，有时候也是有用的。让我们用一个有趣的数据点，来激励我们进一步的工作吧。

首先让我们考虑一下，如果这些繁重的工作都交由编译器来做的话，我们如何计算余数（D 对编译器来说一已知的常量）。我期望编译器能讲下面的代码转换成 32 位的指令序列：

uint32_t compilermod32(uint32_t a) {
  return a % D;
}

接下来我们可以直接计算余数，使用了一些数学技巧和 64 位指令。

#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))

uint32_t directmod64(uint32_t a) {
  uint64_t lowbits = M * a;
  return ((__uint128_t)lowbits * D) >> 64;
}

最后，你可以“间接地”计算余数（先计算出商），但是使用 64 位指令。

uint32_t indirectmod64(uint32_t a) {
  uint64_t quotient = ( (__uint128_t) M * a ) >> 64;
  return a - quotient * D;
}

对于基准测试，我打算使用上述的 3 种方法再加上原始方法来计算线性同余（基本上是一个需要余数的递归线性函数）。我使用了常量除数 22，skylake 处理器，以及 GNU GCC 8.1 编译器。对每一个生成的数，我都测量了平均的 CPU 周期：

slow (division instruction)	29 cycles
compiler (32-bit)	12 cycles
direct (64-bit)	10 cycles
indirect (64-bit)	11 cycles

源代码在这里。

根据你的平台不同，这 3 种方法都可能是最优结果。某些情况下，甚至原生除法指令都可能胜出。例如，在 ARM 和 POWER 处理器上，除法指令就打败了一些编译器。

最后我们得到了什么呢？除了一个简单的 C 函数可以打败先进的优化编译器外，再无其他。但在很多情况下，我们发现使用 64 位指令来直接计算 32 位取余最好了。

本文翻译自 Daniel Lemire 的文章，原文发表于其博客。