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

Question

通常在我的内部循环中,我需要以"环绕"方式索引数组,因此如果数组大小为100并且我的代码要求元素-2,则应该给出元素98.在许多高级语言中作为Python,人们可以简单地使用my_array[index % array_size],但由于某种原因,C的整数运算(通常)向零舍入而不是一致向下舍入,因此当给定负的第一个参数时,其模运算符返回负结果.

通常我知道这index不会少于-array_size,在这些情况下我只是这样做my_array[(index + array_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

我学到的标准方法是

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

这个函数本质上是你没有的第一个变量abs(事实上​​,它使它返回错误的结果).如果优化编译器能够识别这种模式并将其编译为计算"unsigned modulo"的机器代码,我不会感到惊讶.

编辑:

继续你的第二个变体:首先,它也包含一个bug - n < 0应该是i < 0.

这个变体可能看起来不像是分支,但在很多架构上,i < 0会编译成条件跳转.在任何情况下,这将是至少一样快,以取代(n * (i < 0))用i < 0? n: 0,这避免了乘法; 另外,它更"干净",因为它避免了将bool重新解释为int.

至于这两个变体中的哪一个更快,这可能取决于编译器和处理器架构 - 两个变体的时间和看.不过,我认为没有比这两种变体更快的方法.

Answer 2

模数为2的幂,以下工作(假设二进制补码表示):

return i & (n-1);

Answer 3

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

由于您的数组大小始终为正，因此我建议您将商定义为unsigned。编译器会将小的 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

例如modulo(-5, 7)返回2。

不幸的是，由于商不知道它们必须执行整数除法，这与其他整数运算相比有点慢。如果您知道数组的大小是 2 的幂，我建议将这些函数定义保存在头文件中，以便编译器可以将它们优化为更高效的函数。这是功能unsigned modulo256(int v) { return modulo(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%，因此这种差异在一般情况下完全可以忽略不计。

基本上，锵移位value右到其符号位扩展到的整个宽度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 4

使用二进制补码符号位传播获得可选加数的老式方法:

int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}

Answer 5

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

以下快吗？- 可能不像其他人那么快，但对于所有^{1 来说} 都是简单且功能正确的a,b- 与其他人不同。

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: -b is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

其他各种答案都有mod(a,b)弱点，尤其是当b < 0.

参见欧几里得分裂的想法b < 0

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

i % n + n溢出时失败（想想大i, n） - 未定义的行为。

return i & (n-1);

依赖n为二的幂。（公平的答案确实提到了这一点。）

int positive_mod(int i, int n)
{
    /* constexpr */ int shift = CHAR_BIT*sizeof i - 1;
    int m = i%n;
    return m+ (m>>shift & n);
}

时经常失败n < 0。e, g,positive_mod(-2,-3) --> -5

int32_t positive_modulo(int32_t number, int32_t modulo) {
    return (number + ((int64_t)modulo << 32)) % modulo;
}

使用 2 个整数宽度的义务。（公平的答案确实提到了这一点。）
失败modulo < 0。 positive_modulo(2, -3)--> -1。

inline int positive_modulo(int i, int n) {
    int tmp = i % n;
    return tmp ? i >= 0 ? tmp : tmp + n : 0;
}

时经常失败n < 0。e, g,positive_modulo(-2,-3) --> -5

¹例外：在 C 中，a%b当a/b溢出时未定义为 ina/0或INT_MIN/-1。