在C中,为什么"signed int"比"unsigned int"更快？

Question

在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

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;
}

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位).

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

• 优化是一项艰难的艺术,是谦虚和拖延.
• 优化通常会被优化打破.
• 选择一个更好的算法远远超过优化.
• 总是基准代码,不要相信你的直觉.

Answer 2

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

Answer 3

根据AMD/Intel 的指令规范，我们有（对于 K7）：

\n\n

Instruction Ops Latency Throughput\nDIV r32/m32 32  24      23\nIDIV r32    81  41      41\nIDIV m32    89  41      41 \n

\n\n

IDIVL对于 i7，延迟和吞吐量相同DIVL，\xc2\xb5ops 存在细微差别。

\n\n

这可以解释这种差异，因为 -O3 汇编代码仅在我的机器上的符号不同（DIVL 与 IDIVL）。

\n