1brc: merykittys magisches SWAR – 8 Zeilen Code in 3.000 Wörtern erklärt

• Der Engpass bei 1BRC bestand darin, eine Milliarde CSV-Temperaturwerte extrem schnell zu parsen; Quân Anh Mais merykitty-SWAR-Code erregte Aufmerksamkeit, weil er Temperaturen ohne if mit festen ALU-Operationen in Ganzzahlen umwandelt
• Der Code nutzt SWAR (SIMD Within A Register): Er verarbeitet die 8 Bytes in einem einzelnen long auf einmal und behandelt mehrere Zeichen in normalen CPU-Registern quasi parallel
• Der Ablauf besteht aus Erkennen des Minuszeichens, Entfernen des Vorzeichens, Finden der Dezimalpunktposition, Ausrichten auf XY.Z, Umwandeln von ASCII-Ziffern, Magic Multiplication und Anwenden des Vorzeichens
• Das Eingabeformat kann -XX.X, -X.X, X.X oder XX.X sein; anhand der Position des Dezimalpunkts werden Bytes verschoben, sodass unterschiedlich lange Eingaben in dasselbe Bitlayout passen
• Statt Verzweigungen und Schleifen nutzt die Implementierung die Eigenschaften von ASCII-Codes, Zweierkomplement, Bitmasken und die Shift-Add-Eigenschaft von Multiplikation sehr dicht aus, um High-Performance-Parsing zu erreichen

---

Temperatur-Parsing als Engpass bei 1BRC

• Bei der One Billion Row Challenge (1BRC) wurde das extrem schnelle Parsen von Temperaturwerten aus einer CSV-Datei zum zentralen Engpass
• Schon mit früheren Optimierungen wurde idiomatischer paralleler Java-Code von 71 Sekunden auf 1,7 Sekunden beschleunigt
• Das Temperaturformat ist einfach, aber wenn eine Milliarde Werte in unter einer Sekunde geparst werden sollen, summieren sich selbst kleine Kosten stark
  • Mögliche Formate sind -XX.X, -X.X, X.X, XX.X
• Frühe Teilnehmer verwendeten Double.parseDouble(), später erschienen jedoch eigene Parser ohne Schleifen
• Ein Teil der Lösung von Quân Anh Mai @merykitty verarbeitete die Daten ohne if und mit einem einzigen Dateilesedurchlauf und verbreitete sich wie ein Standardbaustein der besten 1BRC-Lösungen
• Der Gewinner Thomas Wuerthinger nennt Quân Anh ausdrücklich als Teil des Teams, das zu seiner Lösung beigetragen hat

Was der merykitty-Code macht

• Der Code nimmt ein long mit 8 Bytes CSV-Eingabe entgegen und gibt den ganzzahligen Temperaturwert zurück, also die tatsächliche Temperatur mal 10
• Die Eingabe kommt über direkte Native-Memory-Lesezugriffe aus einer per mmap gemappten CSV-Datei; dieser Teil ist als separates Thema ausgeklammert
• Die Berechnung besteht aus 18 ALU-Operationen in fester Reihenfolge
  • Bit-Shifts, AND, NOT, XOR
  • Addition, Subtraktion, Multiplikation
  • Long.numberOfTrailingZeros()
• numberOfTrailingZeros() verwendet über ein JDK-Compiler-Intrinsic spezielle CPU-Instruktionen
• Da mehrere Bytes nicht mit speziellen SIMD-Instruktionen, sondern mit normalen CPU-Registern und Befehlen verarbeitet werden, handelt es sich um SWAR
• Der Beispielcode ist gegenüber dem Original leicht angepasst, um ihn lesbarer zu machen; das Original findet sich in CalculateAverage_merykitty.java

Gesamter Ablauf

• Der Code parst die Temperatur in folgender Reihenfolge
  • Prüfen, ob das erste Zeichen - ist, um einen negativen Wert zu erkennen
  • Falls ein Vorzeichen vorhanden ist, dieses Byte auf 0 setzen
  • Position des Dezimalpunkts . finden
  • Bits innerhalb des long so verschieben, dass die Ziffern zum Template XY.Z passen
  • ASCII-Zeichen in tatsächliche Zahlenwerte umwandeln
  • Die einzelnen Stellen mit den Gewichten 1x, 10x, 100x multiplizieren und aufsummieren
  • Am Ende das Vorzeichen anwenden
• Oberflächlich betrachtet ist es ein High-Level-Parsing-Problem, aber jeder Schritt wird ausschließlich mit ALU-Operationen umgesetzt

Schritt 1: Minuszeichen erkennen

• Die Vorzeichenerkennung beginnt mit folgendem Code

long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;

• Wenn man die Reihenfolge zur Erklärung umstellt, kann man es sich wie ( ~(inputData << 59) ) >> 63 vorstellen
• Ausgenutzt wird die Eigenschaft, dass das Minuszeichen - in ASCII Bit 4 auf 0 hat, während Ziffern an dieser Stelle eine 1 haben
• Wird die Eingabe um 59 Bit nach links verschoben, wandert dieses Unterscheidungsbit des ersten Zeichens in das höchstwertige Bit
• Nach dem NOT und einem arithmetischen Rechts-Shift um 63 Bit wird das höchstwertige Bit über das gesamte long verteilt
• Das Ergebnis broadcastSign besteht bei einem Minuszeichen nur aus Einsen, andernfalls nur aus Nullen

Schritt 2: Vorzeichenzeichen entfernen

• Da die Information über ein negatives Vorzeichen in broadcastSign gespeichert ist, wird das Vorzeichenzeichen aus den Eingabedaten entfernt

long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;

• Wenn broadcastSign nur aus Einsen besteht, setzt broadcastSign & 0xFF nur die niedrigsten 8 Bit auf 1
• Das NOT daraus erzeugt eine Maske, bei der nur die niedrigsten 8 Bit 0 sind
• Per AND mit inputData wird das - im niedrigstwertigen Byte entfernt
• Gibt es kein Minuszeichen, ist broadcastSign 0; die Maske besteht dann vollständig aus Einsen, sodass die Ziffernbytes erhalten bleiben

Schritt 3: Position des Dezimalpunkts finden

• Die Position des Dezimalpunkts wird mit folgendem Code berechnet

int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);

• Auch das Zeichen . hat wie das Minuszeichen die Eigenschaft, dass Bit 4 auf 0 steht
• Um nur Bit 4 an den möglichen Positionen des Dezimalpunkts zu prüfen, wird die Maske DOT_DETECTOR = 0x10101000 verwendet
• In der invertierten Originaleingabe negatedInput ist dieses Bit an der Dezimalpunktposition auf 1 gesetzt
• Long.numberOfTrailingZeros() gibt die Position dieses 1-Bits zurück
• Im Beispiel -10.8 liegt der Dezimalpunkt an Bitposition 28, also wird dotPos = 28

Schritt 4: Auf ein festes Template ausrichten

• Anhand der Position des Dezimalpunkts wird die Eingabe nach links verschoben, damit sie immer zum selben Template passt

long alignedToTemplate = withSignRemoved << (28 - dotPos);

• Das Ziel-Template sieht so aus

0 0 0 Z . Y X 0

• Dabei ist X die Zehnerstelle, Y die Einerstelle und Z die erste Nachkommastelle
• 0 bedeutet hier nicht das ASCII-Zeichen "0", sondern ein Byte mit dem Wert 0
• Nach Entfernen des Vorzeichens kann die Eingabe in einer von vier Anordnungen vorliegen
  • 0 0 0 Z . Y X 0
  • 0 0 0 0 Z . Y 0
  • 0 0 0 0 Z . Y X
  • 0 0 0 0 0 Z . Y
• -10.8 hat bereits dotPos = 28, daher beträgt die Verschiebung 0
• Bei -7.7 liegt der Dezimalpunkt an Bit 20, daher wird um 8 Bit, also ein Byte, nach links verschoben, sodass an der Position X eine 0 steht

Schritt 5: ASCII-Ziffern in Werte umwandeln

• Nach dem Ausrichten bleiben aus den ASCII-Zeichen nur die Ziffernwerte übrig

long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;

• Die ASCII-Ziffern 0 bis 9 reichen hexadezimal von 0x30 bis 0x39
• Wenn nur die unteren 4 Bit erhalten bleiben, wird aus dem Zeichencode der tatsächliche Zahlenwert
• Dafür wird eine Maske angewendet, die nur an den Ziffernpositionen des Templates F enthält

0 0 0 Z . Y X 0
000000F000F0F00

• Im Beispiel -10.8 bleiben nach Anwendung der Maske nur die Werte übrig, die Z=8, Y=0, X=1 darstellen

Schritt 6: Stellenwerte per Magic Multiplication aufsummieren

• Der endgültige Absolutwert muss als 100 * X + 10 * Y + Z berechnet werden
• Ausgenutzt wird die Eigenschaft, dass Multiplikation eine Kombination aus Shifts und Additionen ist, um die Gewichtung mehrerer Stellen mit einer einzigen Multiplikation zu erledigen
• Betrachtet man zunächst X + Y + Z, kann man durch Addieren von um 0, 16 und 24 Bit verschobenen Varianten von digits die Summe in einem bestimmten Bitbereich sammeln
• Diese Shift-Add-Kombination lässt sich als folgende Multiplikation ausdrücken

0x1 + 0x10000 + 0x1000000

• Tatsächlich haben die einzelnen Stellen unterschiedliche Gewichte, daher ist MAGIC_MULTIPLIER so aufgebaut

MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;

• Die Berechnung lautet

absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;

• 0x3FF ist eine Maske, die nur das 10 Bit breite Ergebnis isoliert
• 100 * X kann bis zu 10 Bit groß werden und sich mit benachbarten Bits überlappen, aber weil die unteren zwei Bits von Y * 100 0 sind, steht der nötige Bitraum zur Verfügung
• merykitty hinterließ an dieser Stelle den Kommentar // That was close :)

Schritt 7: Vorzeichen ohne Verzweigung anwenden

• Zu diesem Zeitpunkt liegen der Absolutwert absValue und die Vorzeicheninformation broadcastSign vor
• broadcastSign verhält sich bei positiven Zahlen wie 0 und bei negativen wie -1
• Im Zweierkomplement wird eine negative Zahl so dargestellt

-n = NOT(n) + 1

• XOR kann wie ein bedingtes NOT verwendet werden
  • n XOR -1 ist NOT(n)
  • n XOR 0 ist n
• Das optionale +1 wird durch -broadcastSign erledigt

temperature = (absValue ^ broadcastSign) - broadcastSign;

• Dadurch bleibt ein positiver Wert ohne if unverändert, während ein negativer Wert in seinen negativen Zweierkomplementwert umgewandelt wird

Bonus: Startposition der nächsten CSV-Zeile berechnen

• In der vollständigen 1BRC-Lösung muss auch die Startposition der nächsten CSV-Zeile günstig berechnet werden
• Auf den Dezimalpunkt folgen immer eine Nachkommastelle und ein Zeilenumbruch, daher lässt sich die Startposition der nächsten Zeile aus der Position des Dezimalpunkts ableiten
• Da dotPos eine Bitposition ist, wird zum Teilen durch 8 ein Rechts-Shift um 3 Bit verwendet

nextLineStart = (dotPos >>> 3) + 3;

• +3 ist der Wert, der auf das erste Byte nach Dezimalpunkt, einer Nachkommastelle und Zeilenumbruch zeigt

Fazit

• merykittys SWAR-Code vereinheitlicht und parst vier Temperatur-Stringformate allein mit festen Bitoperationen
• Kernpunkte sind die Biteigenschaften von ASCII-Codes, das Ausrichten anhand der Dezimalpunktposition, das Extrahieren der Ziffern per Maske, das Aufsummieren der Stellenwerte per Multiplikation und die Vorzeichenanwendung auf Basis des Zweierkomplements
• Zerlegt man ihn in einzelne Schritte, lässt sich die Funktionsweise nachvollziehen; beeindruckend bleibt jedoch, dass diese Kombination innerhalb weniger Tage eines Online-Challenges entstand

[GN⁺]

Hacker-News-Kommentare

• Die Schritt-für-Schritt-Erklärung ist wirklich hervorragend.
  Vor über zwei Jahren habe ich festgestellt, dass byte array view var handle in Java/Scala ziemlich gut geeignet ist, um effiziente SWAR-Routinen zu erstellen.
  Beispiele für den Einsatz von SWAR gibt es auch hier viele, etwa beim Parsen von Base16/64-Strings, java.time.* oder beim direkten Parsen numerischer Werte aus Byte-Arrays: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...
• Der Artikel ist gut und im Kontext des Codes eine hervorragende Lösung, aber dieser Ansatz setzt voraus, dass die Daten korrekt formatiert sind.
  Der große Wert eines praxiserprobten Parsers liegt in effizienter Fehlerprüfung und -wiederherstellung.
  • Es wäre interessant, aufzuschlüsseln, wie sich fehlerhafte Eingaben auf die Ausgabe auswirken könnten.
    Und ich frage mich auch, wie viel Aufwand nötig wäre, um das so zu erkennen, dass ein Sentinel-Fehlerwert zurückgegeben wird, wie es zum aktuellen Code-Stil passt.
    Nicht interessant genug, um es selbst auszuprobieren, aber ;-)
• Die Technik, in einem Zahlen-Bitfeld jede Stelle mit der entsprechenden Zehnerpotenz zu multiplizieren und per MUL zu verschieben/zu addieren, ist recht bekannt.
  Siehe Lemires Artikel: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
• Dem Artikel zufolge steht SWAR für SIMD Within A Register.
• Wenn einem so etwas gefällt, nutzt auch das simdjson-Paper ähnliche Techniken; es ist sehr gut geschrieben und enthält gute Beispiele.
  Paper: https://arxiv.org/abs/1902.08318
  Github: https://github.com/simdjson/simdjson
  • Das ist zwar kein SWAR, aber ich verstehe, warum es interessant ist.
• Kann jemand erklären, warum BRC nicht durch I/O ausgebremst wird? Ich verstehe nicht, warum die CPU der Flaschenhals sein soll.
  • Auf modernen Systemen ist lokale Festplatten-I/O nicht mehr der Flaschenhals: https://benhoyt.com/writings/io-is-no-longer-the-bottleneck/
    Außerdem wurde beim offiziellen 1BRC ausdrücklich festgelegt, dass die Ergebnisse von einer RAM-Disk bewertet werden, um die I/O-Geschwindigkeit vollständig auszuklammern: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
    „Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)“
  • Als Hintergrund gibt es ein Interview mit Daniel Lemire. Er ist jemand, der seine ganze Karriere auf der Beobachtung aufgebaut hat, dass I/O nicht immer der Flaschenhals ist: https://corecursive.com/frontiers-of-performance-with-daniel...
  • Ich habe mir dieses Problem nicht im Detail angesehen, aber man kann auch von der Gegenseite anfangen: Warum hältst du Speicher-I/O für den Flaschenhals?
    Soweit ich es grob verstehe, wird eine große Textdatei sequenziell in L1 geholt und jeder Wert einmal gelesen. Auf den meisten Prozessoren kann man solche Lesezugriffe zweimal pro Zyklus ausführen. Der langsame Teil wäre, die Daten aus dem RAM nach L1 zu holen, aber sequenzielles Lesen ist ziemlich schnell.
    Danach wird jeder gelesene Wert verarbeitet. Auf den ersten Blick dürften es in einer optimierten Version ungefähr 4 Zyklen sein. Anschließend muss das Ergebnis irgendwohin geschrieben werden, und vermutlich braucht es davor ein oder zwei zufällige Lesezugriffe. Siehst du diesen Teil als I/O-Flaschenhals?
    Ich will nicht sagen, dass klar ist, dass die CPU begrenzt; aber es scheint auch nicht offensichtlich, dass sie es nicht ist.
    Edit: Ich habe nicht bedacht, dass „Festplatten-I/O“ gemeint gewesen sein könnte. Wie andere gesagt haben, spielt das hier faktisch keine Rolle.
  • Die Tests laufen auf memfs. Die Datei und alles andere liegen von Anfang an im RAM.
  • Der Datensatz ist klein genug, um in den Page Cache des Linux-Kernels zu passen, und der Benchmark wird fünfmal hintereinander wiederholt. Daher kann der erste Durchlauf durch Festplatten-I/O begrenzt sein, die übrigen vier aber nicht.
    Das heißt, alle Daten liegen im RAM, genauer gesagt im Page Cache.
• Auf dem 68000 habe ich SWAR recht effektiv eingesetzt. Mit einer Anweisung wurden 4 Bytes parallel verarbeitet.
  Wenn ich mich richtig erinnere, war die Behandlung von Overflows knifflig. Dieser Artikel gefällt mir wirklich sehr.
• Es heißt: „Dass eine einzelne Person allein das alles hervorgebracht hat, während sie ein paar Tage locker an einer Online-Challenge teilnahm, bei der T-Shirts und Kaffeebecher als Belohnung winkten, ist das eigentliche Rätsel.“ Warum ist das ein Rätsel?
  Es gibt immer noch Leute, die CPUs tatsächlich programmieren können und verstehen, was sie tun.
  Das eigentliche Rätsel ist, dass der großen Mehrheit der Menschen, die sich Programmierer nennen, offenbar ein tiefes Verständnis fehlt – und dass sie nicht einmal zu merken scheinen, wie gravierend dieser Mangel ist.
• In C# braucht man solche SWAR-Tricks nicht. Stattdessen gibt es eine erstklassige plattformübergreifende SIMD-API.
  Dass sie in der Praxis gut funktioniert, sieht man an der C#-Lösung, die unter den bisher veröffentlichten 1BRC-Beiträgen offenbar die schnellste ist: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
• Kann man das mit SSE vektorisieren? Der Großteil der Kernverarbeitung scheint mit Vektoren aus vier 32-Bit-Integern möglich zu sein.
  Die Frage ist, ob die Kosten für den Aufbau des Anfangsvektors und das Extrahieren der Ergebnisse nicht zu hoch sind.
  • Ja, das geht, und mehrere andere 1BRC-Implementierungen haben es so gemacht.
    Allerdings bezweifle ich, dass HotSpot das von selbst hinbekommt; außerdem wurden die meisten 1BRC-Einreichungen mit Graal ausgeführt, um den Start-Overhead zu reduzieren.
    In einfachem SSE2 gibt es keine 32-Bit- oder 64-Bit-Multiplikation, daher ist 32×32→64-Bit-Multiplikation ein Problem. SSE4.1 fügt mit pmuldq genau das hinzu, was man braucht. Da das Ergebnis aber 64 Bit breit ist, braucht man zwei solcher Operationen, um einen ganzen Vektor aus 32-Bit-Integern zu verarbeiten.
  • Da das Temperaturfeld mit dem Namensfeld vermischt ist, scheint es schwierig, mit SSE zusätzliche Vorteile zu erzielen.
    Außerdem ist das Temperaturfeld variabel lang; selbst wenn es spaltenweise gespeichert wäre, würde es vermutlich keinen Vorteil bringen.
    Beim Finden des Trennzeichens zwischen Name und Temperatur wurde SSE allerdings erfolgreich eingesetzt.
  • Solcher Code dürfte automatisch vektorisiert werden, entweder von Anfang an oder nachdem HotSpot einen Hotspot erkannt hat.