Einführung in den 1BRC-Wettbewerb
- Beim 1BRC-Wettbewerb wurde vorhergesagt, dass nach der Verarbeitung der „üblichen Verdächtigen“ das Parsen der Temperaturen aus der CSV-Datei zum Flaschenhals werden würde.
- Temperaturen können in vier Formaten auftreten:
-XX.X, -X.X, X.X, XX.X. Anfangs wurde dafür ein Aufruf der Bibliotheksfunktion Double.parseDouble() verwendet.
- Schon bald tauchten jedoch maßgeschneiderte Lösungen auf, und eine davon wirkte wie eine optimierte Methode ohne Schleife mit nur zwei Verzweigungen.
- Dann brachte die von Quân Anh Mai (@merykitty) vorgestellte Lösung den Twitter-Hashtag #1BRC zum Glühen. Diese Lösung verwendete kein
if und nur einen einzigen Dateilesevorgang.
Analyse von merykittys magischem SWAR
- merykittys Code besteht aus nur 18 ALU-Operationen und enthält einen einzigen Aufruf der Low-Level-Funktion
numberOfTrailingZeros().
- Die eingegebene
long-Zahl enthält 8 Byte aus der CSV, und ausgegeben wird die Temperatur als Ganzzahlform (das 10-Fache der tatsächlichen Temperatur).
- Diese Technik wird „SIMD Within A Register“ (SWAR) genannt und verwendet Standard-CPU-Register und -Instruktionen.
- Der Code durchläuft Schritte wie das Erkennen negativer Zahlen, das Entfernen des Vorzeichens, das Finden der Position des Dezimalpunkts, das Ausrichten des Inhalts auf ein Template, das Umwandeln von ASCII-Zeichen in Zahlenwerte, das Multiplizieren jeder Ziffer mit ihrem Gewicht und das Aufsummieren aller Werte sowie das Anwenden des Vorzeichens.
- Diese Schritte werden vollständig nur mit ALU-Operationen ausgeführt.
Fazit
- Wie merykitty all das ganz allein in nur wenigen Tagen schaffen konnte, ist das eigentliche Mysterium, das sich mit einem Blogpost nicht erklären lässt.
- QuestDB ist Open Source und bietet unter der Apache-2.0-Lizenz schnelles Einfügen von Daten und SQL-Analysefunktionen.
Meinung von GN⁺
- Dieser Artikel zeigt die Komplexität und Kreativität der SWAR-Technik, die entwickelt wurde, um ein scheinbar simples Problem beim Parsen von Temperaturen zu lösen. Er unterstreicht die Stärke von Bit-Operationen in der Programmierung und die Bedeutung von Optimierung.
- Gerade für Software Engineers am Anfang ihrer Laufbahn, die sich für Systemprogrammierung oder performancekritische Anwendungen interessieren, kann dieser Ansatz ein spannendes Beispiel sein.
- Um das Verständnis von Bit-Operationen und Optimierung zu vertiefen, kann es hilfreich sein, nach Online-Coding-Wettbewerben oder Tutorials zu suchen, die sich mit verwandten Themen oder Problemen beschäftigen.
- Weitere Untersuchungen sind nötig, wie diese Technik in realen Industrieumgebungen eingesetzt werden kann und ob es andere Datenbanken oder Systeme gibt, die ähnliche Optimierungsmethoden verwenden.
- Bei der Einführung von Systemen wie QuestDB sollten neben Performance-Gewinnen auch andere Faktoren wie Wartbarkeit, Lesbarkeit des Codes und langfristiger technischer Support berücksichtigt werden.
1 Kommentare
Hacker-News-Kommentar
Zusammenfassung der Hacker-News-Kommentare zum simdjson-Paper:
Interpretation des Code-Kontexts: Die vorgestellte Lösung ist hervorragend, setzt aber voraus, dass die Daten gut strukturiert sind. Effiziente Fehlerprüfung und Wiederherstellungsfunktionen haben bei erfahrenen Parsern großen Wert.
Technik zum Parsen von Zahlen: Die numerischen Bitfelder jeweils mit den entsprechenden Zehnerpotenzen zu multiplizieren und per MUL zu shiften/aufzuaddieren, ist eine bekannte Technik. Siehe Lemires Blog.
Erklärung zu SWAR (SIMD Within A Register): Es gibt viele Beispiele dafür, wie man in Java/Scala mit Byte-Array-View-Var-Handles effiziente SWAR-Routinen implementiert.
Kurze Definition von SWAR: "SIMD Within A Register" führt SIMD-Operationen innerhalb eines einzelnen Registers aus.
Frage zum I/O-Flaschenhals bei BRC (Branchless Ray Casting): Es ist nicht nachvollziehbar, warum die CPU der Flaschenhals sein soll.
Erfahrung mit SWAR auf dem 68000: Es war möglich, 4 Byte gleichzeitig parallel zu verarbeiten, aber der Umgang mit Overflow war knifflig. Der Artikel gefällt sehr.
Zustandsraum und Superoptimierer: Frage, ob es wegen des kleinen Zustandsraums einen Superoptimierer gibt, der ähnliche Ergebnisse erzeugt.
AVX-Befehle und Javas SIMD-Unterstützung: Dieser Algorithmus könnte mit AVX-Befehlen 32-fach parallel ausgeführt werden, aber es ist bedauerlich, dass Java die Nutzung von SIMD-CPUs außer in bestimmten Fällen nicht richtig unterstützt.
Verständnis für Bit-Manipulation: Dieser Artikel hat das Verständnis von Bit-Manipulation besser vermittelt als alles zuvor, und es wird dem Autor gedankt, der eine Java-Lösung für die 1BRC-Challenge vorgestellt hat.