- Teilen von Strategien und gemessenen Leistungsdaten für das direkte Design und die Implementierung eines ultraschnellen Lexers für die Sprache purple-garden
- Einsatz verschiedener Optimierungstechniken wie Threaded Lexing (auf Basis einer Jump Table), Zero-Copy- und Window-Strings, Interning und Bump Allocator
- Maximierung der Parsing-Geschwindigkeit durch Token-Hashing und Hash-Vergleiche für Keyword-Tabellen; Jump Tables sind bei der CPU-Cache-Effizienz einem einfachen
switch überlegen
- Durch mmap der gesamten Datei und Minimierung dynamischer Allokationen werden die Kosten für I/O und Speicherverwaltung bei großen Eingaben deutlich gesenkt
- Im Vergleich zu bekannten bestehenden Lexern (z. B. flex, handcoded) wird eine bis zu mehr als 10-fach schnellere Verarbeitung nachgewiesen; inklusive Mikrobenchmark-Werten für Parsing- und Runtime-Phasen
Überblick über Lexing und die Compiler-Pipeline
- Der Lexer (Tokenizer) wandelt einen Eingabestring in eine Liste bedeutungstragender Tokens um; anschließend übernimmt der Parser diese und erzeugt einen AST (abstrakten Syntaxbaum)
- Das Token-Design in der Sprache purple-garden hält eine minimale Struktur bei, die nur das Enum TokenType sowie String- und Typinformationen speichert
Minimales Lexer-Design und Codebeispiele
- Die Lexer-Struktur speichert nur den Eingabestring und die aktuelle Position
- Token-Erzeugung je nach Zeichen per
switch
- Für das Debugging werden ein Mapping-Array von Typ zu String und typbasierte Initialisierung verwendet
Threaded Lexing (auf Basis einer Jump Table)
- Statt eines
switch-Statements wird eine Jump Table für die Unterscheidung von Tokens verwendet (Computed goto)
- In einem 256-Byte-Array werden Zeichenwerte als Index auf die jeweiligen Verarbeitungs-Labels abgebildet
- In der tatsächlichen Codeverzweigung wird mit dem Makro
JUMP_TARGET sofort zum Ziel verzweigt
- Vorteile:
- Weniger Cache-Misses und optimierte Branch Prediction führen zu schnellerer Ausführung
- Nachteile:
- Keine Unterstützung durch MSVC (nur Clang und GCC), schwieriger zu debuggen
Speicherverwaltung und Allocator-Abstraktion
- Definition einer Schnittstelle für verschiedene Speicherallokationsstrategien wie den Bump Allocator (Struktur
Allocator)
- Das Makro
CALL vereinfacht ausführliche Logs und die Übergabe von Kontext
- Es werden reale Strukturen und Codebeispiele für Allokation, Freigabe und Statistiken gezeigt
Zero-Copy- und Window-basierte String-Verarbeitung
- Für eine effiziente Verarbeitung in C wird die Struktur
Str eingeführt (Pointer, Länge, Hash)
- Dinge wie Slices,
concat, eq, Hashing und Zahlkonvertierung werden direkt selbst implementiert
- String-Slices entstehen sofort allein durch Pointer-Verschiebung, ganz ohne Speicherallokation
- Auch die Zahlkonvertierung wird über einen selbst implementierten Zeichen-zu-Integer-Algorithmus gelöst
Token-Hashing und Keyword-Vergleich über vorberechnete Hashes
- Beim Erzeugen von Tokens wird ein Hash (FNV-1a) berechnet, um wiederholte Vergleiche und Interning zu optimieren
- Konstante Keywords wie
true/false werden direkt per Hashwert verglichen und verzweigt, was die Performance verbessert
- Auch
is_alphanum (Erkennung von Buchstaben/Ziffern/Sonderzeichen) wird per Bit-Operationen und Lookup-Verfahren optimiert
Effizienteres Number Parsing und Verlagerung in die Compiler-Phase
- Der Lexer speichert bei Zahlentokens nur Window und Hash; die eigentliche Umwandlung in Integer/Floats erfolgt erst in der Compiler-Phase und nur ein einziges Mal
- Bei wiederholtem Parsen identischer Zahlenwerte wurde eine Verbesserung des Gesamtdurchsatzes um mehr als 64 % festgestellt
Beschleunigtes I/O für große Dateien
- Statt des bisherigen
fread-Ansatzes wird die komplette Datei per mmap direkt in den Speicher gemappt
- Die Funktion
IO_read_file_to_string mappt die gesamte Eingabe per mmap; bei großen Dateien wurden Leistungsverbesserungen um den Faktor 6 bis 35 festgestellt
Praxis-Benchmarks und Leistungsvergleich
- Auf einem Laptop: 44 ms (nur Tokenisierung) bei mehr als 1.000.000 Zeilen und 25 MB Eingabe
- Auf einem Desktop: 30 ms bei derselben Eingabe (bis zu 848 MB/s)
- Im Vergleich zu anderen Lexern mehr als 10-fach schneller (
0,3 s gegenüber 2–13 s)
- Mikrobenchmarks quantifizieren die Wirkung der einzelnen Optimierungen (z. B. Einführung des Bump Allocators 1,58-fach, 0-Alloc-Strings 1,4–1,5-fach, Verlagerung des Number Parsings in die Compiler-Phase 2,8-fach usw.)
Zusammenfassung der Implementierungsstrategie
- Direkte Verzweigung auf Basis einer Jump Table (Threaded Lexing)
- Zero-Copy-Window-Token-Struktur
- Interning konstanter Tokens
- Speicherverwaltung auf Basis eines Bump Allocators
- Token-Hashing und Vergleich über vorberechnete Hashes
- Verzögertes Parsing und Interning von Zahlen- und String-Tokens
- Verarbeitung großer Dateien per
mmap
- Als künftige Aufgaben werden SIMD-Nutzung, schnellere Hash-Algorithmen, Speicherausrichtung und Prefetching sowie eingabespezifische Optimierung der Jump Table genannt
Noch keine Kommentare.