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

Question

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

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

以下是什么？:

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

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

当然,这种"优化"(如果它确实是一种优化)在所有情况下都不起作用(在这种情况下,它只有在i+1永远不会超过的情况下才有效len).

Answer 1

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

就具体示例而言,只有基准测试可以告诉您使用特定编译器在特定体系结构上哪个更快.你可能会用分支替换模数,而且显而易见的是更快的东西.

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(模数版本)或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”循环计数器的下一个值的 2 种方法。

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 导致第一个函数的 and-masking

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位置在右边。