17

我需要在代码的热路径中执行一些整数除法。我已经通过分析和循环计数确定整数除法正在花费我。我希望我能做些什么来加强将师减少到更便宜的东西。

在这条路径中，我除以 2^n+1，其中 n 是可变的。本质上，我想优化此功能以删除除法运算符：

unsigned long compute(unsigned long a, unsigned int n)
{
    return a / ((1 << n) + 1);
}

如果我除以 2^n，我只需将 div 替换为右移 n。如果我除以一个常数，我会让编译器的强度降低那个特定的除法，很可能把它变成一个乘法和一些移位。

是否有适用于 2^n+1 的类似优化？

编辑：这里的 a 可以是任意 64 位整数。n 只取 10 到 25 之间的几个值。我当然可以为每个 n 预先计算一些值，但不能为 a。

4

2 回答 2

13

由于您只能移动int这么多位置，因此您可以将所有这些情况放入一个常数的几个分区之一中的选择中：

unsigned long compute(unsigned long a, unsigned int n)
{
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader):
    switch (n) {
        case  0: return a / ((1 << 0) + 1);
        case  1: return a / ((1 << 1) + 1);
        case  2: return a / ((1 << 2) + 1);

            // cases 3 through 30...

        case 31: return a / ((1 << 31) + 1);
    }
}

所以现在每个除法都是一个常数，编译器通常会将其简化为一系列乘法/移位/加法指令（如问题所述）。请参阅ac/c++ 编译器是否通过二次幂值将常量除法优化为移位？详情。

于 2010-10-25T17:39:10.783 回答
9

您可以将整数除法替换为常数、乘法（模字大小）与幻数和移位。

可以为已知常数预先计算幻数。

由于 n 不能取很多值，例如 0..31，因此“容易”为所有 n 预先计算这些幻数并将其存储在具有 32 个元素的表中。

用于计算幻数的 Javascript 页面

如果除数在编译时是常数，一个好的编译器可以计算幻数并用乘法和移位代替整数除法。根据其余代码是如何围绕性能关键代码构建的，您可以使用宏或内联技巧来展开所有可能的 n 值，并让编译器完成查找幻数的工作（类似于使用开关的答案，但我会在常量区域中放置更多代码，否则它可能是不值得的交易——分支也会降低你的性能）

详细说明和计算幻数的代码可以在 Henry S. Warren, Jr. 的《Hackers Delight》一书中提供资金（强烈推荐必须有书！）第 180 页。

相关章节的 Google 图书链接：

第10-9章除数的无符号除法> = 1

于 2010-10-25T18:16:31.787 回答