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 b
es zu Bit-Hacks kompiliert, während c
es entweder ziemlich unoptimiert war oder auf einen anderen Fall reduziert wurde, a
abhä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 inline
der Nachschlagetabelle etwas schneller : Probieren Sie es online aus!
quelle
-O3
kompiliert, und es wurdec
zu etwas kompiliert , das wahrscheinlich schlimmer ist alsa
oderb
(c
hatte zwei bedingte Sprünge plus ein paar Bitmanipulationen im Vergleich zu nur einem bedingten Sprung und einer einfacheren Bitmanipulation fürb
), 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.if
schlägt aber immer nochswitch
(seltsamerweise wird die Suche noch schneller) [TIO folgt]Antworten:
Wenn Sie alle Fälle explizit aufzählen, ist gcc sehr effizient:
wird nur in einem einfachen indizierten Zweig kompiliert:
Beachten Sie, dass
default:
gcc , wenn es nicht kommentiert ist, zu seiner verschachtelten Zweigversion zurückkehrt.quelle
pslld
/psrad
oder deren 8-Wege-AVX2-Äquivalenten geeignet . Viel hängt von den anderen Besonderheiten Ihres Codes ab.C-Compiler haben spezielle Fälle für
switch
, weil sie erwarten, dass Programmierer die Redewendung verstehenswitch
und sie ausnutzen.Code wie:
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
if
Anweisungen 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 vonif
Aussagen möglich ist, ist astronomisch. Die Analyse ist sowohl kompliziert als auch wahrscheinlich negativ (wie in: "Nein, wir können dieseif
s nicht in a umwandelnswitch
").quelle
if
wenn es überhaupt möglich ist.static
und verwenden Sie C99-Initialisierer, wenn Sie etwas klarer machen möchten, was Sie zuweisen, und es ist eindeutig vollkommen in Ordnung.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 Fallenum
Werte, keine nackten ganzen Zahlen, so dass bitweise Hacks nicht sehr wartbar sind.Der folgende Code berechnet Ihre Suche verzweigungsfrei, LUT-frei, in ~ 3 Taktzyklen, ~ 4 nützlichen Anweisungen und ~ 13 Bytes
inline
hochverfügbaren x86-Maschinencodes.Dies hängt von der Ganzzahldarstellung eines 2er-Komplements ab.
Sie müssen jedoch sicherstellen, dass die
u32
unds32
typedefs wirklich auf vorzeichenlose und vorzeichenbehaftete 32-Bit-Ganzzahltypen verweisen.stdint.h
Typenuint32_t
undint32_t
wäre geeignet gewesen, aber ich habe keine Ahnung, ob der Header für Sie verfügbar ist.Ü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:
Wenn Sie sie mit dem Index 0 platzieren, der dem höchstwertigen Bit am nächsten liegt, wird durch eine einzelne Verschiebung von
2*num
das 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 erweitertint
, wodurch der Trick abgeschlossen wird.quelle
magic
Kommentar zu tun, in dem erklärt wird, wie es regeneriert werden kann. Können Sie erklären, wie Sie darauf gekommen sind?!!(12336 & (1<<x))-!!(771 & (1<<x));
Sie können den gleichen Effekt nur mit Arithmetik erzeugen:
Auch wenn dies technisch gesehen immer noch eine (bitweise) Suche ist.
Wenn das oben genannte zu arkan erscheint, können Sie auch Folgendes tun:
quelle