simdjson - JSON mit GB/s parsen

• Nutzt SIMD-Befehlssätze und parst 2,5-mal schneller als bestehende Parser

• Automatische Auswahl des pro CPU zur Laufzeit optimierten Parsers: Haswell (AVX2)/Westmere (SSE4.2)/ARM64/sonstige 64-Bit

• Unterstützung für vollständige JSON- und UTF-8-Validierung

• Eine einzelne .h- plus .cpp-Datei

• Verwendet im Vergleich zu RapidJSON nur 25 % und zu sajson nur 50 % des Befehlssatzes

[novemberoscar]

Es gibt offenbar verschiedene Bindings / Ports.

• ZippyJSON: Swift-Bindings für das simdjson-Projekt.

• libpy_simdjson: Hochgeschwindigkeits-Python-Bindings für simdjson mit libpy.

• pysimdjson: Python-Bindings für das simdjson-Projekt.

• simdjson-rs: Rust-Port.

• simdjson-rust: Rust-Wrapper (Bindings).

• SimdJsonSharp: C#-Version für .NET Core (Bindings und vollständiger Port).

• simdjson_nodejs: Node.js-Bindings für das simdjson-Projekt.

• simdjson_php: PHP-Bindings für das simdjson-Projekt.

• simdjson_ruby: Ruby-Bindings für das simdjson-Projekt.

• fast_jsonparser: Ruby-Bindings für das simdjson-Projekt.

• simdjson-go: Go-Port mit Golang-Assembly.

rcppsimdjson: R-Bindings.

[xguru]

Rust-Version - https://github.com/simd-lite/simd-json

Vortragsinhalt des Entwicklers auf der QCon: "Parsing JSON Really Quickly: Lessons Learned"

https://www.youtube.com/watch?v=wlvKAT7SZIQ

[kunggom]

Transkript des verlinkten Vortragsvideos:

https://www.infoq.com/presentations/simdjson-parser/

Ich habe es gelesen, weil mich interessiert hat, wie so eine hohe Geschwindigkeit möglich ist, und man kann wohl sagen, dass es geradezu die Essenz aller möglichen schwarzen Magie ist. Die Kernaussagen grob zusammengefasst sind die folgenden.

---

[Einleitung]

Die meisten JSON-Parsing-Bibliotheken sind langsamer als die sequenzielle Lesegeschwindigkeit eines Laufwerks

• Auf meinem Systemlaufwerk beträgt die Geschwindigkeit beim sequenziellen Lesen großer Textdateien 2,2 GB/s, aber die Parsing-Geschwindigkeit der wichtigsten JSON-Bibliotheken kam da nicht mit.

• Weil es nur wenige Bibliotheken gab, die beim Parsing über 1 GB/s kamen, beschlossen wir, selbst eine zu bauen.

• Das Ergebnis war, dass wir einen Durchsatz erreichten, der die gesamte Laufwerksbandbreite ausnutzen konnte. Hochgerechnet bedeutete das, dass die CPU pro Eingabebyte nur 1,5 Zyklen verbrauchte. Wie haben wir das geschafft?

[Verschiedene Prinzipien]

Verzweigungen so weit wie möglich vermeiden

• Wenn man zum Beispiel in einfachen Code, der Zufallszahlen in ein Array schreibt, nur ein einziges if einbaut, das prüft, ob eine Zahl ungerade ist, wird er schon fünfmal langsamer. Der Grund ist, dass Fehlvorhersagen bei der Branch Prediction der CPU teuer sind.

• Entfernt man in dem oben gezeigten Code das if per Bitoperation, ist die Geschwindigkeit fast wieder auf dem ursprünglichen Niveau.

• Führt man denselben Code wiederholt aus, kann die Genauigkeit der Branch Prediction steigen und der Leistungseinbruch kleiner werden. Da das aber letztlich nichtdeterministisches Verhalten ist, werden Performance-Prognosen und -Messungen schwierig, sobald Branch Prediction ins Spiel kommt.

SIMD aktiv einsetzen, um breitere Wörter zu verwenden

• Mit SIMD-Befehlen kann man Register verwenden, deren Wörter breiter als 64 Bit sind, und so pro Zyklus mehr Daten verarbeiten. (Zum Beispiel SSE oder NEON mit 128 Bit, AVX mit 256 Bit.) Deshalb wurde SIMD überall dort intensiv genutzt, wo es möglich war. Das war einer der Schlüssel dazu, pro Eingabebyte mit nur 1,5 Zyklen auszukommen.

• Um SIMD zu nutzen, wurden von bestimmten Prozessoren abhängige Intrinsic Functions verwendet. Die direkte Verwendung von Assembler wird nicht empfohlen.

Speicher-/Objektallokationen vermeiden

• In simdjson werden JSON-Daten wie ein einziges langes Band behandelt und Daten werden wiederverwendet. Anders gesagt: Für Strings oder Zahlen wird kein separater Speicher allokiert, stattdessen wird alles linear verarbeitet. Das ist ein gängiger Trick.

Leistung kontinuierlich messen

• Die Entwicklung war Benchmark-getrieben. In unserer CI sind Performance-Benchmarks enthalten.

• Nebenbei sollte man sich bei CPU-intensiven Aufgaben immer vor Augen halten, dass sich die Taktfrequenz der CPU fortlaufend verändert.

[Konkrete Beispiele]

Beispiel 1: Prüfen, ob es gültiges UTF-8 ist

• Das Prüfen, ob beliebige Eingabedaten gültige UTF-8-Codepoints bilden, ist normalerweise eine Aufgabe mit mehreren Verzweigungen.

• Wir haben mit SIMD eine Methode entwickelt, um 32 Byte Daten in höchstens 20 Zyklen ohne Verzweigungen auf gültiges UTF-8 zu prüfen.

• Da ein UTF-8-Byte als Integer den Wert 244 nicht überschreiten kann, lädt man die Daten per SIMD in ein 256-Bit-Register, subtrahiert dann von jedem Byte per Saturation Arithmetic den Integerwert 244 und prüft anschließend nur noch, ob es keinen von null verschiedenen Wert gibt.

• Diese Methode ist mehr als 20-mal schneller als ein Verfahren mit Verzweigungen!

Beispiel 2: Zeichentypen klassifizieren

• Um JSON zu parsen, muss man verschiedene Zeichen wie Komma, Doppelpunkt, Klammern oder Leerraum nach Typ klassifizieren.

• Auf x86-64 und ARM NEON gibt es einen Befehl, der Lookup-Tabellen mit einer Größe von 16 Byte auf einen Schlag durchsuchen kann.

• Man teilt ein Byte in die oberen 4 Bit und die unteren 4 Bit, wendet auf beide jeweils vorbereitete Lookup-Tabellen an und verknüpft die Ergebnisse dann mit einer AND-Operation.

• Der Code sieht zwar schmutzig aus, aber mit nur fünf Befehlen lassen sich so 16 Zeichen ohne Verzweigungen klassifizieren.

Beispiel 3: Escape-Zeichen erkennen

• Kann man Escape-Zeichen, die durch ein vorangestelltes Backslash (\) dargestellt werden, ohne Verzweigungen erkennen? Besonders muss man dabei auch den Fall behandeln, dass mehrere Backslashes hintereinander auftreten, weil auch der Backslash selbst escaped werden kann.

• Für solche Fälle gibt es den Trick, nur auf die Backslashes an ungeraden Positionen zu schauen.

• Hält man Bitmasken für gerade und ungerade Positionen als Konstanten vor, kann man mit komplizierten Bitoperationen Escape-Zeichen ohne Verzweigungen herausfiltern.

• Filtert man die escaped Anführungszeichen heraus, bleiben die Anführungszeichen übrig, die Strings markieren.

• Legt man die so ermittelten Positionen der Anführungszeichen als Bitmaske ab und wendet wiederholt XOR-Bitoperationen an, erhält man eine Bitmaske, die die Positionen von Strings angibt. Dieser Teil lässt sich auf den meisten Prozessoren mit nur einem einzigen Befehl erledigen.

• Es gibt auch einen Trick dafür, Bitmengen und String-Positionen einander zuzuordnen, aber aus Zeitgründen wird das übersprungen.

Beispiel 4: Zahlen parsen

• Zahlen zu parsen ist extrem teuer. In einem Benchmark mit einer gut optimierten C-Funktion zum Parsen von Gleitkommazahlen kam eine verrückte Geschwindigkeit von 0,09 GB/s heraus. Das war ganz offensichtlich ein Bottleneck.

• Der meiste Code zum Parsen von Zahlen arbeitet üblicherweise byteweise. Schnell ist das keineswegs.

• Nimmt man acht Zeichen auf einmal, macht daraus einen einzigen 64-Bit-Integer und setzt ihn in eine bestimmte Formel ein, die sich der Vortragende an einem späten Samstagabend ausgedacht hat, kann man erkennen, ob diese acht Zeichen acht aufeinanderfolgende Ziffern sind. Das ist besonders wichtig, weil das Parsen umso länger dauert, je mehr Stellen eine Zahl hat.

• Auf Stack Overflow fand sich auch ein Code-Snippet, um achtstellige Integer schnell zu parsen. Mit SIMD lässt sich das noch etwas verbessern, aber wichtig ist vor allem die Idee dieser Strategie, große Datenmengen auf einmal zu verarbeiten.

[Sonstiges]

Runtime-Dispatch

• Weil viel hardwareabhängiger Code enthalten ist, gibt es für jeden Prozessor optimierte Funktionen. Zur Laufzeit jeweils die zur Prozessorart passende Funktion aufzurufen, war allerdings ziemlich schwierig.

• Man versteht vielleicht nicht sofort, warum das schwierig ist, aber das Problem war, so etwas portabel und compilerunabhängig zu implementieren. Manche Compiler hatten Bugs, und auf Sprachebene gibt es dafür auch keine direkte Unterstützung.

• Dieser Punkt war wichtig, weil simdjson eine Open-Source-Bibliothek als Single-Header-Datei ist, die sich leicht in andere Projekte integrieren lässt.

Weitere Punkte

• Es gibt Wrapper für verschiedene Sprachen.

• Es gibt eine Portierung für Rust, und Portierungen für Go und C# sind in Vorbereitung, aber keine für Java.

• Die verschiedenen mathematischen Formeln, die in diesem Projekt verwendet wurden, hat er zusammen mit dem Mitautor Geoff Langdale entwickelt; dazu wurde ein entsprechendes Paper im VLDB Journal veröffentlicht. ( https://doi.org/10.1007/s00778-019-00578-5 )

[xguru]

Wow, das war sehr gut zu lesen. Vielen Dank!