在 C 中,为什么 signed int
比 unsigned int
快?是的,我知道这个问题已经在这个网站上被多次询问和回答(下面的链接)。但是,大多数人表示没有区别。我写过代码,无意中发现了显着的性能差异。
为什么我的代码的“未签名”版本比“签名”版本慢(即使测试相同的数字)? (我有一个 x86-64 Intel 处理器)。
相似链接
编译命令: 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 ./测试
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
对于2
,3
,5
和7
,这是不正确的。 - 测试
if (i != num) return 0; else return 1;
完全没用,因为循环体只针对i < num
运行.这样的测试对于小素数测试很有用,但对它们进行特殊封装并不是很有用。 - 未签名版本中的转换是多余的。
- 向终端生成文本输出的基准测试代码不可靠,您应该使用
clock()
无需任何干预 I/O 即可对 CPU 密集型功能进行计时的功能。 - 素数测试算法在循环运行时效率极低
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;
}
用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 位)更长。
这个令人惊讶的结果应该给我们一些教训:
- 优化是一门困难的艺术,要谦虚和拖延。
- 正确性经常被优化破坏。
- 选择更好的算法远远胜过优化。
- 始终对代码进行基准测试,不要相信自己的直觉。
关于c - 在 C 中,为什么 "signed int"比 "unsigned int"快?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34165099/