在C中，为什么“signed int”比“unsigned int”更快？
在C中，为什么signed int比unsigned int更快？ 是的，我知道这个网站已被多次询问和回答（链接如下）。 但是，大多数人都说没有区别。 我编写了代码并意外地发现了显着的性能差异。
为什么我的代码的“未签名”版本比“签名”版本慢（即使在测试相同的数字时）？ （我有一个x86-64英特尔处理器）。
类似的链接
- 签名比无符号整数更快
- 无符号vs有符号整数的性能
编译命令： 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; }
unsigned int版本
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
您的问题确实很有趣，因为无符号版本始终产生的代码速度慢10到20％。 然而，代码中存在多个问题：
- 两个函数都返回
0和7，这是不正确的。 - 测试
if (i != num) return 0; else return 1;if (i != num) return 0; else return 1;完全没用，因为循环体只运行i < num。 这样的测试对于小型主要测试是有用的，但特殊的shell测试并不是真正有用。 - 无符号版本中的强制转换是多余的。
- 产生文本输出到终端的基准测试代码是不可靠的，你应该使用
clock()函数来计算CPU密集型函数，而不需要任何干预I / O. - 主要测试的算法完全没有效率，因为循环运行
num / 2次而不是sqrt(num)。
让我们简化代码并运行一些精确的基准测试：
#include #include 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倍 ！
关于问题为什么函数在无符号时变慢？ ，让我们看一下生成的代码（ 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的寄存器内容相同，但是idivl指令可能比idivl指令占用更少的周期。 实际上，有符号除法的运算精度比无符号除法的精度低一点，但这种微小变化的差异似乎相当大。 - 我怀疑在
idivl的硅实现中投入了更多的努力，因为签名的划分比无符号的划分更常见（通过英特尔多年的编码统计来衡量）。 - 正如rcgldr评论，查看英特尔工艺的指令表，对于Ivy Bridge，DIV 32位需要10个微操作，19到27个周期，IDIV 9微操作，19到26个周期。 基准时间与这些时间一致。 额外的微操作可能是由于DIV（64/32位）中的操作数较长而不是IDIV（63/31位）。
这个令人惊讶的结果应该教给我们一些教训：
- 优化是一项艰难的艺术，是谦虚和拖延。
- 优化通常会被优化打破。
- 选择一个更好的算法远远超过优化。
- 总是基准代码，不要相信你的直觉。
由于未定义有符号整数溢出，编译器可以对涉及有符号整数的代码进行大量假设和优化。 无符号整数溢出被定义为环绕，因此编译器将无法进行优化。 另请参见http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html#signed_overflow和http://www.airs.com/blog/archives/120 。
根据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延迟和吞吐量相同， IDIVL存在细微差别。
这可以解释差异，因为-O3汇编代码仅因我的机器上的签名（DIVL与IDIVL）而不同。
替代维基候选测试可能/可能不会显示显着的时差。
#include #include #define J 10 #define I 5 int main(void) { clock_t c1,c2,c3; for (int j=0; j
样本输出
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