serde_json: 20 % schnellere String-Verarbeitung

 (purplesyringa.moe)
2 Punkte von GN⁺ 2024-08-25 | 1 Kommentare | Auf WhatsApp teilen
  • serde_json, das im Rust-Ökosystem wie der Standard-JSON-Parser verwendet wird, erzielt in Benchmarks mit vielen Strings allein durch kleine interne Optimierungen Leistungsverbesserungen von 10 %, 23 % und 32 %
  • Die Berechnung von Fehlerpositionen wurde so geändert, dass statt eines direkten Scans des String-Anfangs mit memchr die Zeilenzahl und der letzte Zeilenumbruch gesucht werden; dadurch schrumpft der Abstand zum Erfolgspfad, nachdem der Fehlerpfad zuvor mehr als doppelt so langsam war
  • Die zentrale Schleife des String-Parsings sucht \, " und Steuerzeichen nicht mehr getrennt, sondern prüft sie mit SWAR auf einmal und erreicht so auch ohne echtes SIMD niedrige Latenz bei kurzen Strings
  • Das Dekodieren von \u-Escapes reduziert mit LUT, vorzeichenbehafteten Ganzzahlen und vorab geshifteten Tabellen die Kosten für Branches und Shifts; das Parsen von russischem War and Peace als JSON wurde dadurch von 284 MB/s auf 344 MB/s beschleunigt
  • Die anschließend zum Bottleneck gewordene UTF-8-Kodierung wird über manuelle UTF-8-Erzeugung gelöst, die die Initialisierungs- und Kopierkosten von char::encode_utf8 und Vec::extend_from_slice vermeidet; derselbe Benchmark steigt damit auf 374 MB/s

Warum die Optimierung von serde_json so viel bewirkt

  • serde ist das führende Framework für Serialisierung und Deserialisierung in Rust, und serde_json wird als offizielle Kombination für die JSON-Verarbeitung breit eingesetzt
  • Zum Zeitpunkt der Veröffentlichung hatte serde_json 26.916 Reverse Dependencies, simd-json dagegen 66
  • Bei einer Nutzung in dieser Größenordnung können selbst kleine Verbesserungen innerhalb von serde_json einen kumulativen Effekt im gesamten Rust-Ökosystem haben
  • Da viele Nutzer nicht ohne Weiteres auf einen anderen JSON-Parser wechseln, sind risikoarme Optimierungen innerhalb der bestehenden Library praktisch sinnvoll

Fehlerpositionsberechnung: von einfacher Schleife zu memchr

  • In Benchmarks für den Fehlerpfad war serde_json bei denselben Daten mehr als doppelt so langsam wie im Erfolgspfad
    • In den Datensätzen canada, citm_catalog und twitter war der Fehlerpfad gegenüber dem Erfolgspfad um -48 % bis -77 % langsamer
  • Der Bottleneck war die Funktion position_of_index(), die für die Formatierung von Fehlermeldungen einen Index in line/column umrechnet
    • Die bisherige Implementierung durchlief self.slice[..i] byteweise und aktualisierte line und column bei jedem \n
  • Teilt man die Berechnung in zwei Schritte auf, lässt sich memchr einsetzen
    • Die Anzahl der \n in self.slice[..i] zählen, um die nullbasierte line-Nummer zu erhalten
    • Die Position des letzten \n finden und von i abziehen, um die column-Nummer zu erhalten
  • memchr bietet optimierte Implementierungen für die Suche nach einzelnen Zeichen und für das Zählen; intern wird SIMD verwendet
  • Nach dem Merge von PR #1160 verbesserte sich die Performance des Fehlerpfads deutlich
    • Bei canada DOM stieg der Fehlerpfad von 122 MB/s auf 216 MB/s
    • Bei citm_catalog struct stieg er von 195 MB/s auf 736 MB/s
    • Der Fehlerpfad blieb zwar langsamer als der Erfolgspfad, der Abstand wurde aber kleiner

Suche nach String-Escapes: drei Bedingungen auf einmal finden

  • Die bisherige zentrale Schleife beim String-Parsing lief anhand einer ESCAPE-Tabelle über Bytes hinweg, die kein Escape waren
    • In JSON-Strings müssen \, " sowie ASCII-Steuerzeichen bis einschließlich 0x1F speziell behandelt werden
    • Laut JSON-Spezifikation sind Steuercodes innerhalb von Strings nicht erlaubt
  • Der erste Versuch bestand darin, mit memchr2 zunächst \ oder " zu finden und danach Steuerzeichen separat zu prüfen
    • Dadurch wurde der String einmal schnell und einmal langsam durchlaufen, also zweimal, und das war langsamer als zuvor
    • Wenn man nur eine einfache Hälfte vektorisiert und den Rest skalar belässt, ergibt sich daraus keine Gesamtverbesserung
  • Der zweite Versuch kombinierte memchr2 mit manuellem SIMD, um zu prüfen, dass keine Steuerzeichen vorhanden sind
    • Bei kurzen Strings wurde der Overhead des Funktionsaufrufs für die Laufzeit-Auswahl teuer
    • Bei langen Strings blieb das Problem bestehen, den Speicher zweimal zu lesen
  • Die finale Implementierung wurde darauf ausgerichtet, \, " und Steuerzeichen in einem einzigen Pass zu finden

SIMD-nahe Verarbeitung mit SWAR

  • Um keinen plattformspezifischen SIMD-Code einbauen zu müssen, wird die Technik SWAR (SIMD Within A Register) verwendet
    • Statt 128-Bit-SIMD wird ein 64-Bit-Wort wie acht Bytes behandelt
    • Mit Bitoperationen wird gleichzeitig geprüft, ob jedes Byte eine Bedingung erfüllt
  • Die Prüfung auf Steuerzeichen wird von der Bedingung c >= 0 && c < 0x20 in eine Bitoperationsform umgewandelt
    • Für 8-Byte-Blöcke wird das mit einer Maske der Form !c & (c - 0x2020202020202020) & 0x8080808080808080 geprüft
    • Der Borrow einer 64-Bit-Subtraktion kann zwar in höherwertige Bytes propagieren, für das Ziel, das Steuerzeichen an der niedrigsten Position zu finden, ist das aber kein Problem
  • \ und " werden auf ähnliche Weise geprüft und zu einem Ausdruck zusammengeführt
    • Der Gesamtausdruck besteht aus 9 Bitoperationen
    • Mit x86-SIMD wären 7 Operationen nötig; der Durchsatz ist also geringer, bei kurzen Strings ist aber die Latenz wichtiger
  • Im json-benchmark war dieser SWAR-Code effizienter als echter SIMD-Code
  • Bei sehr kurzen Strings kann SWAR langsamer sein als skalarer Code
    • Bei Strings mit etwa 5 Zeichen zeigte sich eine Regression
    • Um häufige Muster wie den leeren String "" und aufeinanderfolgende Escapes wie \r\n oder \uD801\uDC37 zu schützen, wird vor Eintritt in die SWAR-Schleife geprüft, ob das erste Zeichen ein Escape ist
  • Die Ergebnisse der Optimierung der String-Suche fielen je nach Datensatz unterschiedlich aus
    • twitter struct stieg von 638 MB/s auf 785 MB/s, also +23 %
    • twitter DOM stieg von 305 MB/s auf 335 MB/s, also +10 %
    • citm_catalog struct stieg von 865 MB/s auf 905 MB/s, also +5 %
    • Leere Strings wurden in einem bestimmten Mikrobenchmark weiterhin um weniger als 2 % langsamer

Optimierung der Unicode-Escape-Dekodierung

  • serde_json verarbeitet sowohl rohe Unicode-Strings als auch \u-Escapes
    • Zum Beispiel: "🥺" und "\ud83e\udd7a"
  • Die bisherige Hex-Dekodierung nutzte eine LUT mit 256 Einträgen, um jedes Zeichen auf einen Wert von 0 bis 15 abzubilden
    • Verarbeitet werden '0'..='9', 'A'..='F' und 'a'..='f'
    • Ungültige Zeichen werden mit einem Sentinel-Wert markiert
  • Da ein \u-Escape 4 Hex-Digits liest, enthielt die bisherige Methode pro Iteration Shift, Addition, Vergleich und bedingten Branch
  • Die verbesserte Implementierung gibt nicht während der Schleife bei jedem Fehler zurück, sondern verarbeitet alle 4 Stellen und prüft danach die Gültigkeit
  • Die finale Implementierung nutzt eine [i8; 256]-LUT, in der ungültige Digits -1 sind, und rechnet mit 32-Bit-Integern
    • Bei Erfolg ist das Ergebnis nicht negativ, bei Fehler negativ
    • Auf x86 können Speicher-Load und Sign Extension zu movsx kombiniert werden
  • Um die Shift-Latenz zu verringern, werden zwei Tabellen verwendet
    • HEX0: der ursprüngliche Wert
    • HEX1: eine Tabelle, in der der Wert vorab um 4 Bit nach links geshiftet ist
  • Das Ganze wurde als klar entrollte Implementierung von decode_four_hex_digits() aufbereitet
  • Durch diese Optimierung stieg die Performance beim Parsen von russischem War and Peace in JSON-kodierter Form von 284 MB/s auf 344 MB/s, eine Verbesserung um 21 %

UTF-8-Kodierung als Bottleneck und manuelle Erzeugung

  • Nach der Unicode-Escape-Dekodierung verlagerte sich der Bottleneck zur UTF-8-Kodierung
  • UTF-8 kodiert Codepoints je nach Länge in 1 bis 4 Bytes
    • 1 Byte: 0xxxxxxx
    • 2 Bytes: 110xxxxx 10xxxxxx
    • 3 Bytes: 1110xxxx 10xxxxxx 10xxxxxx
    • 4 Bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • char::encode_utf8 aus der Rust-Standardbibliothek schreibt in einen &mut [u8]-Buffer, der daher bereits gültige u8-Werte enthalten muss
    • In einen uninitialisierten Buffer kann nicht direkt geschrieben werden
    • Weil UTF-8 eine Kodierung variabler Länge ist, ist es für LLVM schwierig, unnötige Zeroization zu entfernen
  • serde_json verarbeitete dies mit scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())
    • Bei Verwendung eines lokalen [0u8; 4]-Buffers könnte die Alias-Analyse theoretisch helfen
    • In der Praxis erzeugt LLVM wegen der variablen Kopie von 1 bis 4 Bytes einen memcpy-Aufruf
  • Um memset- und memcpy-Aufrufe zu vermeiden, wird UTF-8 direkt erzeugt
    • Der Algorithmus selbst ist einfach, erforderte aber unsafe
    • Zusammen mit einigen kleinen Änderungen verbesserte sich der War and Peace-Benchmark weiter von 344 MB/s auf 374 MB/s, also um zusätzliche +9 %

Endergebnis

  • In JSON-Benchmarks mit vielen Strings verbesserte sich die Performance von serde_json um 10 %, 23 % und 32 %
  • Da viele JSON-Daten zahlreiche Strings enthalten, kann diese Optimierung Auswirkungen auf Rust-Code insgesamt haben, der serde_json nutzt
  • Die Verbesserungen entstanden dadurch, dass nacheinander verschiedene Bottlenecks beseitigt wurden: Fehlerpositionsberechnung, Suche nach String-Escapes, Dekodierung von Unicode-Escapes und UTF-8-Kodierung

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-08-25
Hacker-News-Meinungen

  • UTF-8-Tricks machen mich ziemlich nervös, weil ich schon zu viele Parser-Confusion-Angriffe gesehen habe
    serde nutzt man eher wegen der Korrektheit als wegen der Geschwindigkeit; ich hoffe also, sie haben es mit massenhaft ungültigen UTF-8-Strings bis zum Ende durchgefuzzt

    • Zum Glück ist die UTF-8-Struktur im Vergleich zu einem durchschnittlichen Parser sehr einfach
      Das heißt nicht, dass es keine Bugs gibt, aber der interne Zustand des Parsers sollte nicht groß sein, und exhaustive Tests wirken machbar
    • Genau in diesem Bereich würde ich gern die Ergebnisse eines Fuzzers sehen
    • Kannst du ein Beispiel nennen, das dir bei dieser Art von Bug sofort einfällt?

  • Es ist cool, wie schnell sich serde bewegt
    Ich habe gerade simdutf8 angeschaut und festgestellt, dass der PR für SIMD-gestütztes UTF-8-Parsing schon fast fünf Jahre alt ist
    https://github.com/rust-lang/rust/issues/68455

  • In diesem Blog habe ich starke jart-Vibes gespürt und ihn deshalb gern gelesen
    Bei der Stelle „wir werden das Rad neu erfinden müssen, aber wenn man darüber nachdenkt, ist das ziemlich großartig“ weiß ich nicht, ob sie ernst gemeint oder ironisch ist
    Beim Lesen fing ich an zu lachen, weil ich mich über den Autor lustig machte, aber der Rest der Seite wirkt ziemlich selbstironisch

    • Ich glaube, damit ist nicht gemeint, dass die Tatsache, das Rad neu erfinden zu müssen, großartig ist, sondern der Ansatz
    • Was bedeutet jart?

  • „Zu lehren, wie man denkt, ist genauso wichtig wie das Lehren des Programmierens, passiert aber fast nie“
    Das klingt nach der Arroganz, zu glauben, das Gegenüber denke nicht

    • Ich sehe in diesem Satz keine Arroganz
      Er nimmt nicht an, dass andere Menschen nicht denken, sondern beobachtet eher, dass die meisten Blogposts und Anleitungen nur das Endergebnis zeigen und nicht unbedingt die Schritte dorthin
    • Der Autor behauptet das nicht
      Zu lehren, wie man denkt, bedeutet, dass man recherchieren muss und diesen Schritt nicht überspringen kann; und dass die Recherche einem nicht die Verantwortung abnimmt, selbst zu einem Schluss zu kommen
      Eines von beidem zu überspringen ist leicht, aber falsch

  • serde_json belegt nach je einem Debug- und Release-Build 3 GB an Abhängigkeiten
    Wenn man serde in ein paar aktiven Projekten verwendet, ist der Speicherplatz schnell weg
    Ich verstehe nicht, warum JSON-Parsing 3 GB Abhängigkeiten braucht; ich bin für Code-Wiederverwendung, aber die JSON-Abhängigkeiten von serde wirken ziemlich chaotisch
    Wenn in einer dieser Abhängigkeiten ein Exploit auftaucht, ist die Hälfte des Rust-Ökosystems verwundbar
    Rust sollte JSON eingebaut haben

    • Es gibt nur fünf Abhängigkeiten, eine davon ist optional und eine andere ist serde selbst: https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      Es ist sehr wahrscheinlich, dass das, was du tatsächlich gemessen hast, nicht „3 GB Abhängigkeiten“ sind
      Ich kann es nicht sicher sagen, weil du es ohne Belege als Tatsache darstellst, aber ich würde vermuten, dass durch viel Nutzung von #[derive(Serialize, Deserialize)] eine große Menge Code generiert wurde und du danach die Gesamtgröße des target-Verzeichnisses misst
      Ein einfacher Build liegt, wie andere Kommentare gezeigt haben, im Bereich von einigen Dutzend MB
    • JSON in Rust einzubauen halte ich nicht für einen sinnvollen Ansatz
      Das würde nur Bloat hineinziehen, und da die Standardbibliothek abgesehen von Stabilitätsgarantien nicht anders ist als andere Crates, bringt es keinen Vorteil
      Am Ende koppelt man damit nur den Release-Zyklus der Bibliothek an den Release-Zyklus des Compilers
      Früher war rustc-serialize tatsächlich nahezu eingebaut; Rust hat diese Richtung also bereits ausprobiert
      Außerdem ist serde_json im Default-Zustand nicht groß
      Weder serde_json noch serde sind groß, und beide halten eine sehr niedrige MSRV ein, die andere Crates kaum unterstützen, sodass sie faktisch gar nicht viele Abhängigkeiten haben können
    • Dependency-Bloat ist ein generelles Problem in Rust
      Der Abhängigkeitsbaum eines halbwegs großen Rust-Projekts wird schnell ziemlich furchtbar, all diese Abhängigkeiten zu auditieren ist praktisch unmöglich, und bei vielen von ihnen ist das Vertrauen eher gering
      Nachdem ich ein paar Jahre mit Rust gearbeitet habe, werde ich Rust wohl nicht wieder anfassen, bis das Ökosystem deutlich reifer ist
      Diese Reife wird erst durch breite Enterprise-Adoption kommen; andernfalls würde ich es nur für no-std-, no-deps- oder reine C-Ersatzprojekte nutzen
      Sobald Zig stabil ist, könnte es Rust allerdings auch in diesem Einsatzbereich verdrängen
    • Rust spuckt ungewöhnlich viele Debug-Informationen aus
      Das ist so grotesk groß, dass ich einfach von einem Bug ausgehe
      Egal was man kompiliert, im target-Ordner sammeln sich Gigabytes an, aber das ist nicht repräsentativ für das finale Artefakt, nachdem man Debug-Informationen entfernt oder zumindest weniger detaillierte Einstellungen verwendet hat
    • Bei einem Projekt von gewisser Größe scheint der target-Ordner buchstäblich immer mindestens ein paar GB groß zu sein