{n}-mal schneller als C

 (owen.cafe)
1 Punkte von GN⁺ 2023-07-07 | 1 Kommentare | Auf WhatsApp teilen
  • Selbst bei einer kleinen C-Schleife ist die Compiler-Ausgabe nicht immer optimal; durch direktes Feintuning von x86_64-Assembly wurde eine Version ohne bedingte Verzweigungen erstellt, die 6,73-mal schneller als die Ausgabe von clang ist
  • Die Zielfunktion behandelt in einem String 's' als +1, 'p' als -1 und '\0' als Ende; die Ausgabe von clang 16 teilt diesen Ablauf in drei bedingte Verzweigungen auf
  • Durch das Ändern der Verzweigungsreihenfolge, das Umordnen von Basic Blocks und das Ersetzen von Sprüngen durch Arithmetik sank die Laufzeit von 3,23 s auf 2,87 s; damit wurde auf dieser Stufe dieselbe Geschwindigkeit wie mit GCC 12 erreicht
  • Die schnellste Version wählt mit cmove für jedes Zeichen einen Additionswert von 0, 1 oder -1 und führt dann immer add aus; sie erreichte 0,48 s und einen Durchsatz von 1,94 GiB/s
  • Gebenchmarkt wurde auf einem AMD Ryzen 5 5625U und Linux 6.1.33; verarbeitet wurde 1000-mal eine Liste von 1 Million zufälligen 'p'/'s'-Zeichen, und aus mehreren Läufen wurde jeweils das beste Ergebnis verwendet

Zielfunktion und Compiler-Ausgabe im Experiment

  • Die Zielfunktion erhöht einen String-Zeiger Schritt für Schritt und aktualisiert je nach Zeichen den Integer res
    • 's': res += 1
    • 'p': res -= 1
    • '\0': res zurückgeben
    • andere Zeichen: keine Änderung
  • Da die Funktion klein ist, ging man zunächst davon aus, dass gcc oder clang sie ziemlich gut, vielleicht sogar optimal, optimieren könnten
  • Das von clang erzeugte anfängliche Assembly teilt die vier Fälle in drei bedingte Verzweigungen (je, je, jne) auf
    • Start mit res = 0
    • Zeichen lesen und zuerst auf '\0' prüfen
    • danach Vergleiche mit 'p' und 's'
  • Anfangsergebnis von clang
    • Laufzeit: 3,23 s
    • Durchsatz: 295,26 MiB/s
  • GCC erzeugte etwas mehr Code, war aber geringfügig schneller

Häufige Zeichen vor der seltenen Abbruchbedingung prüfen

  • Die Schleife endet nur beim Null-Terminierungszeichen '\0', und in dieser Funktion kann dieses Zeichen höchstens einmal auftreten
  • Die clang-Ausgabe prüft '\0' jedoch zuerst, sodass bei jedem 'p'- und 's'-Zeichen erst die Abbruchbedingung getestet wird
  • Die erste manuelle Änderung bestand darin, die Vergleichsreihenfolge zu drehen und zuerst 'p' und 's' zu prüfen
  • Ergebnis
    • Laufzeit: 3,10 s
    • Beschleunigung: 1,04-mal
    • Durchsatz: 307,64 MiB/s

Basic Blocks umordnen und Sprünge reduzieren

  • Da beide häufigen Fälle, 'p' und 's', zurück zum Schleifenanfang springen, kann man die Anzahl der Verzweigungen verringern, indem man einen der Blöcke über der Schleife platziert
  • Wenn der 's'-Block direkt vor der Schleife liegt, fließt die Ausführung nach der Verarbeitung von 's' ohne zusätzlichen Sprung in die Schleife zurück
  • Dafür muss beim Funktionsstart einmal in die Schleife gesprungen werden, um den 's'-Block zu überspringen
    • Dieser Sprung am Funktionsanfang tritt nur einmal auf
    • 's' kann dagegen viele Male vorkommen, daher ist der Trade-off akzeptabel
  • Ergebnis
    • Laufzeit: 2,98 s
    • Gesamtbeschleunigung: 1,08-mal
    • Durchsatz: 320,02 MiB/s

Einen unbedingten Sprung per Arithmetik eliminieren

  • Um den unbedingten jmp aus dem p:-Block zurück in die Schleife zu entfernen, wurde Arithmetik verwendet
  • Eine einmalige Verringerung lässt sich mit sub eax, 2 gefolgt von inc eax mit demselben Effekt ausdrücken, sodass die Ausführung nach der 'p'-Verarbeitung in den 's'-Block weiterfallen kann
  • Dadurch wurde ein weiterer Verzweigungsbefehl entfernt
  • Ergebnis
    • Laufzeit: 2,87 s
    • Gesamtbeschleunigung: 1,12-mal
    • Durchsatz: 332,29 MiB/s
  • Die Leistung auf diesem Stand entsprach dem von GCC 12 erzeugten Code
    • GCC-12-Code lief ebenfalls in 2,87 s
    • Die handgeschriebene Version bestand aus 13 Instruktionen
    • Die GCC-Ausgabe aus 19 Instruktionen
    • Der GCC-Code scheint die Schleife unrolled und Case-Blöcke teilweise wiederverwendet zu haben

Bedingte Verzweigungen durch cmove ersetzen

  • Wenn bedingte Verzweigungen der Flaschenhals sind, kann man sie selbst eliminieren, statt sich auf den Branch Predictor zu verlassen
  • Die schnellste Version verwendet cmove, also einen bedingten Move bei Gleichheit
  • Die Logik ist einfach
    • Standardwert ist 0
    • Wenn das aktuelle Zeichen 's' ist, wird 1 gewählt
    • Wenn das aktuelle Zeichen 'p' ist, wird -1 gewählt
    • In jeder Iteration wird der ausgewählte Wert immer zu res addiert
  • Dadurch verschwinden viele Pfeile aus dem Control-Flow-Graphen
  • Ergebnis
    • Laufzeit: 0,48 s
    • Gesamtbeschleunigung: 6,73-mal
    • Durchsatz: 1,94 GiB/s
  • Bei diesem kompakten C-Schleifen-Assembly war also eine mehr als 6-fache Beschleunigung durch Optimierungen möglich, die der Compiler nicht automatisch vorgenommen hatte

Versuch, Register zu sparen, und weitere erfolglose Experimente

  • Es wurde auch eine Version getestet, die sete auf x86_64 verwendet, um ein 1-Byte-Register bedingt auf 0 oder 1 zu setzen
  • Diese Version vermeidet die Verwendung von r8d, war aber langsamer als die reine cmov-Variante
  • Ergebnis
    • Laufzeit: 0,51 s
    • Gesamtbeschleunigung: 6,33-mal
    • Durchsatz: 1,83 GiB/s
  • Weniger Register zu verwenden oder statt 32-Bit-Operationen 8-Bit-Operationen einzusetzen, machte den Code also nicht schneller
  • Auch weitere Versuche verschlechterten die Leistung
    • Loop-Unrolling der besten Version: langsamer
    • Ausrichtung des Schleifenanfangs auf eine 16-Byte-Grenze: langsamer
    • Im GNU-Assembler kann man mit .align <bytes> vor einem Label nop-Instruktionen einfügen

Benchmark-Umgebung und Code

  • Die Codeliste befindet sich auf GitHub
  • Benchmark-Umgebung
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • CPU-Familie 25, 6 Kerne, 2 Threads pro Kern, 1 Sockel
    • clang: 16.0.1
    • gcc: 12.2.0
  • Die C-Version wurde mit -march=native kompiliert, damit Code erzeugt wird, der auf die konkrete CPU zugeschnitten ist
  • Der Benchmark lief auf einer Liste von 1 Million Zeichen, bestehend aus zufälligen 'p' und 's'
    • Jede Funktionsvariante verarbeitete diese Liste 1000-mal
    • Jede Variante wurde mehrfach ausgeführt, und das beste Ergebnis wurde ausgewählt
  • Als Folgeartikel ist part two verlinkt

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-07-07
Meinungen auf Hacker News

  • Die richtige Schlussfolgerung ist nicht handgeschriebenes Assembly ist 6-mal schneller als C, sondern eher: Sprünge können deutlich langsamer sein als bedingte Arithmetik.
    Auch in C lässt sich derselbe Effekt leicht erzielen, wenn man kein switch verwendet, sondern ein oder zwei ifs. Als die C-Funktion so geändert wurde, dass sie bei s inkrementiert, bei p dekrementiert und bei \0 beendet, wurde sie 5,5-mal schneller; im Beispiellauf sank die Zeit von 3,58 Sekunden auf 0,65 Sekunden.

    • Gut. In Teil 2 wurde C neu geschrieben und eine 12-fache Beschleunigung erreicht: https://owen.cafe/posts/the-same-speed-as-c/
      Wie andere gesagt haben, kann man nach Anpassung der Eingabe den Algorithmus auch vektorisieren. Ich habe das als Übung zu Lernzwecken gesehen und hoffe ernsthaft, dass niemand ohne ausreichenden Grund auf Assembly heruntergeht.
    • Sprünge sind langsamer als bedingte Arithmetik stimmt, wenn die Sprünge nicht vorhersagbar sind. Wenn Sprünge vorhersagbar sind, sind Sprünge schneller.
      Auch Linus hat früher ausführlich geschrieben, dass cmov bei vorhersagbaren Branches nicht nützlich ist: https://yarchive.net/comp/linux/cmov.html
    • Ich frage mich, welche GCC-Version verwendet wird. Unter Ubuntu und Windows kam jeweils dieselbe Performance heraus, und mit gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 lagen lone und ltwo beide bei etwa 3,58 Sekunden.
    • Ich frage mich, ob es immer schneller ist, ein switch durch mehrere ifs zu ersetzen. Außerdem, ab wie vielen Fällen switch schneller wird; wenn das konsistent ist, sollte es wohl in die Compiler-Optimierung einfließen.
    • Man könnte meinen, dass auch der Compiler eine solche Transformation beherrschen sollte.

  • Ich finde nicht, dass der ursprüngliche Code besonders compilerfreundlich geschrieben ist. Wenn man ihn etwa als result += *s == 's'; result -= *s == 'p'; schreibt, erzeugt der Compiler passenden branchlosen sete/cmov-Code, der fast dieselbe Geschwindigkeit wie das optimierte Assembly im Artikel erreicht.
    Loop-Unrolling oder Vektorisierung macht er allerdings nicht. Wenn man die Stringgröße separat übergibt und mit bekannter size iteriert, kennt der Compiler die Loop-Größe, kann unrollen und, wenn möglich, auch AVX-512-Instruktionen verwenden. Bei großen Eingaben ist das deutlich schneller, aber ich habe keine Lust, es selbst zu benchmarken. Wenn C-Programmierer die Stringlänge nicht verfolgen, ist das ihre Sache, aber ich finde, das sollte man wirklich nicht tun: https://godbolt.org/z/rde51zMd8

    • Die compilerfreundliche Version steht in Teil 2: https://owen.cafe/posts/the-same-speed-as-c/
      Diese Version erreicht 3,88 GiB/s. Ich bin absichtlich nicht bis zur Vektorisierung gegangen, sondern wollte den Problemumfang klein halten und die Assembly-Tipps und -Tricks aus dem Artikel zeigen. Später wäre noch ein Artikel möglich, in dem der Eingabestring gepaddet und der Algorithmus vektorisiert wird.
    • Im Code fehlt eine wichtige Zeile: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • In Nim scheint es sich ebenfalls so auslösen zu lassen: {.overflowChecks:off.} aktivieren, über input iterieren und bei 's' == c inkrementieren, bei 'p' == c dekrementieren.
      Auf einem Apple M1 ergab das etwa eine 5-fache Beschleunigung; mit aktivierten Overflow-Checks wurde es gegenüber der Standard-C-Version nur etwa 2-mal schneller. Es ist immer gut, Muster zu kennen, die SIMD-Optimierungen begünstigen.
    • Bedeutet „das sollte man wirklich nicht tun“, dass man die Stringlänge nicht verfolgen sollte?

  • Aus der Perspektive von jemandem, der ziemlich nah an einem Optimierungsexperten ist, würde ich dieses Problem völlig anders lösen. Auf meinem Rechner lag die anfängliche C-Version bei 389 MB pro Sekunde; wenn das Assembly aus dem Artikel dieselbe 6,2-fache Verbesserung bringt, wären das etwa 2,4 GB pro Sekunde.
    Bei langen Buffern kommt diese C++-Version auf meinem Rechner auf über 24 GB pro Sekunde: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    Ohne Assembly, auf Basis von AVX2-Intrinsics, ist sie 61-mal schneller als die ursprüngliche Version.

    • Interessant. Statt Zähler in ymm-Registern zu halten, könnte man vermutlich movemask und popcnt verwenden, um den Prolog zu vektorisieren.
      Der Code ist noch nicht getestet und braucht Benchmarks, aber der Ansatz scheint möglich: Masken für s, p und \0 bilden und mit tzcnt sowie bzhi die Bits bis vor das Stringende zählen.
    • Aus Neugier würde ich gern wissen, ob das auch mit std::experimental::simd möglich ist: https://en.cppreference.com/w/cpp/experimental/simd
    • Es wäre wohl gut, das in einer Form neu zu schreiben, die mit dem Repository von @414owen kompatibel ist.
    • Ich frage mich, welche Materialien gut sind, um AVX zu lernen und zu üben.

  • Dieser Code scheint wirklich gut zu SIMD zu passen. Wenn man den Prototyp so ändern kann, dass er eine explizite Länge annimmt, ist es einfach, jeweils 16 Byte zu lesen und zu verarbeiten.
    Man kann die Vergleichsergebnisse direkt addieren und subtrahieren, und allein der Aufruf von strlen() am Funktionsanfang, um eine explizite Länge zu erhalten, dürfte sich vermutlich lohnen.

  • Ich habe schnell eine RISC-V-vektorisierte Implementierung erstellt. Sie liest den String mit rvv, sucht die Position von \0 und zählt dann die Anzahl von s und p mit vcpop.
    Auf einem Mangopi MQ Pro (C906, rv64gc + rvv 0.7.1, 128-Bit-Vektorlänge) kam switch auf 0,19 Bytes/Cycle, die Tabellen-C-Implementierung auf 0,17 Bytes/Cycle und rvv auf 1,57 Bytes/Cycle; nach etwa 30 KiB fiel es auf 1,35. Wenn man den Pointer an Pages ausrichtet und vl nicht größer als die Page-Größe macht, sind 2/1,7 Bytes/Cycle möglich.

    • Um vollständig korrekt zu sein, müssten die Loads fault-only-first loads sein. rvv hat diese Funktion; andernfalls kann es fehlschlagen, wenn das Nullbyte direkt vor dem Ende des zugewiesenen Speichers liegt.

  • Das wirkt wie eine Eigenschaft, die speziell für die x86-Architektur typisch ist. Weil die Kosten dafür, keinen Branch zu nehmen, so extrem niedrig sind, wirken Branches relativ teuer: https://wordsandbuttons.online/challenge_your_performance_in...
    Auf anderen Prozessoren muss das aber nicht gelten: https://wordsandbuttons.online/using_logical_operators_for_l...
    Die größere Frage ist, wozu man C im Allgemeinen braucht. Wenn man etwas von Hand so anpassen will, dass es auf bestimmter Hardware optimal läuft, ist C das falsche Werkzeug; dann braucht man Assembly und ein brauchbares Makrosystem. Das ursprüngliche Ziel von C war, systemnahen Code leichter von einer Plattform auf eine andere zu übertragen, und Effizienzverluste waren dabei einkalkuliert. Es ist ähnlich, als würde man ein Hindi-Gedicht nicht ins Urdu übersetzen, sondern es in Esperanto schreiben und dann automatisch in die gewünschte Sprache übersetzen lassen. Man bekommt keine zwei großartigen Gedichte, sondern schnell zwei minderwertige Übersetzungen — und genau das ist die Rolle von C.

  • Wenn man mit FDO/PGO baut, können Branches und Blöcke definitiv umsortiert werden. Ohne FDO kann der Compiler nämlich nicht wissen, wie häufig welcher Branch genommen wird. In manchen Fällen kann FDO auch cmov aktivieren.
    Ob cmov effektiver ist als ein normales test/jump, hängt allerdings stark davon ab, wie gut der Branch vorhersagbar ist; üblicherweise funktioniert cmov besser, wenn der Branch sehr schlecht vorhersagbar ist. Wenn cmov das Ganze um den Faktor 6 beschleunigt hat, vermute ich, dass die Testeingabe fast ausschließlich aus zufälligen Strings aus s und p bestand. Das ist nicht falsch, aber es nutzt eine im Text nicht erwähnte Eigenschaft der Daten speziell für den Benchmark aus, weshalb der Artikel etwas missverständlich wirken kann.

    • Der Testcode ist hier: https://github.com/414owen/blog-code/blob/master/02-the-same...
      Es wird zufällig 's' oder 'p' gewählt, und außer 's', 'p' und dem abschließenden Nullbyte können keine Zeichen vorkommen. Wenn man diese Eingabeeigenschaft kennt, sind auch übermäßig clevere Optimierungen wie result += (1 | *s++) - 'r'; möglich. Das ist zu schlauer Code, zeigt aber perfekt den Punkt, dass hier Dateneigenschaften ausgenutzt werden.
    • \0 kann im String höchstens einmal vorkommen, weil die Funktion dann zurückkehrt, andere Zeichen dagegen mehrfach. Diese Information scheint etwas zu sein, auf das der Compiler auch ohne PGO zugreifen kann.
      Natürlich hilft PGO, und auf meinem Rechner komme ich auf 2,80 Sekunden, was besser ist als der Code am Ende des Abschnitts Rearranging blocks. Die Eingabe ist unter Benchmarking setup beschrieben und liegt auch im Repository: https://github.com/414owen/blog-code/blob/master/01-six-time...
      Im am Ende verlinkten zweiten Teil wird der C-Code so schnell wie möglich gemacht und schlägt sämtlichen Assembly-Code aus diesem Artikel. Ich habe nie behauptet, dass Assembly zu schreiben unbedingt eine gute Idee sei; ich sehe Optimierung und das Entschlüsseln von Compiler-Ausgaben eher als interessante Herausforderung und gute Lerngelegenheit.

  • Ich glaube, ich habe es schneller gemacht als der Artikel und der Folgeartikel. Allerdings um den Preis, dass es auf Strings spezialisiert ist, die nur aus 's' und 'p' bestehen.
    Da der Benchmark ebenfalls nur Strings testet, die ausschließlich aus 's' und 'p' bestehen, halte ich das für fair. Der Kernpunkt ist: Wenn das nächste Zeichen s ist, möchte man res um 1 erhöhen, aber res += c - 'r' ergibt bei s zwar 1, bei p aber -2 und scheitert damit. Betrachtet man jedoch 'p' - 'r' als unsigned Integer, entsteht ein Underflow und das Carry-Flag wird gesetzt; adc auf x64 addiert zwei Register zusammen mit dem Carry-Flag. So kann man zwei cmp, cmov durch ein sub, adc ersetzen. Diese Version war 1,08-mal schneller als die C-Version aus dem Folgeartikel und 1,66-mal schneller als das bisherige x64-7. Mit SWAR/SIMD ließe sich das natürlich noch weiter verbessern.

    • Interessanter Ansatz. Ich hätte wohl klar dazuschreiben sollen, dass das eher einfache Assembly in 02-the-same-speed-as-c/loop-5.x64.s die schnellste Version ist, die ich habe.
      Auf meinem Rechner braucht loop-5.x64.s 0,244 Sekunden, die obige Implementierung 0,422 Sekunden. Warum dieser Unterschied genau entsteht, weiß ich nicht; vom Ansehen her wirkt die obige Implementierung schneller. Deshalb sollte man immer auf der Hardware benchmarken, auf der es tatsächlich laufen soll.
    • Noch einfacher: Man summiert alle Elemente des Arrays, zieht am Ende 'p' * len ab und teilt durch ('s' - 'p'), um die Anzahl der s zu erhalten. Die Anzahl der p ist dann len - s_count.
      Auch die anfängliche Summierung lässt sich leicht vektorisieren. Wenn ich keinen Fehler gemacht habe, sollte das funktionieren; das einzige Problem ist die mögliche Überlaufgefahr bei der Akkumulation. Ich habe keine Motivation, es selbst zu benchmarken. Edit: Ich hatte übersehen, dass der Wert beim Auftreten von s abnimmt; das Endergebnis ist also p_count - s_count.

  • strlen() dürfte ziemlich schnell implementiert sein, und wenn die Puffergröße bekannt ist, kann der Compiler die innere Schleife automatisch vektorisieren.
    Tatsächlich wird Code, der nach len = strlen(buf) in einer for-Schleife (buf[i] == 's') - (buf[i] == 'p') addiert, automatisch vektorisiert: https://gcc.godbolt.org/z/qYfadPYoq

  • Ich habe früher einmal einen Common-Lisp-UTF-8-Decoder für SBCL geschrieben. Es gab bereits einen eingebauten Decoder, also war es nur zur Übung.
    Abgesehen von offensichtlichen einfachen Optimierungen kamen fast alle Performance-Gewinne daher, den Code so zu strukturieren, dass der Compiler statt Branches cmov*-Instruktionen erzeugte.

    • Mich würde ein Beispiel interessieren, wie du den Code geändert hast. Außerdem, ob du die Funktion wiederholt disassembliert hast, um zu sehen, ob die richtigen Instruktionen verwendet werden, oder ob du per Benchmark die tatsächliche Verbesserung überprüft hast.
    • Wenn der Branch korrekt vorhergesagt wird, ist er vermutlich schneller als ein bedingter Move, weil er die Länge des kritischen Pfads nicht erhöht.
      UTF-8-Decoder laufen meistens auf Eingaben, die vollständig aus ASCII bestehen. Mich würde interessieren, mit welcher Eingabe du gebenchmarkt hast.