2

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

设 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 倍！

4

2 回答 2

2

艺术 把它钉牢了。

对于 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，您测量的不是计算速度，而是循环控制代码的速度，因此差异很小。通过优化，您可以同时测量计算和回路控制，并且计算中的速度差异清楚地显示出来。

于 2012-08-30T18:02:28.797 回答
1

两者之间的区别归结为这样一个事实，即除以 2 的幂可以在逻辑指令中轻松转换。

a/n其中 n 是 2 的幂 等价于a >> log2 n 模它的相同 a mod n可以由a & (n-1)

但在你的情况下，它甚至更进一步：你的价值 0x100000000ULL 是 2^32。这意味着任何无符号 32 位变量将自动成为模 2^32 值。编译器足够聪明，可以删除该操作，因为它是对 32 位变量的不必要操作。ULL 说明符不会改变这一事实。

对于适合 32 位变量的值 0x0F0000000，编译器无法省略操作。它使用看起来比除法运算更快的转换。

于 2012-08-30T15:07:06.183 回答