Mit einem nutzlosen `if` die Code-Performance vervierfachen

 (purplesyringa.moe)
1 Punkte von GN⁺ 3 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • Durch das Hinzufügen genau einer Bedingung zu der Schleife, die den optimalen Kodierungspfad eines domänenspezifischen Kompressors durchläuft, sank die Laufzeit eines synthetischen Benchmarks von 320µs auf 80µs
  • Da die Speicheradresse in jeder Iteration vom j der vorherigen Iteration abhängt, kann selbst ein einzelner mov-Befehl keine Instruction-Level Parallelism nutzen und bleibt an die Latenz des Speicherzugriffs gebunden
  • Wenn man die Eigenschaft, dass next_j[i][j] meist dem bisherigen j entspricht, in die Sprungvorhersage einfließen lässt, kann die CPU die Abhängigkeit zwischen Iterationen umgehen und mehrere Iterationen spekulativ ausführen
  • Damit der Compiler das semantisch überflüssige if nicht entfernt, wird ein volatile-Cast verwendet. Unter LLVM funktionieren auch [[unlikely]] oder __builtin_expect(..., 0), aber volatile erzeugt besseren Code und wird auch von GCC unterstützt
  • In realistischeren Tests ergab sich eine Leistungssteigerung von etwa dem Zweifachen, möglicherweise wegen nicht optimaler Codegenerierung in LLVM; wenn sich j schwer vorhersagen lässt, kann alternativ pshufb mit 1 Zyklus Latenz verwendet werden

Den optimalen Pfad im Kompressor durchlaufen

  • Die Eingabezeichenkette wird in mehrere Chunks aufgeteilt, und für jeden Chunk muss die kleinste Kodierung gewählt werden
    • Welche Zeichen sich gut komprimieren lassen, unterscheidet sich je nach Kodierung, daher lassen sich Chunk-Grenzen nicht direkt festlegen
    • Der Algorithmus aus dem vorherigen Beitrag wandelt dieses Problem in eine Suche nach dem kürzesten Pfad auf einem Gitter um
  • In jeder Zelle wird die optimale nächste Zelle gespeichert
    • Verfolgt man die Referenzen von der ersten bis zur letzten Zelle, erhält man die optimale Reihenfolge der Kodierungen
  • Die erste Schleife zum Füllen von next_j ist bereits mit SIMD optimiert
    • Der eigentliche Flaschenhals ist die folgende einfache Schleife zum Durchlaufen des Pfads
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • Die Kernoperation ohne den Schreibzugriff, j = next_j[i][j], wird zu einem einzelnen mov-Befehl kompiliert

Abhängigkeiten machen selbst einen einzelnen Befehl langsam

  • Moderne CPUs nutzen Instruction-Level Parallelism, um mehrere Befehle und Arbeiten aus verschiedenen Iterationen gleichzeitig auszuführen
    • Deshalb blockieren in gewöhnlichen Schleifen weder die Prüfung i < n_symbols noch i++ andere Arbeit
  • Abhängige Befehle können jedoch nicht gleichzeitig ausgeführt werden
    • Um die Speicheradresse next_j[i][j] der aktuellen Iteration zu berechnen, wird das j aus der vorherigen Iteration benötigt
    • Die nächste Iteration kann erst beginnen, wenn das Ergebnis der vorherigen vorliegt; dadurch dominiert die Latenz des Speicherzugriffs, selbst wenn sich die Daten im Cache befinden

Sprungvorhersage als Wertspekulation nutzen

  • Bei diesem Kompressor wird erwartet, dass es nicht viele Chunks gibt, daher ist next_j[i][j] in den meisten Fällen gleich dem bisherigen j
  • Man kann der CPU nicht direkt anweisen, die Adresse anhand eines stabilen j vorherzusagen, aber über die Sprungvorhersage lässt sich derselbe Effekt erzielen
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • Wenn die CPU vorhersagt, dass der if-Block nicht ausgeführt wird, nimmt sie an, dass keine iterationsübergreifende Abhängigkeit bei der Aktualisierung von j besteht, und führt mehrere Iterationen spekulativ aus
  • Ist die Bedingung tatsächlich wahr, erfolgt eine Wiederherstellung nach Fehlvorhersage
    • Fälschlich spekulierte Schreibvorgänge werden verworfen
    • Die Ausführung wird mit dem korrekten j neu gestartet
  • Solange sich j kaum ändert, verschiebt sich der Flaschenhals der Schleife von der Latenz zum Durchsatz

Verhindern, dass der Compiler das if entfernt

  • Aus Sicht des Compilers haben der Code mit der zusätzlichen Bedingung und der ursprüngliche Code dieselbe Bedeutung
    • Wenn j im Speicher läge, könnte man unnötige Schreibvorgänge oder Schreibzugriffe auf schreibgeschützten Speicher vermeiden, hier handelt es sich jedoch um einen Registerwert
    • Optimierungen wie Common Subexpression Elimination (CSE) können die Bedingung und doppelte Zugriffe entfernen
  • Übliche Compiler-Hinweise dienen oft dazu, Verzweigungen zu beseitigen; hier soll umgekehrt der verzweigungslose Code als Verzweigungscode erhalten bleiben
  • Dazu wird auf der Zuweisungsseite ein volatile-Cast angewandt, damit die Speicherzugriffe der Bedingungsprüfung und der Zuweisung als unabhängig erscheinen
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • In einer am 13. Juli ergänzten Bestätigung zeigte sich, dass man unter LLVM auch mit [[unlikely]] oder __builtin_expect(..., 0) denselben Effekt erzielen kann, wie ibookstein herausfand
  • Der volatile-Ansatz erzeugt jedoch besseren Code und funktioniert auch mit GCC

Im Benchmark beobachtete Leistungsänderung

  • Im synthetischen Benchmark sank die Laufzeit der Schleife von 320µs auf 80µs, also auf ein Viertel
    • Der Unterschied pro Ausführung ist klein, aber da die Schleife im Komprimierungsvorgang mehrfach läuft, summiert sich der Effekt auf die Gesamtkosten
  • In realistischeren Tests wurde eine Leistungssteigerung von etwa 2× gemessen
    • Möglicherweise lag das an nicht optimaler Codegenerierung von LLVM, trotzdem war der Effekt weiterhin groß genug, um nützlich zu sein

Alternative: eine bitmaskenbasierte Darstellung

  • In diesem Algorithmus kann next_j[i][j] nur einen von zwei Werten annehmen
    • Meist ist es das aktuelle j
    • Der andere Wert ist unabhängig von j und hängt nur von i ab
  • Das Array next_j[i] mit 8 Elementen kann durch ein Paar aus Ersatzwert und Bitmaske ersetzt werden
    • In dieser Darstellung ist das if semantisch tatsächlich nötig, sodass kein volatile-Workaround erforderlich ist
    • Auf x86 kann eine Operation zum Prüfen eines Bits an variabler Position jedoch langsamer sein als ein Vergleich, sodass die Gesamtleistung sogar sinken kann

Wenn sich j nicht vorhersagen lässt

  • Auch der Beitrag zur Beschleunigung des Traversierens verketteter Listen durch Wertspekulation behandelt dieselbe Methode zur Leistungssteigerung
  • Wenn sich j schwer vorhersagen lässt, kann die Vektor-Index-Operation pshufb verwendet werden
    • Die Latenz von pshufb beträgt 1 Zyklus, daher lässt sie sich auch ohne spekulative Ausführung kaum weiter reduzieren
    • Per Vektoroperation können die Pfade für alle möglichen Startwerte von j parallel berechnet werden
    • Es ist auch möglich, die Arbeit auf mehrere Threads zu verteilen und die Ergebnisse anschließend zusammenzuführen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 3 시간 전
Meinungen auf Lobste.rs

  • Das [[unlikely]]-Attribut aus C++20 an eine if-Anweisung zu hängen, scheint auszureichen, damit clang den betreffenden Code nicht entfernt: https://clang.godbolt.org/z/r4xYWfPfe
    Bei anderen Compilern habe ich es nicht überprüft.

    • Beim erneuten Nachsehen stellte sich heraus, dass es in LLVM tatsächlich funktioniert; vermutlich hatte ich es zuerst fälschlicherweise mit GCC getestet, wo es keine Wirkung hat.
      Allerdings verschiebt [[unlikely]] den Code aus dem schnellen Pfad heraus, sodass LLVM wie unten etwas ineffizienten Code erzeugt: 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      Die folgende Form wirkt sinnvoller: 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      Außerdem fügt es der heißen Schleife eine Instruktion hinzu, während es optimiert, um mehrfache Lesezugriffe auf den Wert aus dem Speicher zu vermeiden. Daher bleibt die Technik mit volatile weiterhin nützlich, aber es ist erfreulich, dass auch der ursprüngliche Code unverändert funktionieren kann.

  • Diese Technik wird anderswo Value Speculation genannt: https://mazzo.li/posts/value-speculation.html

    • Nachdem ich diese Methode erneut entwickelt hatte, dachte ich zuerst, dass sie sich auch auf verkettete Listen anwenden ließe, die in einer Arena gespeichert sind; der verlinkte Artikel behandelt genau das, daher habe ich den Link auch in meinen Beitrag aufgenommen.

  • Ich frage mich, ob Entwickler in 2–3 Jahren, wenn ihnen die Ausgaben von LLMs immer gleichgültiger werden, weiterhin Interesse an Blogposts dieser Art haben werden.

    • Schon jetzt interessieren sich nur sehr wenige dafür, und im gesamten Programmierbereich ist es Nischenwissen.
      Für diejenigen, die sich dafür interessieren, ist es aber weiterhin sehr nützlich und ein guter Artikel.
    • Godbolt ist sehr beliebt. Wenn Entwickler, die von LLMs berauscht sind, wegen ihrer Gewohnheit kritisiert werden, keinen Code zu lesen, bringen sie „Schaut ihr euch etwa sogar Assembly an?“ als vermeintlich starkes Gegenargument. Tatsächlich aber prüfen wir Assembly und werden das auch weiterhin tun.
      Entwickler, die Details für unwichtig halten, werden kaum gute Entwickler. So wie ein hervorragender Bauingenieur bei Großprojekten auch auf Schrauben und Muttern achtet, muss auch ein hervorragender Entwickler bis in kleine Details vordringen. Das Ganze besteht aus Details; wer Wert auf das legt, was er baut, kann dem nicht ausweichen.
    • Ich sehe keinen grundlegenden Unterschied zu heute. Auch derzeit interessiert sich die Mehrheit nicht für die Compiler-Ausgabe von Code, den Menschen geschrieben haben.
      Vielleicht werden noch weniger Menschen die Compiler-Ausgabe von KI-generiertem Code anschauen, aber die Grundkonstellation dürfte sich nicht ändern.
    • Was sich ändert, ist weniger das Vorhandensein von Interesse als vielmehr eine Neuordnung der Optimierungsprioritäten.
      Vor 10 Jahren hätte man bei einem etwas langsamen Bash-Skript wohl nicht zuerst über Parallelität auf Instruktionsebene oder CPU-Branch-Prediction nachgedacht. Es kann einen performancekritischen Teil geben, der in einer kompilierbaren und optimierbaren Sprache geschrieben ist; darin einen heißen Pfad, den man im Detail betrachten sollte; und darin wiederum ein oder zwei heiße Schleifen, bei denen es sich lohnt, Vektorisierung oder Unterschiede im Verhalten moderner CPUs zu prüfen.
      Auch beim Einsatz von LLMs lohnt es sich ausnahmsweise, die aus Performance-Sicht heißesten Stellen direkt zu überprüfen. Selbst wenn man bewusst die niedrigere Qualität des Ergebnisses in Kauf nimmt oder mit einem LLM 70 % erstellt und die restlichen 30 % von Hand korrigiert, und sich das vielleicht auf 85:15 verbessert, behandelt dieser Artikel weiterhin einen Detailbereich auf Top-1-%-Niveau.
    • Da ich kein C++ schreibe, betrifft es mich in diesem Sinne auch heute nicht direkt, aber ich habe es dennoch mit Interesse gelesen, und ich denke, solche Inhalte werden auch in 2–3 Jahren noch spannend sein.