最好避免在可能的情况下使用mod运算符吗？

Question

我假设计算数字的模数是一个稍微昂贵的操作，至少与简单的算术测试（例如，查看数字是否超过数组的长度）相比。如果确实如此，替换更有效，例如，以下代码：

res = array[(i + 1) % len];

以下是什么？ ：

res = array[(i + 1 == len) ? 0 : i + 1];

第一个更容易在眼睛上，但我想知道第二个可能更有效。如果是这样，当使用编译语言时，我是否可以期望优化编译器将第一个代码段替换为第二个代码段？

当然，这种“优化”（如果它确实是一种优化）在所有情况下都不起作用（在这种情况下，只有当i+1永远不超过len时才有效）。

Answer 1

我的一般建议如下。使用您认为更容易看到的版本，然后分析整个系统。只优化探查器标记为代码瓶颈的代码部分。我敢打赌我的底价是模数运算符不会在其中。

就具体示例而言，只有基准测试可以告诉您使用特定编译器在特定体系结构上哪个更快。你可能用branching替换modulo，而且它显而易见的更快。

Answer 2

一些简单的测量：

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int test = atoi(argv[1]);
    int divisor = atoi(argv[2]);
    int iterations = atoi(argv[3]);

    int a = 0;

    if (test == 0) {
        for (int i = 0; i < iterations; i++)
            a = (a + 1) % divisor;
    } else if (test == 1) {
        for (int i = 0; i < iterations; i++)
            a = a + 1 == divisor ? 0 : a + 1;
    }

    printf("%d\n", a);
}

使用gcc或clang与-O3进行编译，并运行time ./a.out 0 42 1000000000（modulo version）或time ./a.out 1 42 1000000000（比较版本）会导致

• 模数版本的用户运行时间为6.25秒，
• 比较版本为1.03秒。

（使用gcc 5.2.1或clang 3.6.2; Intel Core i5-4690K @ 3.50GHz; 64位Linux）

这意味着使用比较版本可能是个好主意。

Answer 3

那么，看看有两种方法来获得“模3”循环计数器的下一个值。

int next1(int n) {
    return (n + 1) % 3;
}

int next2(int n) {
    return n == 2 ? 0 : n + 1;
}

我用gcc -O3选项（对于常见的x64架构）编译它，并使用-s来获取汇编代码。

第一个函数的代码执行一些无法解释的魔法（*）以避免除法，无论如何使用乘法：

addl    $1, %edi
movl    $1431655766, %edx
movl    %edi, %eax
imull   %edx
movl    %edi, %eax
sarl    $31, %eax
subl    %eax, %edx
leal    (%rdx,%rdx,2), %eax
subl    %eax, %edi
movl    %edi, %eax
ret

并且比第二个功能更长（我打赌更慢）：

leal    1(%rdi), %eax
cmpl    $2, %edi
movl    $0, %edx
cmove   %edx, %eax
ret

因此，“（现代）编译器做得比你更好”并不总是如此。

有趣的是，使用4而不是3的相同实验导致第一个函数的屏蔽

addl    $1, %edi
movl    %edi, %edx
sarl    $31, %edx
shrl    $30, %edx
leal    (%rdi,%rdx), %eax
andl    $3, %eax
subl    %edx, %eax
ret

但它仍然，并且大到不如第二个版本。

更明确地说明了做事的正确方法

int next3(int n) {
    return (n + 1) & 3;;
}

产生更好的结果：

leal    1(%rdi), %eax
andl    $3, %eax
ret

（*）好吧，不是那么复杂。通过互惠的乘法。计算整数常数K =（2 ^ N）/ 3，对于一些足够大的N值。现在，当你想要X / 3的值而不是除以3时，计算X * K，并将其移位N位置向右。

Answer 4

如果代码中的'len'足够大，则条件将更快，因为分支预测器几乎总是正确猜测。

如果没有，那么我认为这与循环队列密切相关，通常情况下长度是2的幂。这将使编译器能够用简单的AND替换模数。

代码如下：

#include <stdio.h>
#include <stdlib.h>

#define modulo

int main()
{
    int iterations = 1000000000;
    int size = 16;
    int a[size];
    unsigned long long res = 0;
    int i, j;

    for (i=0;i<size;i++)
        a[i] = i;

    for (i=0,j=0;i<iterations;i++)
    {
        j++;
        #ifdef modulo
            j %= size;
        #else
            if (j >= size)
                j = 0;
        #endif
        res += a[j];
    }

    printf("%llu\n", res);
}

大小= 15：

• 形式：4,868s
• cond：1,291s

大小= 16：

• 形式：1,067s
• cond：1,599s

在gcc 7.3.0中编译，带-O3优化。这台机器是i7 920。

Answer 5

Modulo可以在大多数架构上使用单处理器指令完成（例如x86上的DIV）。但是，您可能需要过早优化。