为什么使用 unsigned int 的模数比使用 unsigned long long 的模数运行得更快？

Question

为什么要测试取模速度？

我有一个每秒执行数百万次模数运算的应用程序。我必须处理非常大的数字，所以我选择 unsigned long long 作为数据类型。大约一周前，我为我的应用程序编写了一个新算法，该算法需要对比我以前使用的数字少的数字执行模运算（例如 26 而不是 10000000）。我选择使用 unsigned int 作为数据类型。 速度大幅提升而算法几乎相同。

正在测试...

我用C写了两个简单的程序来测试模数计算的速度。

#include <stdio.h>

typedef unsigned long long ull;

int main(){
   puts("Testing modulus with ull...");
   ull cnt;
   ull k, accum=0;
   for(k=1, cnt=98765432;k<=10000000;++k,--cnt) 
      accum+=cnt%80;
   printf("%llu\n",accum);
   return 0;
}

我唯一要更改的是名为 cnt 的变量类型。

我用time ./progname测试了这些程序，结果如下。

unsigned long long：3.28 秒
unsigned int：0.33 秒

注意：我正在越狱iPad上测试它，这就是为什么它需要这么多时间。

为什么？

为什么 unsigned long long 的版本要花这么多时间到运行？

Update1: 将 --cnt 添加到循环中，因此 cnt%80 不会保持不变；结果还是一样。

Update2: 删除了 printf 并添加了 accum 以消除 printf 占用的时间；结果现在少了很多，但仍然有很大不同。

Answer 1

从根本上说，执行算术运算所花费的时间量与操作数中的位数至少成线性关系。对于现代 cpus，加法、减法、逻辑运算的时间是恒定的（通常是一个周期），当操作数适合寄存器时可能还有乘法，但可以扩展到 RSA 数量级或其他 "bignum" 用法，你会清楚地看到执行算术缩放的时间。

在除法和取余运算的情况下，这些运算本质上成本更高，而且您通常会注意到不同操作数大小的显着差异。当然，如果您的 cpu 是 32 位的，则执行 64 位 division/remainder 操作将涉及从多个较小的操作中构建它（很像 [=21= 的一个小特例） ] 算术）所以它会慢得多。

但是，您的测试完全无效。除法是恒定的，因此甚至不应该在每次循环迭代时重新计算，循环中花费的时间应由 printf 决定，并且您使用 printf 的格式说明符对打印 unsigned long long 类型的参数，因此您的程序具有未定义的行为。

Answer 2

假设是 32 位系统，区别在于 64 位与 32 位模运算。

ull cnt;

结果（使用 -O2 优化）：

.L2:
    pushl   [=11=]
    pushl   
    pushl   %edi
    pushl   %esi
    call    __umoddi3           ; note the function call here
    addl    , %esp
    addl    %eax, -32(%ebp)
    adcl    %edx, -28(%ebp)
    addl    $-1, %esi
    movl    %esi, %eax
    adcl    $-1, %edi
    xorl    765432, %eax
    orl     %edi, %eax
    jne     .L2
    pushl   -28(%ebp)
    pushl   -32(%ebp)
    pushl   $.LC1
    pushl   
    call    __printf_chk

而

unsigned int cnt;

结果（也使用 -O2 优化）：

.L2:
    movl    %ecx, %eax
    mull    %ebx
    shrl    , %edx
    leal    (%edx,%edx,4), %eax
    movl    %ecx, %edx
    sall    , %eax
    subl    %eax, %edx
    movl    %edx, %eax
    xorl    %edx, %edx
    addl    %eax, %esi
    adcl    %edx, %edi
    subl    , %ecx
    cmpl    765432, %ecx
    jne     .L2
    pushl   %edi
    pushl   %esi
    pushl   $.LC1
    pushl   
    call    __printf_chk

考虑到 __umoddi3 函数中的代码量，我们已经回答了问题。

为什么使用 unsigned int 的模数比使用 unsigned long long 的模数运行得更快？

Why is modulus with unsigned int runs faster than with unsigned long long?

c

modulus

speed-test

为什么要测试取模速度？

正在测试...

为什么？