c - 在 C 中，为什么 "signed int"比 "unsigned int"快？

Question

在 C 中，为什么 signed int 比 unsigned int 快？是的，我知道这个问题已经在这个网站上被多次询问和回答(下面的链接)。但是，大多数人表示没有区别。我写过代码，无意中发现了显着的性能差异。

为什么我的代码的“未签名”版本比“签名”版本慢(即使测试相同的数字)？ (我有一个 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 ./测试

---

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()无需任何干预 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 位)更长。

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

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