Warum ist “signed int” in C schneller als “unsigned int”?

Question 1

In C ist warum signed int schneller als unsigned int? Stimmt, ich weiß, dass dies auf dieser Website mehrfach gefragt und beantwortet wurde (Links unten). Die meisten Leute sagten jedoch, dass es keinen Unterschied gibt. Ich habe Code geschrieben und versehentlich einen signifikanten Leistungsunterschied festgestellt.

Warum sollte die „unsignierte“ Version meines Codes langsamer sein als die „signierte“ Version (auch wenn dieselbe Nummer getestet wird)? (Ich habe einen x86-64 Intel-Prozessor).

Ähnliche Verbindungen

Vergleicht schneller vorzeichenbehaftete als vorzeichenlose Ints
Leistung von vorzeichenlosen vs. vorzeichenbehafteten Ganzzahlen

Befehl kompilieren: 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` Ausführung

HINWEIS: Es gibt keinen Unterschied, wenn ich dies ausdrücklich erkläre signed int auf allen Nummern.

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` Ausführung

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

Testen Sie dies in einer Datei mit dem folgenden Code:

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

Ergebnisse (time ./test):

Signed - real 0m0.949s
Unsigned - real 0m1.174s

Question 2

Ihre Frage ist wirklich faszinierend, da die nicht signierte Version durchweg Code erzeugt, der 10 bis 20 % langsamer ist. Dennoch gibt es mehrere Probleme im Code:

Beide Funktionen kehren zurück 0 zum 2, 3, 5 und 7was falsch ist.
Die Prüfung if (i != num) return 0; else return 1; ist völlig nutzlos, da der Schleifenkörper nur ausgeführt wird i < num. Ein solcher Test wäre für die kleinen Prime-Tests nützlich, aber eine spezielle Hülle ist nicht wirklich nützlich.
die Umwandlungen in der unsignierten Version sind überflüssig.

Benchmarking-Code, der eine Textausgabe an das Terminal erzeugt, unzuverlässig ist, sollten Sie die verwenden clock() Funktion, um CPU-intensive Funktionen ohne dazwischenliegende I/O zu timen.
Der Algorithmus für Prime-Tests ist absolut ineffizient, während die Schleife läuft num / 2 mal statt sqrt(num).

Vereinfachen wir den Code und führen einige präzise Benchmarks aus:

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

Der Code kompiliert mit clang -O2 unter OS/X erzeugt diese Ausgabe:

         isprime_slow:  788.004ms
unsigned_isprime_slow:  965.381ms
         isprime_fast:    0.065ms
unsigned_isprime_fast:    0.089ms

Diese Timings stimmen mit dem beobachteten Verhalten des OP auf einem anderen System überein, zeigen jedoch die dramatische Verbesserung, die durch den effizienteren Iterationstest verursacht wird: 10000 mal Schneller!

Zu der Frage Warum ist die Funktion mit unsigned langsamer?schauen wir uns den generierten Code an (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

Die inneren Schleifen sind sehr ähnlich, gleiche Anzahl von Anweisungen, ähnliche Anweisungen. Hier sind jedoch einige mögliche Erklärungen:

cltd erweitert das Zeichen der eax registrieren Sie sich in der edx registrieren, was eine Befehlsverzögerung verursachen kann, weil eax wird durch die unmittelbar vorhergehende Anweisung modifiziert movl %edi, %eax. Dies würde die signierte Version jedoch langsamer als die unsignierte machen, nicht schneller.
Die anfänglichen Anweisungen der Schleifen könnten für die nicht signierte Version falsch ausgerichtet sein, aber es ist unwahrscheinlich, da eine Änderung der Reihenfolge im Quellcode keine Auswirkungen auf die Zeitabläufe hat.

Obwohl die Registerinhalte für die vorzeichenbehafteten und vorzeichenlosen Divisions-Opcodes identisch sind, ist es möglich, dass die idivl Anweisung dauert weniger Zyklen als die divl Anweisung. Tatsächlich arbeitet die vorzeichenbehaftete Division mit einem Bit weniger Genauigkeit als die vorzeichenlose Division, aber der Unterschied scheint für diese kleine Änderung ziemlich groß zu sein.
Ich vermute, dass mehr Aufwand in die Siliziumimplementierung gesteckt wurde idivl weil vorzeichenbehaftete Unterteilungen häufiger vorkommen als vorzeichenlose Unterteilungen (gemessen an jahrelangen Codierungsstatistiken bei Intel).
Wie von rcgldr kommentiert und sich die Anweisungstabellen für Intel-Prozesse ansieht, benötigt DIV 32 Bit für Ivy Bridge 10 Mikrooperationen, 19 bis 27 Zyklen, IDIV 9 Mikrooperationen, 19 bis 26 Zyklen. Die Benchmark-Zeiten stimmen mit diesen Timings überein. Die zusätzliche Mikrooperation kann auf die längeren Operanden in DIV (64/32 Bit) im Gegensatz zu IDIV (63/31 Bit) zurückzuführen sein.

Dieses überraschende Ergebnis sollte uns einige Lektionen beibringen:

Optimieren ist eine schwierige Kunst, seien Sie bescheiden und zögern Sie.
Korrektheit wird oft durch Optimierungen gebrochen.

Die Wahl eines besseren Algorithmus schlägt die Optimierung bei weitem.
immer Benchmark-Code, vertrauen Sie nicht Ihren Instinkten.

Question 3

Da der Überlauf von vorzeichenbehafteten Ganzzahlen undefiniert ist, kann der Compiler viele Annahmen und Optimierungen für Code treffen, der vorzeichenbehaftete Ganzzahlen enthält. Der Überlauf von vorzeichenlosen Ganzzahlen ist so definiert, dass er umbrochen wird, sodass der Compiler nicht so viel optimieren kann. Siehe auch http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html#signed_overflow und http://www.airs.com/blog/archives/120.

Question 4

Aus Befehlsspezifikation auf AMD/Intel wir haben (für K7):

Instruction Ops Latency Throughput
DIV r32/m32 32  24      23
IDIV r32    81  41      41
IDIV m32    89  41      41

Bei i7 sind Latenz und Durchsatz gleich IDIVL und DIVLgibt es einen kleinen Unterschied für die µops.

Dies kann den Unterschied erklären, da sich -O3-Assembly-Codes nur durch die Signiertheit (DIVL vs. IDIVL) auf meinem Computer unterscheiden.

Question 5

Alternativer Wiki-Kandidatentest, der möglicherweise einen signifikanten Zeitunterschied aufweist.

#include <stdio.h>
#include <time.h>

#define J 10
#define I 5

int main(void) {
  clock_t c1,c2,c3;
  for (int j=0; j<J; j++) {
    c1 = clock();
    for (int i=0; i<I; i++) {
      isprime(294967241);
      isprime(294367293);
    }
    c2 = clock();
    for (int i=0; i<I; i++) {
      isunsignedprime(294967241);
      isunsignedprime(294367293);
    }
    c3 = clock();
    printf("%d %d %d\n", (int)(c2-c1), (int)(c3-c2), (int)((c3-c2) - (c2-c1)));
    fflush(stdout);
  }
  return 0;
}

Beispielausgabe

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

signed int Ausführung

unsigned int Ausführung

`signed int` Ausführung

`unsigned int` Ausführung