c++ - 当模数为特殊形式时，通过模加法进行性能优化

Question

我正在编写一个执行数百万次模块化加法的程序。为了提高效率，我开始思考如何使用机器级指令来实现模块化加法。

令 w 为机器的字长(通常为 32 或 64 位)。如果取模为 2^w，那么模加法可以非常快地执行:只需简单地添加加数，并丢弃进位就足够了。

我使用以下 C 代码测试了我的想法:

#include <stdio.h>
#include <time.h>

int main()
{
    unsigned int x, y, z, i;
    clock_t t1, t2;

    x = y = 0x90000000;

    t1 = clock();

    for(i = 0; i <20000000 ; i++)
        z = (x + y) % 0x100000000ULL;

    t2 = clock();

    printf("%x\n", z);
    printf("%u\n", (int)(t2-t1));

    return 0;
}

使用具有以下选项的 GCC 进行编译(我使用 -O0 来防止 GCC 展开循环):

-S -masm=intel -O0

生成的汇编代码的相关部分是:

    mov DWORD PTR [esp+36], -1879048192
    mov eax, DWORD PTR [esp+36]
    mov DWORD PTR [esp+32], eax
    call    _clock
    mov DWORD PTR [esp+28], eax
    mov DWORD PTR [esp+40], 0
    jmp L2
L3:
    mov eax, DWORD PTR [esp+36]
    mov edx, DWORD PTR [esp+32]
    add eax, edx
    mov DWORD PTR [esp+44], eax
    inc DWORD PTR [esp+40]
L2:
    cmp DWORD PTR [esp+40], 19999999
    jbe L3
    call    _clock

很明显，不涉及任何模运算。

现在，如果我们将 C 代码的模块化添加行更改为:

z = (x + y) % 0x0F0000000ULL;

汇编代码改为(只显示相关部分):

    mov DWORD PTR [esp+36], -1879048192
    mov eax, DWORD PTR [esp+36]
    mov DWORD PTR [esp+32], eax
    call    _clock
    mov DWORD PTR [esp+28], eax
    mov DWORD PTR [esp+40], 0
    jmp L2
L3:
    mov eax, DWORD PTR [esp+36]
    mov edx, DWORD PTR [esp+32]
    add edx, eax
    cmp edx, -268435456
    setae   al
    movzx   eax, al
    mov DWORD PTR [esp+44], eax
    mov ecx, DWORD PTR [esp+44]
    mov eax, 0
    sub eax, ecx
    sal eax, 28
    mov ecx, edx
    sub ecx, eax
    mov eax, ecx
    mov DWORD PTR [esp+44], eax
    inc DWORD PTR [esp+40]
L2:
    cmp DWORD PTR [esp+40], 19999999
    jbe L3
    call    _clock

显然，在对 _clock 的两次调用之间添加了大量指令。

考虑到汇编指令数量的增加，我预计通过正确选择模数获得的性能增益至少为 100%。但是，运行输出时，我注意到速度仅提高了 10%。我怀疑操作系统正在使用多核 CPU 并行运行代码，但即使将进程的 CPU 亲和性设置为 1 也没有改变任何东西。

你能给我一个解释吗？

编辑: 使用 VC++ 2010 运行该示例，我得到了预期结果:第二个代码比第一个示例慢了大约 12 倍!

Answer 1

Art nailed it .

对于2的幂模，-O0和-O3生成的计算代码是一样的，不同的是循环控制代码，并且运行时间相差 3 倍。

对于另外一个模数，循环控制代码的区别是一样的，但是计算的代码不太相同(优化后的代码看起来应该快一点，但我不太了解关于组装或我的处理器是肯定的)。未优化和优化代码之间的运行时间差异约为 2 倍。

两个模块的运行时间与未优化代码相似。与不带任何模数的运行时间大致相同。与从生成的程序集中去除计算得到的可执行文件的运行时间大致相同。

所以运行时间完全由循环控制代码支配

    mov DWORD PTR [esp+40], 0
    jmp L2
L3:
    # snip
    inc DWORD PTR [esp+40]
L2:
    cmp DWORD PTR [esp+40], 19999999
    jbe L3

打开优化后，循环计数器保存在寄存器中(此处)并递减，然后跳转指令为 jne。该循环控制速度如此之快，以至于模数计算现在占用了运行时间的很大一部分，从生成的程序集中删除计算现在将运行时间减少了 3 倍。 2.

因此，当使用 -O0 进行编译时，您测量的不是计算速度，而是循环控制代码的速度，因此差异很小。通过优化，您可以同时测量计算和循环控制，计算速度的差异会清楚地显示出来。