Warum C-Compiler den Switch optimieren und wenn anders

9

Ich habe kürzlich an einem persönlichen Projekt gearbeitet, als ich auf ein seltsames Problem gestoßen bin.

In einer sehr engen Schleife habe ich eine Ganzzahl mit einem Wert zwischen 0 und 15. Ich muss -1 für die Werte 0, 1, 8 und 9 und 1 für die Werte 4, 5, 12 und 13 erhalten.

Ich wandte mich an Godbolt, um einige Optionen zu überprüfen, und war überrascht, dass der Compiler eine switch-Anweisung nicht wie eine if-Kette optimieren konnte.

Der Link ist hier: https://godbolt.org/z/WYVBFl

Der Code lautet:

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}

int b(int num) {
    num &= 0xF;

    if (num == 0 || num == 1 || num == 8 || num == 9) 
        return -1;

    if (num == 4 || num == 5 || num == 12 || num == 13)
        return 1;

    return 0;
}

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
        default:
            return 0;
    }
}

Ich hätte gedacht, dass b und c die gleichen Ergebnisse liefern würden, und ich hatte gehofft, dass ich die Bit-Hacks lesen könnte, um selbst eine effiziente Implementierung zu erzielen, da meine Lösung (die switch-Anweisung - in einer anderen Form) ziemlich langsam war.

Seltsamerweise wurde bes zu Bit-Hacks kompiliert, während ces entweder ziemlich unoptimiert war oder auf einen anderen Fall reduziert wurde, aabhängig von der Zielhardware.

Kann jemand erklären, warum es diese Diskrepanz gibt? Was ist der "richtige" Weg, um diese Abfrage zu optimieren?

BEARBEITEN:

Klärung

Ich möchte, dass die Switch-Lösung die schnellste oder eine ähnlich "saubere" Lösung ist. Beim Kompilieren mit Optimierungen auf meinem Computer ist die if-Lösung jedoch erheblich schneller.

Ich habe ein schnelles Programm geschrieben, um zu demonstrieren, und TIO hat die gleichen Ergebnisse wie vor Ort: Probieren Sie es online aus!

Mit static inlineder Nachschlagetabelle etwas schneller : Probieren Sie es online aus!

LambdaBeta
quelle
4
Ich vermute, die Antwort lautet "Compiler treffen nicht immer vernünftige Entscheidungen". Ich habe gerade Ihren Code zu einem Objekt mit GCC 8.3.0 mit -O3kompiliert, und es wurde czu etwas kompiliert , das wahrscheinlich schlimmer ist als aoder b( chatte zwei bedingte Sprünge plus ein paar Bitmanipulationen im Vergleich zu nur einem bedingten Sprung und einer einfacheren Bitmanipulation für b), aber immer noch besser als naive Item-by-Item-Tests. Ich bin mir nicht sicher, wonach Sie hier wirklich fragen. Die einfache Tatsache ist, dass ein optimierender Compiler jedes dieser Elemente in eines der anderen umwandeln kann, wenn er dies wünscht, und es gibt keine festen Regeln dafür, was er tun oder nicht tun wird.
ShadowRanger
Mein Problem ist, dass ich es schnell haben muss, aber die if-Lösung ist nicht übermäßig wartbar. Gibt es eine Möglichkeit, den Compiler dazu zu bringen, eine sauberere Lösung ausreichend zu optimieren? Kann jemand erklären, warum dies in diesem Fall nicht möglich ist?
LambdaBeta
Ich würde damit beginnen, zumindest die Funktionen als statisch zu definieren oder sie noch besser zu definieren.
Wildplasser
@ Wildplasser beschleunigt es, ifschlägt aber immer noch switch(seltsamerweise wird die Suche noch schneller) [TIO folgt]
LambdaBeta
@LambdaBeta Es gibt keine Möglichkeit, einen Compiler anzuweisen, auf eine bestimmte Weise zu optimieren. Sie werden feststellen, dass clang und msvc für diese völlig unterschiedlichen Code generieren. Wenn es dich nicht interessiert und du nur willst, was auf gcc am besten funktioniert, dann wähle das aus. Compiler-Optimierungen basieren auf Heuristiken, und diese liefern nicht in allen Fällen die optimale Lösung. Sie versuchen im Durchschnitt gut zu sein, nicht in allen Fällen optimal.
Cubic

Antworten:

6

Wenn Sie alle Fälle explizit aufzählen, ist gcc sehr effizient:

int c(int num) {
    num &= 0xF;
    switch (num) {
        case 0: case 1: case 8: case 9: 
            return -1;
        case 4: case 5: case 12: case 13:
            return 1;
            case 2: case 3: case 6: case 7: case 10: case 11: case 14: case 15: 
        //default:
            return 0;
    }
}

wird nur in einem einfachen indizierten Zweig kompiliert:

c:
        and     edi, 15
        jmp     [QWORD PTR .L10[0+rdi*8]]
.L10:
        .quad   .L12
        .quad   .L12
        .quad   .L9
        .quad   .L9
        .quad   .L11
        .quad   .L11
        .quad   .L9
        .quad   .L9
        .quad   .L12
etc...

Beachten Sie, dass default:gcc , wenn es nicht kommentiert ist, zu seiner verschachtelten Zweigversion zurückkehrt.

Alain Merigot
quelle
1
@LambdaBeta Sie sollten in Betracht ziehen, meine Antwort nicht zu akzeptieren und diese zu akzeptieren, da moderne Intel-CPUs zwei parallel indizierte Speicherlesevorgänge / -zyklen ausführen können, während der Durchsatz meines Tricks wahrscheinlich 1 Suche / Zyklus beträgt. Auf der anderen Seite ist mein Hack vielleicht eher für eine 4-Wege-Vektorisierung mit SSE2 pslld/ psradoder deren 8-Wege-AVX2-Äquivalenten geeignet . Viel hängt von den anderen Besonderheiten Ihres Codes ab.
Iwillnotexist Idonotexist
4

C-Compiler haben spezielle Fälle für switch, weil sie erwarten, dass Programmierer die Redewendung verstehen switchund sie ausnutzen.

Code wie:

if (num == 0 || num == 1 || num == 8 || num == 9) 
    return -1;

if (num == 4 || num == 5 || num == 12 || num == 13)
    return 1;

würde die Überprüfung durch kompetente C-Codierer nicht bestehen; drei oder vier Rezensenten würden gleichzeitig ausrufen "das sollte ein sein switch!"

Für C-Compiler lohnt es sich nicht, die Struktur von ifAnweisungen für die Konvertierung in eine Sprungtabelle zu analysieren . Die Bedingungen dafür müssen genau richtig sein, und das Ausmaß der Variation, die in einer Reihe von ifAussagen möglich ist, ist astronomisch. Die Analyse ist sowohl kompliziert als auch wahrscheinlich negativ (wie in: "Nein, wir können diese ifs nicht in a umwandeln switch").

Kaz
quelle
Ich weiß, deshalb habe ich mit dem Schalter angefangen. Die if-Lösung ist in meinem Fall jedoch deutlich schneller. Ich frage im Grunde, ob es eine Möglichkeit gibt, den Compiler davon zu überzeugen, eine bessere Lösung für den Switch zu verwenden, da er das Muster im ifs finden konnte, aber nicht im Switch. (Ich mag die Wenns nicht speziell, weil sie nicht so klar oder wartbar sind)
LambdaBeta
Upvoted aber nicht akzeptiert, da das Gefühl genau der Grund ist, warum ich diese Frage gestellt habe. Ich möchte den Schalter benutzen, aber er ist in meinem Fall zu langsam. Ich möchte das vermeiden, ifwenn es überhaupt möglich ist.
LambdaBeta
@ LambdaBeta: Gibt es einen Grund, die Nachschlagetabelle zu vermeiden? Machen Sie es staticund verwenden Sie C99-Initialisierer, wenn Sie etwas klarer machen möchten, was Sie zuweisen, und es ist eindeutig vollkommen in Ordnung.
ShadowRanger
1
Ich würde anfangen, zumindest das niedrige Bit zu verwerfen, damit der Optimierer weniger Arbeit zu erledigen hat.
R .. GitHub STOP HELPING ICE
@ShadowRanger Leider ist das immer noch langsamer als das if(siehe Bearbeiten). @R .. Ich habe die vollständige bitweise Lösung für den Compiler ausgearbeitet, die ich derzeit verwende. Leider sind dies in meinem Fall enumWerte, keine nackten ganzen Zahlen, so dass bitweise Hacks nicht sehr wartbar sind.
LambdaBeta
4

Der folgende Code berechnet Ihre Suche verzweigungsfrei, LUT-frei, in ~ 3 Taktzyklen, ~ 4 nützlichen Anweisungen und ~ 13 Bytes inlinehochverfügbaren x86-Maschinencodes.

Dies hängt von der Ganzzahldarstellung eines 2er-Komplements ab.

Sie müssen jedoch sicherstellen, dass die u32und s32typedefs wirklich auf vorzeichenlose und vorzeichenbehaftete 32-Bit-Ganzzahltypen verweisen. stdint.hTypen uint32_tund int32_twäre geeignet gewesen, aber ich habe keine Ahnung, ob der Header für Sie verfügbar ist.

const int lookup[16] = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};

int a(int num) {
    return lookup[num & 0xF];
}


int d(int num){
    typedef unsigned int u32;
    typedef signed   int s32;

    // const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
    // 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
    // Hexadecimal:                   F     0     5     0     F     0     5     0
    const u32 K = 0xF050F050U;

    return (s32)(K<<(num+num)) >> 30;
}

int main(void){
    for(int i=0;i<16;i++){
        if(a(i) != d(i)){
            return !0;
        }
    }
    return 0;
}

Überzeugen Sie sich hier: https://godbolt.org/z/AcJWWf


Bei der Auswahl der Konstante

Ihre Suche umfasst 16 sehr kleine Konstanten zwischen -1 und +1 einschließlich. Jedes passt in 2 Bits und es gibt 16 davon, die wir wie folgt auslegen können:

// const int lookup[16]     = {-1, -1, 0, 0, 1, 1, 0, 0, -1, -1, 0, 0, 1, 1, 0, 0};
// 2-bit signed 2's complement: 11 11 00 00 01 01 00 00 11 11 00 00 01 01 00 00
// Hexadecimal:                   F     0     5     0     F     0     5     0
u32 K = 0xF050F050U;

Wenn Sie sie mit dem Index 0 platzieren, der dem höchstwertigen Bit am nächsten liegt, wird durch eine einzelne Verschiebung von 2*numdas Vorzeichenbit Ihrer 2-Bit-Nummer in das Vorzeichenbit des Registers eingefügt. Wenn Sie die 2-Bit-Zahl um 32-2 = 30-Bit-Vorzeichen nach rechts verschieben, wird sie vollständig erweitert int, wodurch der Trick abgeschlossen wird.

Iwillnotexist Idonotexist
quelle
Dies ist möglicherweise der sauberste Weg, dies mit einem magicKommentar zu tun, in dem erklärt wird, wie es regeneriert werden kann. Können Sie erklären, wie Sie darauf gekommen sind?
LambdaBeta
Akzeptiert, da dies "sauber" gemacht werden kann und gleichzeitig schnell ist. (über etwas Präprozessor-Magie :) < xkcd.com/541 >)
LambdaBeta
1
!!(12336 & (1<<x))-!!(771 & (1<<x));
Schlägt
0

Sie können den gleichen Effekt nur mit Arithmetik erzeugen:

// produces : -1 -1 0 0 1 1 0 0 -1 -1 0 0 1 1 0 0 ...
int foo ( int x )
{
    return 1 - ( 3 & ( 0x46 >> ( x & 6 ) ) );
}

Auch wenn dies technisch gesehen immer noch eine (bitweise) Suche ist.

Wenn das oben genannte zu arkan erscheint, können Sie auch Folgendes tun:

int foo ( int x )
{
    int const y = x & 6;
    return (y == 4) - !y;
}
KevinZ
quelle