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

Question

在C语言中，为什么signed int比unsigned int更快？虽然这个问题在本网站上已经被问答过多次（参见下面的链接），但是大多数人说它们之间没有差别。我写了代码，偶然发现了显著的性能差异。

即使测试相同的数字，为什么我的代码的“unsigned”版本比“signed”版本慢？（我使用的是x86-64 Intel处理器）。 类似的链接：

• Faster comparing signed than unsigned ints
• performance of unsigned vs signed integers

编译命令: gcc -Wall -Wextra -pedantic -O3 -Wl,-O3 -g0 -ggdb0 -s -fwhole-program -funroll-loops -pthread -pipe -ffunction-sections -fdata-sections -std=c11 -o ./test ./test.c && strip --strip-all --strip-unneeded --remove-section=.note --remove-section=.comment ./test

---

signed int 版本

注意：如果我明确声明所有数字为signed int，则不会有任何区别。

int isprime(int num) {
    // Test if a signed int is prime
    int i;
    if (num % 2 == 0 || num % 3 == 0)
        return 0;
    else if (num % 5 == 0 || num % 7 == 0)
        return 0;
    else {
        for (i = 11; i < num; i += 2) {
            if (num % i == 0) {
                if (i != num)
                    return 0;
                else
                    return 1;
            }
        }
    }
    return 1;
}

无符号整数 版本

int isunsignedprime(unsigned int num) {
    // Test if an unsigned int is prime
    unsigned int i;
    if (num % (unsigned int)2 == (unsigned int)0 || num % (unsigned int)3 == (unsigned int)0)
        return 0;
    else if (num % (unsigned int)5 == (unsigned int)0 || num % (unsigned int)7 == (unsigned int)0)
        return 0;
    else {
        for (i = (unsigned int)11; i < num; i += (unsigned int)2) {
            if (num % i == (unsigned int)0) {
                if (i != num)
                    return 0;
                else
                    return 1;
            }
        }
    }
    return 1;
}

使用以下代码在文件中测试：

int main(void) {
    printf("%d\n", isprime(294967291));
    printf("%d\n", isprime(294367293));
    printf("%d\n", isprime(294967293));
    printf("%d\n", isprime(294967241)); // slow
    printf("%d\n", isprime(294967251));
    printf("%d\n", isprime(294965291));
    printf("%d\n", isprime(294966291));
    printf("%d\n", isprime(294963293));
    printf("%d\n", isprime(294927293));
    printf("%d\n", isprime(294961293));
    printf("%d\n", isprime(294917293));
    printf("%d\n", isprime(294167293));
    printf("%d\n", isprime(294267293));
    printf("%d\n", isprime(294367293)); // slow
    printf("%d\n", isprime(294467293));
    return 0;
}

结果（time ./test）：

Signed - real 0m0.949s
Unsigned - real 0m1.174s

- Devyn Collier Johnson

---

我会首先比较生成的汇编代码，看看在无符号情况下是否有额外的指令被发出。我会尽量让翻译更加通俗易懂，但不会改变原意。 - Tom Karzes

在编写基准测试时，我强烈建议将测量时间增加至少30秒，并以可能的最高优先级运行执行基准测试的任务。否则，您所测量到的20％差异可能很大程度上是由操作系统引起的。 - Lukas Thomsen

它们是自由转换。它们告诉编译器改变类型，但不需要任何代码来实现。 - harold

在我的机器上，两种汇编代码仅在有符号/无符号算术运算（idivl与divl）方面存在差异，但执行时间大致相同，跟OP所展示的情况一样。这种差异可能是由于这些指令引起的...是否由于指令并行性、乱序执行等原因导致的边界效应呢？ - Jean-Baptiste Yunès

(unsigned int)3 可以更清晰地写成 3u。 - M.M

Answer 1

你的问题非常有趣，因为未签名版本总是产生比较慢10到20％的代码。然而，这段代码存在多个问题：

- 两个函数都返回0用于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倍！ 关于问题“为什么使用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 位）。

这个惊人的结果应该教我们一些经验教训：

• 优化是一门困难的艺术，要谦虚和拖延。
• 正确性常常被优化破坏。
• 选择更好的算法比优化要好得多。
• 始终对代码进行基准测试，不要相信自己的直觉。

- chqrlie

---

为什么不预先计算sqrt(m)向下取整（例如将float转换为unsigned int），然后在迭代中使用它作为上限呢？这比测试i * i <= m更快。 - Henno Brandsma

可能更快也可能不更快，只有基准测试才能说明。在现代CPU上，乘法速度非常快。对于较大的“num”值还存在精度问题。最后但并非最不重要的是，我试图编写非常简单的函数，以便汇编代码也可以保持简单。 - chqrlie

这个答案似乎包含了最实际的信息，但是对我来说仍然没有澄清问题。 - Michael Burr

@MichaelBurr：我怀疑在idivl的硅实现中投入了更多的精力，因为有符号除法比无符号除法更常见（根据英特尔多年的编码统计数据），但我没有证据。 - chqrlie

查看英特尔处理器的指令表，对于Ivy Bridge，DIV 32位需要10个微操作，19至27个周期，IDIV需要9个微操作，19至26个周期。在Windows XP（我唯一的32位操作系统），Intel 3770K 3.5 GHz，Visual Studio上，整数的快速时间为0.048毫秒，无符号整数为0.065毫秒。 - rcgldr

Answer 2

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

- shadow_map

---

你的陈述是正确的，但是看着x86编译器生成的代码，似乎并不是一个恰当的解释。 - chqrlie

你的语句看起来没问题，但似乎回答了相反的问题。所以最后是错误的。 - iBug

Answer 3

从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的延迟和吞吐量相同，微操作略有不同。这可能解释了在我的机器上，-O3汇编代码仅因符号不同（DIVL vs IDIVL）而不同的差异。

- Jean-Baptiste Yunès

---

稍等，这个顺序是错误的：这会让未签名的速度更快。 - harold

但是这个表格显示对于32位无符号整数应该更快，但实际上并不是这样的（当然，OP可能已经没有K7了）。 - harold

这些可能是最坏情况的延迟，例如负操作数。当操作数为负时，您测量的性能是否会发生变化？ - Michael

unsigned版本使用了div，这将会更快速。 - phuclv

Answer 4

备选维基百科候选测试，可能/可能不会显示出显著的时间差异。

#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

- chux - Reinstate Monica

Answer 5

实际上，在许多情况下，无符号比有符号更快，例如：

• 在除以2的幂时

    unsigned int x=37;
    cout<<x/4;

• 检查一个数字是否为偶数

    unsigned int x=37;
    cout<<(x%2==0)?"even":"odd";

- ishandutta2007

---

“在许多情况下，无符号整型比有符号整型更快。”您对这种说法有证据吗？您的示例只展示了如何使用unsigned int，但您的答案并未展示任何与性能有关的内容，因此没有真正回答该问题。 - Thomas Flinkow

目前你的回答不够清晰，请编辑并添加更多细节，以帮助其他人理解它如何回答问题。你可以在帮助中心找到有关如何编写好答案的更多信息。 - Community

@ThomasFlinkow 进行基准测试，请查看此回答：链接。 - ishandutta2007