在C中,为什么signed int速度比unsigned int？是的,我知道这个网站已被多次询问和回答(链接如下).但是,大多数人说没有区别.我编写了代码并意外地发现了显着的性能差异.
为什么我的代码的"未签名"版本比"签名"版本慢(即使在测试相同的数字时)？(我有一个x86-64英特尔处理器).
类似的链接
签名比无符号整数更快
无符号与有符号整数的性能
编译命令: 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
chqrlie.. 16
您的问题确实很有趣,因为无符号版本始终产生的代码速度慢了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#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; }
clang -O2在OS/X上编译的代码会产生以下输出:
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指令可能比指令占用的周期少divl.实际上,带符号的除法运算精度比无符号除法的精度低一点,但这种微小变化的差异似乎很大.
我怀疑在硅实现方面付出了更多努力,idivl因为签名分区比无符号分区更常见(根据英特尔多年的编码统计数据来衡量).
正如rcgldr评论,查看英特尔工艺的指令表,对于Ivy Bridge,DIV 32位需要10个微操作,19到27个周期,IDIV 9微操作,19到26个周期.基准时间与这些时间一致.额外的微操作可能是由于DIV(64/32位)中的操作数较长而不是IDIV(63/31位).
这个令人惊讶的结果应该教给我们一些教训:
优化是一项艰难的艺术,是谦虚和拖延.
优化通常会被优化打破.
选择一个更好的算法远远超过优化.
总是基准代码,不要相信你的直觉.
查看英特尔工艺的指令表，对于Ivy Bridge，DIV 32位需要10个微操作（19到27个周期），IDIV 9个微操作（19到26个周期）。在Windows XP（我只有32位操作系统），Intel 3770K 3.5 GHz，Visual Studio上，int的快速时间为0.048 ms，unsigned int的快速时间为0.065 ms。 (2认同)
shadow_map.. 7
由于带符号整数溢出是不确定的，因此编译器可以对涉及带符号整数的代码进行大量假设和优化。无符号整数溢出被定义为可环绕，因此编译器将无法进行尽可能多的优化。另请参见http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html#signed_overflow和http://www.airs.com/blog/archives/120。
您的问题确实很有趣,因为无符号版本始终产生的代码速度慢了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#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; }
clang -O2在OS/X上编译的代码会产生以下输出:
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指令可能比指令占用的周期少divl.实际上,带符号的除法运算精度比无符号除法的精度低一点,但这种微小变化的差异似乎很大.
我怀疑在硅实现方面付出了更多努力,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。
京公网安备 11010802040832号 | 京ICP备19059560号-6 