55 GiB/s FizzBuzz (2021)

 (codegolf.stackexchange.com)
5 Punkte von GN⁺ 2023-07-04 | 1 Kommentare | Auf WhatsApp teilen
  • High Throughput Fizz Buzz auf Code Golf Stack Exchange ist ein Performance-Experiment, bei dem es darum geht, wie schnell sich FizzBuzz-Ausgaben erzeugen und durch eine Pipe schicken lassen; bewertet wird der Durchsatz mit <program> | pv > /dev/null
  • Gültige Ausgaben müssen schlichtes ASCII sein, \n als Zeilenumbruch verwenden, korrektes Fizz/Buzz/FizzBuzz ausgeben und mindestens bis 2^58 oder praktisch unendlich weiterlaufen; der Null-Byte-Trick, der nur von pv gezählt wird, ist verboten
  • Die Top-Implementierungen verzichten auf % 3, % 5 und printf-Schleifen und reduzieren Engpässe durch Unrolling des 15-Zeilen-Musters, Verarbeitung von Zahlen mit fester Breite, große Buffer, Parallelisierung und Zero-Copy-Ausgabe
  • Die gezeigte x86-64+AVX2-Assembly-Antwort setzt Linux und AVX2 voraus und kombiniert vmsplice, L2-Cache, Huge Pages und einen FizzBuzz-Bytecode-Interpreter; sie erreicht etwa 61 GiB/s
  • Die Ergebnisse schwanken stark je nach CPU, Pipe-Buffer, pv-Version, CPU-Affinity und Mitigation-Einstellungen; auf der Maschine des Fragestellers wird David Franks C++-Implementierung mit rund 1,7 Tb/s als Bestwert geführt

Mit FizzBuzz an die Grenzen des Durchsatzes

  • Im Kern geht es nicht um das FizzBuzz-Problem, sondern darum herauszufinden, was bei der Erzeugung sehr einfacher Texte zuerst zum Flaschenhals wird: CPU-Berechnung, Speicherkopien, Pipe-I/O oder Kernel-Grenzen
  • Die naive C-Referenzimplementierung verwendet % 3, % 5 und printf und kommt auf einer durchschnittlichen Maschine auf etwa 170 MiB/s
  • Der Fragesteller hatte auf derselben Maschine bereits Implementierungen mit mehr als 3 GiB/s gesehen und wollte, dass die Community höhere Durchsatzgrenzen auslotet
  • Die Punkte werden auf dem Desktop des Fragestellers gemessen
    • AMD 5950x, 16C/32T
    • 64 GB 3200-MHz-RAM
    • CPU-Mitigations deaktiviert
  • Die Tabelle nach Sprachen enthält unter anderem asm mit 60,8 GiB/s, C mit 20,9 GiB/s, Julia mit 15,5 GiB/s, Go mit 6,8 GiB/s, Java mit 5,8 GiB/s, Rust mit 3,4 GiB/s, Ruby mit 1,7 GiB/s und Python mit 0,5 GiB/s
  • Die x86-64+AVX2-Assembly-Antwort von ais523 zielt auf maximale Single-Thread-Leistung ab und erreicht auf der Maschine des Autors etwa 31 GiB/s, in der Auswertung des Fragestellers rund 61 GiB/s
  • David Franks C++-Implementierung ist laut Fragetext aktuell der Bestwert und erreicht etwa 1,7 Terabit/s; eine separate C++20-Implementierung gibt an, auf einem AMD Ryzen 9 7700X 283 GB/s erreicht zu haben

Ausgaberegeln und Benchmark-Bedingungen

  • Die Anforderungen an gültige Ausgaben sind streng
    • Die Ausgabe muss korrektes FizzBuzz sein
    • Sie muss 1 Byte pro ASCII-Zeichen verwenden
    • Als Zeilenumbruch ist nur \n erlaubt
    • \r\n ist nicht erlaubt
    • Die Ausgabe muss mindestens bis zu einer sehr großen Zahl von 2^58 oder darüber hinaus fortgesetzt werden
  • Auch die Benchmark-Methode selbst beeinflusst den Durchsatz
    • pv und Linux-Pipe-Buffer werden als standardmäßig mit 64K-Buffer arbeitend diskutiert
    • Je nach Platzierung auf CPU-Sibling-Cores kann sich der L2-Cache-Pfad zwischen erzeugendem Programm und konsumierendem Programm unterscheiden
    • Mit taskset lässt sich die CPU-Platzierung erzwingen, um Vergleiche anzustellen

Optimierungsansatz der Assembly-Implementierung

  • Der Kern der Assembly-Implementierung liegt darin, die Kosten für das Kopieren der Ausgabe stärker zu senken als die Berechnung selbst
    • Bei write fallen hohe Kosten für das Kopieren vom Userspace in den Kernelspace an
    • Der Autor schreibt, dass die Leistung auf ein Fünftel fällt, wenn man auf write umstellt
    • Mit vmsplice kann die Pipe auf den Buffer des Programms verweisen, wodurch Kopien reduziert werden
  • Die FizzBuzz-Berechnung ist in drei Phasen aufgeteilt
    • Die erste Phase hardcodiert die Anfangsstrings
    • Die zweite Phase verarbeitet 2- bis 5-stellige Zahlen mit relativ direkten AVX2-Routinen
    • Die dritte Phase verarbeitet den Bereich von 6 bis 18 Stellen mit einem FizzBuzz-Bytecode-Interpreter
  • Die Hauptschleife der dritten Phase zielt auf 64 Byte Ausgabe pro 4 Taktzyklen ab
    • 1 Byte Bytecode erzeugt 1 Byte Ausgabe
    • Es werden 32 Byte Bytecode geladen und mit vpshufb, vpsubb und ähnlichen Instruktionen 32 Byte Ausgabe erzeugt
    • Zeilennummern werden über Näherungswerte und Bytecode-Korrekturen verarbeitet, sodass nicht in jeder Zeile eine normale Zahlenkonvertierung nötig ist
  • Diese Implementierung ist stark plattformabhängig
    • Sie benötigt ein nicht zu altes Linux
    • Sie benötigt einen x86-64-Prozessor mit AVX2-Unterstützung
    • Wenn die Standardausgabe keine Pipe ist, gibt sie beim Start einen Fehler aus
    • Der Autor weist darauf hin, dass sie in Pipe-Konfigurationen mit splice in manchen Fällen falsche Ausgaben liefern kann

Gemeinsame Strategien anderer Sprachimplementierungen

  • Auch Implementierungen in C, Go, Java, Rust, Python, Julia, Ruby und C# verfolgen ähnliche Optimierungsrichtungen
    • Sie rollen das 15-Zeilen-FizzBuzz-Muster aus
    • Sie reduzieren die Zahl der Umwandlungen in Zahlenstrings
    • Sie sammeln Ausgaben in großen Buffern
    • Sie parallelisieren die Erzeugung mit Threads oder Goroutines
    • Sie nutzen Barrier, Channel, Queue oder Mutex, um die Ausgabereihenfolge beizubehalten
  • Diese Ergebnisse lassen sich schwer als simpler Vergleich der „Sprachperformance“ lesen
    • pv-Version, Pipe-Größe, Verfügbarkeit von vmsplice, CPU-Affinity, Huge Pages, Compiler-Optimierung und das Inlining von memcpy verändern den Durchsatz erheblich
    • Zu einigen Antworten gibt es Kommentare, dass sie auf bestimmten Maschinen schnell sind, sich dieselben Werte in anderen Umgebungen aber nicht reproduzieren ließen

Nicht abgedeckter Umfang

  • In der Eingabenotiz steht, dass einige Source-Chunks aus Längen- und Kostengründen ausgelassen wurden; daher werden nicht alle 46 Antworten sowie sämtlicher Code und alle Kommentare vollständig behandelt
  • Der ausgelassene Umfang kann einzelne Einreichungen nach Sprache, lange Code-Blöcke, detaillierte Tuning-Logs und Kommentardiskussionen enthalten

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-07-04
Hacker-News-Meinungen

  • Am beeindruckendsten ist, dass Linux Daten, die von einem Programm zu einem anderen gepiped werden, ausschließlich im L2-Cache halten kann, ohne den Hauptspeicher anzufassen.
    Dass mehrere Teile eines gewöhnlichen Linux-Kernels so zusammenspielen, dass dieser schnelle Pfad möglich wird, halte ich für ein erstaunliches Systemarchitektur-Design.
    Ich frage mich, ob so etwas auch mit Mach-Ports unter Mac OSX oder mit Named Pipes unter Windows möglich wäre.

    • Wenn CPU-Caches physische Adress-Tags verwenden und die Seitentabellen zweier Prozesse dieselbe physische Seite teilen, lässt die CPU jeden der Prozesse die Cache-Inhalte verwenden, solange das Betriebssystem den Cache beim Kontextwechsel nicht explizit leert oder invalidiert.
    • Das ist einer der vielen Gründe, warum die gesamte High-Frequency-Trading-Branche auf Linux läuft.

  • Ganz dem Benutzernamen „ais523 - high effort answers“ entsprechend hat diese Person auch jemandem, der das Programm nicht ausführen konnte, einen ziemlich aufwendig ausgearbeiteten Kommentar hinterlassen; die Schlussfolgerung war:
    „Vermutlich wurde das Programm versehentlich mit aktiviertem ASLR kompiliert. In diesem Fall respektiert der dynamische Linker die 4-MiB-Ausrichtung des BSS-Segments nicht, ignoriert damit faktisch mein .align, und das scheint die Ursache des Bugs zu sein.“

    • Ich weiß nur: Wenn diese Person sich auf denselben Job bewirbt wie ich, habe ich keine Chance. Der ultimative Leet Coder.

  • Jedes Mal, wenn dieser Beitrag wieder hochkommt, muss ich über diesen Kommentar lachen:
    „@chx: Ich habe bereits eine Masterarbeit. Das hier war schwieriger. – ais523 - high effort answers Oct 29, 2021 at 1:17“

  • Ich habe einfache Implementierungen in Rust, Python3 und C ohne Optimierung ausprobiert. Verwendet wurden nur schlichtes if/else/while und Ausgaben auf die Standardausgabe.
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    Weiß jemand, warum die Rust-Performance in einem ähnlichen Bereich wie Python3 liegt? Ich hätte erwartet, dass sie näher an C ist.

    • Rusts print-Funktion nimmt standardmäßig einen Lock. Das dient der Sicherheit, C macht das nicht. Details stehen in der Rust-Dokumentation: https://doc.rust-lang.org/std/macro.print.html
      Um eine ähnliche Performance wie C zu erreichen, muss man diesen Lock sehr wahrscheinlich selbst handhaben.
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      Außerdem muss auch die Puffergröße der Standardausgabe an C angeglichen werden.
    • Ein älterer Beitrag von mir, der hilfreich sein könnte:
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C und Python verwenden adaptives Buffering für die Standardausgabe. Wenn das Ausgabenziel ein Terminal ist, wird bei jedem Zeilenumbruch geleert; andernfalls erst, wenn der interne Puffer voll ist.
      Bei einem C-Programm, das mit 1 ms Verzögerung Zahlen hochzählt, ist die zweite Spalte die seit dem vorherigen read() vergangene Zeit.
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      Man sieht, dass alles auf einmal geschrieben wurde. Wenn man ein Terminal zuweist, kommt es zeilenweise heraus.
      $ rtss --pty ./out
      0.8ms 0.8ms | 1
      1.9ms 1.1ms | 2
      3.0ms 1.1ms | 3
      4.1ms 1.1ms | 4
      4.3ms exit status: 0
      Rust hat dieses adaptive Verhalten bei der Ausgabe nicht und verhält sich daher unabhängig davon, ob es ein Terminal ist, immer wie im zweiten Ergebnis.
      Technisch wird die Standardausgabe immer in einen LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html) gewrappt, und sobald ein Schreibvorgang einen Zeilenumbruch enthält, wird immer geleert. Um den Durchsatz zu maximieren, muss man mehrere Zeilen bündeln, etwa indem man sie in einen BufWriter wrappt.
    • Rust muss mit --release, C mit -O3 kompiliert werden.
    • Es liegt fast sicher an der Ausgabe. Wahrscheinlich ist es ein Problem mit Buffering oder Locks.

  • Man fragt sich, wie schnell das gewesen wäre, wenn alles in Assembly geschrieben worden wäre
    In der Audioentwicklung ist es sehr üblich, DSP-Code in Assembly zu schreiben

    • Der Grund, warum das schnell ist, ist nicht einfach, dass es Assembly ist. Das ist für diese Lösung zwar nötig, aber keineswegs hinreichend.
      Möglich wird das erst durch eine Kombination aus extremer Algorithmenforschung, tiefem Wissen über Linux-Systemaufrufe und plattformspezifischer Optimierung. Um den Autor Alex Smith selbst zu zitieren:
      „@chx: Ich habe bereits eine Masterarbeit. Das hier war schwieriger.“
      Das ist eine völlig andere Liga als etwas, das man einfach mit „macht man halt in Assembly“ hinbekommt.
    • Selbst wenn alles nur in Java geschrieben worden wäre, wäre es wohl besser gewesen als der heutige Ansatz, Chrome in eine Python-Instanz zu stecken und darin einen JavaScript-Webserver laufen zu lassen, um Dokumente zu rendern.
    • Am Ende würde es wohl so ausgehen wie in Steve Yegges Geoworks-Geschichte:
      „Also gut. Ich war an der University of Washington und nahm dann einen Job bei einer Firma namens Geoworks an, wo ich fünf Jahre lang in Assemblersprache programmierte. Wir Geoworker schrieben das gesamte Betriebssystem, die Bibliotheken, Treiber, Apps, also ein komplettes Desktop-Betriebssystem, vollständig in Assembly. 8086-Assembly! Nicht einmal gutes Assembly! Es gab nur vier Register! Wenn man bis zum 386 geht, hatten wir auch noch das si-Register. Es war furchtbar.
      Tatsächlich mochten wir es ziemlich. Es war objektorientiertes Assembly. Es ist erstaunlich, wozu sich Menschen selbst überreden können, etwas zu mögen, und genau das ist die eigentliche Ironie an der ganzen Sache. Für uns war C++ der Gipfel römischer Dekadenz. Wie sich übergeben zu gehen, um noch mehr essen zu können. Die hatten IF! Wir hatten jump CX zero! Die hatten ‚Objekte‘. Wir hatten sie zwar auch, aber sie hatten Syntax dafür. Das wirkte wirklich verweichlicht. Und damals wussten wir, dass wir schnelleren Code schreiben konnten als jeder Compiler, und das taten wir auch!
      Und was ist dann passiert? Die Firma ging bankrott. Warum? Vermutlich werde ich damit jedem Geoworker widersprechen. Tatsächlich weiß ich, dass ich der Einzige bin, der das glaubt. Aber der Grund war, dass wir 15 Millionen Zeilen 8086-Assemblersprache geschrieben hatten. Wir hatten wirklich gute Tools, Tools auf Weltklasseniveau, glaubt mir. So etwas braucht man unbedingt. Aber irgendwann kommt ein Punkt …
      Das Problem ist: Stellt euch eine Ameise vor, die versucht, in einer geraden Linie über den Garagenboden zu laufen. Sie kann nicht geradeaus gehen. Wir wissen das, weil wir ein größeres Sichtfeld haben. Man sieht, wie die Ameise herumläuft, lokal an diesem Stein optimiert und dann in jene Richtung weitergeht.
      Genau so war es, als wir ein riesiges System in Assemblersprache schrieben. Schließlich brachte Microsoft eine Plattform für Mobilgeräte heraus, die viel schneller war als unsere. Ich ging mit dem Debugger hinein und sagte: ‚Was ist das? Warum passiert das? Das Rendering ist wirklich langsam, es ruckelt.‘ Als ich hineinschaute, wurde bei jeder Bildschirmaktualisierung irgendeine Titelleiste 140-mal gerendert. Und es war nicht nur die Titelleiste. Alles wurde mehrfach aufgerufen.
      Weil wir nicht mehr sehen konnten, wie das System funktionierte!
      Kleine Systeme sind nicht nur leichter zu optimieren, sie sind überhaupt optimierbar. Das heißt, globale Optimierung ist möglich.“
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • Assembly ist heute so weit von dem Quellcode entfernt, der geschrieben wird, dass es kaum realistisch ist, überhaupt darüber nachzudenken. Trotzdem kann man sich vorstellen, wie viel schneller alles wäre, wenn Unternehmen, die Software bauen, sich tatsächlich um Performance kümmern würden.
      Ich denke, etwa 99 % der heutigen Websites und Software könnten schon mit grundlegenden Änderungen mindestens 50 % schneller werden, wenn man der Anwendungs-Performance nur ein wenig Aufmerksamkeit schenken würde: korrektes Caching, Asset-Optimierung, das Ersetzen aufgeblähter Third-Party-Bibliotheken durch grundlegende native Calls, die dasselbe leisten, sowie passende Konfiguration von Servern und Datenbanken.
      Es scheint auch denkbar, dass KI in ein paar Jahren One-Click-Optimierungen für Repositories anbietet, Best Practices anwendet oder den ursprünglichen Code in schnelles Assembly umschreibt.
    • Ein Detail, das bei der Behauptung, primitivere Sprachen führten zu schnelleren Programmen, oft übersehen wird: Wenn schon kleine Fortschritte beim Coden schmerzhaft sind, bemüht man sich sehr, so wenig wie möglich zu implementieren.
      Ressourcenbeschränkungen können für Klarheit im Fokus sorgen.

  • Dieses Experiment ist zwar interessant und lehrreich, wirkt aber etwas fehlerhaft. Es testet weniger, wie schnell ein komplexes Problem gelöst wird, sondern vor allem das Randproblem, wie effizient Speicher aus einem Prozess herausgeholt und an einen anderen Prozess übergeben wird.
    Deshalb sieht es zwar so aus, als würde der zweite Prozess fortlaufend auf die Konsole oder in eine Datei schreiben, technisch gesehen ist das aber nicht der Fall. pv >/dev/null auszuführen ist im Grunde ziemlich nahe daran, gar nichts zu tun, und der write-Systemaufruf kehrt fast sofort zurück.
    vmsplice ist im Wesentlichen eine Shared-Memory-artige Funktion, die es einem anderen Prozess erlaubt, auf den Puffer/Speicher eines Prozesses zuzugreifen. Wahrscheinlich waren die ursprünglichen Wettbewerbsanforderungen unklar, daher wirkt es unklar, ob das regelkonform ist.

    • Ob die ursprünglichen Anforderungen unklar waren, kann man prüfen, indem man zur ursprünglichen Frage nach oben scrollt; in der Bearbeitungshistorie sieht man außerdem, dass sie seit Beginn der Challenge nicht geändert wurden.
      „Schreibt ein FizzBuzz-Programm. Führt es aus. Leitet die Ausgabe mit | pv > /dev/null weiter. Je höher der Durchsatz, desto besser.“
      „Die Programmausgabe muss exakt gültiges FizzBuzz sein. Keine Tricks wie das Einschieben von Null-Bytes zwischen gültige Ausgaben — also Null-Bytes, die in der Konsole nicht sichtbar sind, aber beim Durchsatz von pv mitgezählt werden.“
      Und vmsplice(2) erzeugt tatsächlich einen Byte-Stream in der Standardausgabe-Pipe, den pv(1) nach /dev/null splicen oder cat(1) ins Terminal kopieren kann.
      Außerdem ist diese Einreichung nicht die einzige, die vmsplice(2) verwendet. Andere Teilnehmende haben ebenfalls herausgefunden, dass das keineswegs eine magische Lösung ist. Selbst nachdem man die I/O-Barriere überwunden hat, bleibt noch viel Arbeit, um Ausgabeseiten so schnell wie möglich zu erzeugen.
    • Ich glaube, „die Effizienz, Speicher aus einem Prozess herauszuholen und an einen anderen Prozess weiterzugeben“ ist fast immer das gesamte Problem.
      Der meiste Code hat Engpässe bei Speicher und I/O. Auch komplexe Probleme scheitern meistens daran, Daten von einem Ort an einen anderen zu bewegen, und nur selten daran, die Daten zu berechnen. Selbst wenn ich den Tag damit verbringe, GPU-Assembler zu optimieren: In den seltenen Fällen, in denen Rechenleistung der Engpass ist, wird nach deren Optimierung der Speicher zum Engpass.
    • Da stimme ich nicht zu. Ohne zunächst erhebliche FizzBuzz-spezifische Optimierungen vorzunehmen, erreicht der Engpass gar nicht erst die „Effizienz, Speicher aus einem Prozess herauszuholen und an einen anderen Prozess weiterzugeben“.
      Es gibt zum Beispiel eine clevere Bitdarstellung, bei der dezimale Überträge auf natürliche Weise passieren.
      Auch die ursprünglichen Wettbewerbsanforderungen sind an dieser Stelle nicht wirklich unklar. Sie sagen ausdrücklich, dass der Durchsatz mit | pv > /dev/null gemessen werden soll, und formulieren außerdem:
      „Architekturspezifische Optimierungen / Assembler sind ebenfalls erlaubt. Das ist kein echter Wettbewerb. Ich möchte einfach nur sehen, wie Leute FizzBuzz bis an die Grenzen treiben, auch wenn es nur in einer speziellen Umgebung/auf einer speziellen Plattform funktioniert.“
    • I/O ist buchstäblich etwas, das jedes Programm tun muss. 99 % des Codes, der auf moderner Hardware läuft, haben genau dort ihren Engpass. Bytes von einem Ort an einen anderen zu bewegen ist unverzichtbar und vergleichsweise langsam.
      Zu verstehen, wie man Speicher-I/O und Datei-I/O performant handhabt, ist eine Fähigkeit, die für alle Programme und Programmierer relevant ist.

  • Es heißt, man solle es als fizzbuzz.S speichern; ich frage mich, was der Unterschied zwischen den Endungen .S und .s ist.

    • Das große S lässt zuerst den Präprozessor laufen.
      Laut Manpage:
      file.s
      Assembler-Code
      file.S
      file.sx
      Assembler-Code, der vorverarbeitet werden muss
    • Soweit ich mich erinnere, war das traditionell der Unterschied, ob die Eingabe durch den Präprozessor läuft (.S) oder nicht (.s).
      Ob es in modernen Toolchains noch einen Unterschied gibt, weiß ich nicht genau.
    • In der Konvention, die ich kenne, verwendet man .S für von Menschen direkt geschriebene Assembly-Dateien, normalerweise Dateien, die in git getrackt werden, und .s für maschinell erzeugten Assembly-Code, der bei Bedarf überschrieben werden kann.
    • GCC und Ähnliche überschreiben .S nicht, aber wenn man sie auffordert, Assembly zu erzeugen (z. B. gcc -S xyz.c), überschreiben sie .s.

  • Frühere Beiträge:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • Ich habe zuerst 55 GiB/s FritzBox gelesen. FritzBox ist ein im deutschsprachigen Europa beliebter Router.
    Mein ISP hat letzte Woche ebenfalls eine bald verfügbare OPNSense-Box[1] mit Unterstützung für 60 GiB/s getwittert.
    [1] https://twitter.com/init7/status/1674920410889043973

    • Ich nutze eine DEC750 mit auf 16 GB erweitertem Speicher. Ein Router mit 10GbE-Unterstützung und 2,3GbE über WireGuard, der leise ist und im Idle mit 8 W etwa so viel verbraucht wie ein Kabelmodem, war ein hervorragendes Gerät; ich habe nicht vor, ihn vor 2030–2035 zu ersetzen.
      Außerdem steckt ein USB-WiFi-Adapter daran, sodass bei einem Kabelausfall bestimmte VLANs per Failover umschalten und ich über das Handy die zentrale Konnektivität für die Arbeit aufrechterhalte.
      Billig ist das nicht, aber wenn man das OPNSense-Projekt finanziell unterstützen und zugleich ordentliche Hardware haben möchte, sind Deciso-Geräte schwer zu widerlegen. Sie sind energieeffizient, verwenden auf Langlebigkeit ausgelegte Komponenten und funktionieren einfach.
      Schön zu sehen, dass die kommerzielle Produktreihe leistungsfähiger wird.