在C/C中获得正模的最快方法

Question

通常在我的内部循环中，我需要以“环绕”的方式对数组进行索引，因此（例如）如果数组大小为100，并且我的代码要求元素-2，那么应该给它元素98。在许多高级语言（如Python）中，只需使用my_array[index%array\u size]就可以做到这一点，但由于某种原因，C的整数算术（通常）向零舍入，而不是一致地向下舍入，因此当给定负的第一个参数时，其模运算符返回负结果。

通常我知道index不会小于-array_size，在这些情况下，我只是做my_array[（indexarray_size）%array_size]。然而，有时这不能保证，对于这些情况，我想知道实现总是正模函数的最快方法。有几种“聪明”的方法可以在没有分支的情况下做到这一点，例如

inline int positive_modulo(int i, int n) {
    return (n + (i % n)) % n;
}

或

inline int positive_modulo(int i, int n) {
    return (i % n) + (n * (i < 0));
}

当然，我可以分析这些，找出我的系统中哪一个最快，但我不能不担心我可能错过了一个更好的，或者我的机器上快的可能在另一个机器上慢。

那么，有没有一种标准的方法来做到这一点，或者是一些我错过的聪明的技巧，这可能是最快的方法呢？

此外，我知道这可能是一厢情愿的想法，但如果有一种方法可以自动矢量化，那将是惊人的。

Answer 1

大多数时候，编译器非常擅长优化代码，因此通常最好保持代码可读性（让编译器和其他开发人员都知道您在做什么）。

由于数组大小始终为正，我建议您将商定义为无符号。编译器将把小的if/else块优化为没有分支的条件指令：

unsigned modulo( int value, unsigned m) {
    int mod = value % (int)m;
    if (mod < 0) {
        mod += m;
    }
    return mod;
}

这创建了一个没有分支的非常小的函数：

modulo(int, unsigned int):
        mov     eax, edi
        cdq
        idiv    esi
        add     esi, edx
        mov     eax, edx
        test    edx, edx
        cmovs   eax, esi
        ret

例如，模（-5，7）返回2。

不幸的是，由于商是未知的，它们必须执行整数除法，这与其他整数运算相比有点慢。如果您知道数组的大小是2的幂，我建议将这些函数定义保存在头中，以便编译器可以将它们优化为更高效的函数。下面是函数无符号模256（int v）{返回模（v，256）；} ：

modulo256(int):                          # @modulo256(int)
        mov     edx, edi
        sar     edx, 31
        shr     edx, 24
        lea     eax, [rdi+rdx]
        movzx   eax, al
        sub     eax, edx
        lea     edx, [rax+256]
        test    eax, eax
        cmovs   eax, edx
        ret

见大会：https://gcc.godbolt.org/z/DG7jMw

请参阅与多数投票答案的比较：http://quick-bench.com/oJbVwLr9G5HJb0oRaYpQOCec4E4

编辑：事实证明，Clang能够生成一个没有任何条件移动指令的函数（这比常规算术运算要贵）。这种差异在一般情况下是完全可以忽略的，因为整除大约占总时间的70%。

基本上，Clang将值向右移动，以将其符号位扩展到m的整个宽度（当为负时为0xffffffff，否则为0），用于屏蔽中的第二个操作数mod m.

unsigned modulo (int value, unsigned m) {
    int mod = value % (int)m;
    m &= mod >> std::numeric_limits<int>::digits;
    return mod + m;
}

Answer 2

将二的幂模化，以下工作（假设两个补码表示）：

return i & (n-1);

Answer 3

我学习的标准方式是

inline int positive_modulo(int i, int n) {
    return (i % n + n) % n;
}

此函数本质上是没有abs的第一个变体（实际上，这会使它返回错误的结果）。如果优化编译器能够识别这种模式并将其编译为计算“无符号模”的机器代码，我不会感到惊讶。

编辑：

继续讨论第二个变体：首先，它也包含一个bug--n

这种变体看起来可能不像是分支，但在许多体系结构上，i

至于这两个变体中哪一个更快，这可能取决于编译器和处理器体系结构——对这两个变体计时，然后查看。不过，我认为没有比这两种变体更快的方法了。