在C中，为什么“signed int”比“unsigned int”更快？

4 回答

• 0

  您的问题确实很有趣，因为无符号版本始终产生的代码速度慢了10％到20％ . 然而，代码中存在多个问题：

  • 这两个函数都返回 2 ， 2 ， 3 ， 5 和 7 ，这是不正确的 .

  • 测试 if (i != num) return 0; else return 1; 完全没用，因为循环体仅为 i < num 运行 . 这样的测试对于小型主要测试是有用的，但是特殊的套管它们并不真正有用 .

  • 无符号版本中的强制转换是多余的 .
    产生文本输出到终端的

  • 基准测试代码是不可靠的，您应该使用 clock() 函数来计算CPU密集型功能，而无需任何干预I / O.

  • 主要测试的算法完全没有效率，因为循环运行 num / 2 次而不是 sqrt(num) .

  让我们简化代码并运行一些精确的基准测试：

  #include <stdio.h>
  #include <time.h>
  
  int isprime_slow(int num) {
      if (num % 2 == 0)
          return num == 2;
      for (int i = 3; i < num; i += 2) {
          if (num % i == 0)
              return 0;
      }
      return 1;
  }
  
  int unsigned_isprime_slow(unsigned int num) {
      if (num % 2 == 0)
          return num == 2;
      for (unsigned int i = 3; i < num; i += 2) {
          if (num % i == 0)
              return 0;
      }
      return 1;
  }
  
  int isprime_fast(int num) {
      if (num % 2 == 0)
          return num == 2;
      for (int i = 3; i * i <= num; i += 2) {
          if (num % i == 0)
              return 0;
      }
      return 1;
  }
  
  int unsigned_isprime_fast(unsigned int num) {
      if (num % 2 == 0)
          return num == 2;
      for (unsigned int i = 3; i * i <= num; i += 2) {
          if (num % i == 0)
              return 0;
      }
      return 1;
  }
  
  int main(void) {
      int a[] = {
          294967291, 0, 294367293, 0, 294967293, 0, 294967241, 1, 294967251, 0,
          294965291, 0, 294966291, 0, 294963293, 0, 294927293, 1, 294961293, 0,
          294917293, 0, 294167293, 0, 294267293, 0, 294367293, 0, 294467293, 0,
      };
      struct testcase { int (*fun)(); const char *name; int t; } test[] = {
          { isprime_slow, "isprime_slow", 0 },
          { unsigned_isprime_slow, "unsigned_isprime_slow", 0 },
          { isprime_fast, "isprime_fast", 0 },
          { unsigned_isprime_fast, "unsigned_isprime_fast", 0 },
      };
  
      for (int n = 0; n < 4; n++) {
          clock_t t = clock();
          for (int i = 0; i < 30; i += 2) {
              if (test[n].fun(a[i]) != a[i + 1]) {
                  printf("%s(%d) != %d\n", test[n].name, a[i], a[i + 1]);
              }
          }
          test[n].t = clock() - t;
      }
      for (int n = 0; n < 4; n++) {
          printf("%21s: %4d.%03dms\n", test[n].name, test[n].t / 1000), test[n].t % 1000);
      }
      return 0;
  }
  

  在OS / X上使用 clang -O2 编译的代码生成此输出：

  isprime_slow:  788.004ms
  unsigned_isprime_slow:  965.381ms
           isprime_fast:    0.065ms
  unsigned_isprime_fast:    0.089ms
  

  这些时间与OP在不同系统上观察到的行为一致，但显示了更高效的迭代测试所带来的显着改善：更快！ 10000 times ！

  关于为什么函数使用unsigned更慢的问题？让我们看一下生成的代码（gcc 7.2 -O2）：

  isprime_slow(int):
          ...
  .L5:
          movl    %edi, %eax
          cltd
          idivl   %ecx
          testl   %edx, %edx
          je      .L1
  .L4:
          addl    $2, %ecx
          cmpl    %esi, %ecx
          jne     .L5
  .L6:
          movl    $1, %edx
  .L1:
          movl    %edx, %eax
          ret
  
  unsigned_isprime_slow(unsigned int):
          ...
  .L19:
          xorl    %edx, %edx
          movl    %edi, %eax
          divl    %ecx
          testl   %edx, %edx
          je      .L22
  .L18:
          addl    $2, %ecx
          cmpl    %esi, %ecx
          jne     .L19
  .L20:
          movl    $1, %eax
          ret
         ...
  .L22:
          xorl    %eax, %eax
          ret
  

  内部循环非常相似，指令数量相同，类似指令 . 然而，这里有一些可能的解释：

  • cltd 将 eax 寄存器的符号扩展到 edx 寄存器，这可能导致指令延迟，因为 eax 被紧接的前一条指令 movl %edi, %eax 修改 . 然而，这会使签名版本比未签名版本慢，而不是更快 .

  • 对于无符号版本，循环的初始指令可能未对齐，但不太可能，因为更改源代码中的顺序对时序没有影响 .

  • 尽管有符号和无符号除法运算符的寄存器内容相同，但 idivl 指令可能比 divl 指令占用的周期更少 . 实际上，带符号的除法运算精度比无符号除法的精度低一点，但这种微小变化的差异似乎很大 .

  • 我怀疑在 idivl 的硅实现中投入了更多的努力，因为签名的划分比无符号划分更常见（通过英特尔多年的编码统计来衡量） .

  • 由rcgldr评论，查看英特尔过程的指令表，对于Ivy Bridge，DIV 32位需要10个微操作，19到27个周期，IDIV 9微操作，19到26个周期 . 基准时间与这些时间一致 . 额外的微操作可能是由于DIV（64/32位）中的操作数较长而不是IDIV（63/31位） .

  这个令人惊讶的结果应该教给我们一些教训：

  • 优化是一项艰难的艺术，谦虚和拖延 .

  • 正确性经常被优化打破 .

  • 选择一个更好的算法远远超过优化 .

  • 总是基准代码，不要相信你的直觉 .

  回复于 2024-04-29T18:22:13+08:00
• 4

  由于未定义有符号整数溢出，编译器可以对涉及有符号整数的代码进行大量假设和优化 . 无符号整数溢出被定义为环绕，因此编译器将无法进行优化 . 另见http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html#signed_overflow和http://www.airs.com/blog/archives/120 .

  回复于 2024-04-29T18:22:13+08:00
• 12

  从Instruction specification on AMD/Intel我们（对于K7）：

  Instruction Ops Latency Throughput
  DIV r32/m32 32  24      23
  IDIV r32    81  41      41
  IDIV m32    89  41      41
  

  对于i7， IDIVL 和 DIVL 的延迟和吞吐量相同，μops存在细微差别 .

  这可以解释差异，因为-O3汇编代码仅相差在我的机器上签名（DIVL vs IDIVL） .

  回复于 2024-04-29T18:22:13+08:00
• 1

  替代维基候选测试可能/可能不会显示显着的时差 .

  #include <stdio.h>
  #include <time.h>
  
  #define J 10
  #define I 5
  
  int main(void) {
    clock_t c1,c2,c3;
    for (int j=0; j<J; j++) {
      c1 = clock();
      for (int i=0; i<I; i++) {
        isprime(294967241);
        isprime(294367293);
      }
      c2 = clock();
      for (int i=0; i<I; i++) {
        isunsignedprime(294967241);
        isunsignedprime(294367293);
      }
      c3 = clock();
      printf("%d %d %d\n", (int)(c2-c1), (int)(c3-c2), (int)((c3-c2) - (c2-c1)));
      fflush(stdout);
    }
    return 0;
  }
  

  样本输出

  2761 2746 -15
  2777 2777 0
  2761 2745 -16
  2793 2808 15
  2792 2730 -62
  2746 2730 -16
  2746 2730 -16
  2776 2793 17
  2823 2808 -15
  2793 2823 30
  

  回复于 2024-04-29T18:22:13+08:00