ASTs und die Abflachung anderer Compiler-Datenstrukturen

• Arenen oder Regionen sind eine einfache und effektive Technik für Compiler und compilerähnliche Systeme.
• Die Abflachung abstrakter Syntaxbäume (ASTs) mit Arenen kann die Leistung verbessern und mehr Komfort bieten.
• Abflachung bedeutet, AST-Knoten in ein einziges Array zu packen und statt Zeigern Array-Indizes zu verwenden.
• Abgeflachte ASTs bieten Vorteile wie bessere Lokalität, kleinere Referenzen sowie günstigere Allokation und Freigabe.
• Abgeflachte ASTs können die Speicherverwaltung vereinfachen und eine bequeme Deduplizierung ermöglichen.
• Leistungsergebnisse zeigen, dass eine abgeflachte Interpreter-Version 2,4-mal schneller sein kann als eine normale Version.
• Durch die Nutzung der flachen AST-Darstellung lassen sich Rekursionen entfernen und lineare Durchläufe nutzen, um die Leistung weiter zu verbessern.
• Der Artikel behandelt die Leistungssteigerungen, die durch die Abflachung von Datenstrukturen in einem Interpreter für Programmiersprachen erzielt wurden.
• Zusätzlich zeigt der abgeflachte Interpreter im Vergleich zum rekursiven Interpreter eine Leistungsverbesserung von 8,2 %, mit 1,2 Sekunden gegenüber 1,3 Sekunden.
• Die Technik erfindet im Wesentlichen die Idee eines Bytecode-Interpreters neu, wobei die Expr-Struktur als Bytecode-Befehl verwendet wird.
• Erwähnt werden weitere Artikel und Projekte zur Abflachung von Datenstrukturen im Zusammenhang mit LuaJIT, dem Sorbet-Type-Checker und der Oil-Shell.
• Ähnliche Konzepte rund um Abflachung und Lokalitätsoptimierung tauchen auch in Bereichen wie Videospielen, der Verarbeitung serialisierter Daten, datenorientiertem Design und Entity-Component-Systemen auf.
• Der Artikel empfiehlt außerdem den Beitrag von Inanna Malick, die dieselbe Technik auf eine in Rust implementierte Spielzeug-„Rechner“-Sprache anwendet.
• Es werden Einschränkungen bei der Verwendung dieser Technik in Rust diskutiert, darunter die Grenze, dass andere Expr-Elemente nicht inline innerhalb der Expr-Struktur enthalten sein können.
• Die Leistungsvergleiche wurden auf einem MacBook Pro mit M1-Max-Prozessor und 32 GB Arbeitsspeicher durchgeführt, auf dem macOS 13.3.1 und Rust 1.69.0 liefen.

[GN⁺]

Hacker-News-Kommentar

• Blender verwendet auf der Festplatte und im Speicher dieselbe Darstellung, um Dateien schnell und verlustfrei zu laden und zu speichern.
• In pulldown-cmark wird ein abgeflachter AST verwendet, um Inline-Markup effizient zu parsen.
• Eine abgeflachte AST-Darstellung ermöglicht O(1)-Baumtransformationen unabhängig von der Anzahl der Knoten oder der Stacktiefe.
• Die Performance von pulldown-cmark ist im Vergleich zu anderen CommonMark-Parsern herausragend.
• Die Warren Abstract Machine (WAM) verwendet für Prolog eine abgeflachte Darstellung auf dem Heap.
• Das Abflachen von ASTs war bereits ein Konzept, das in Sprachen wie Lisp verwendet wurde.
• Das Speichern von Knoten in einem dynamisch skalierbaren Array kann Probleme bei der Speicherallokation verursachen, lässt sich aber durch Pooling in Blöcken der Seitengröße abmildern.
• Es ist Vorsicht dabei geboten, wie AST-Knoten im Code dargestellt werden, und unnötiges Padding sollte vermieden werden.
• Die Verwendung von Indizes statt Zeigern kann zu kleinerem und schnellerem Code führen.
• Abgeflachter Speicher kann mit benutzerdefinierten Speicherallokatoren implementiert werden, die in bestimmten Szenarien nützlich sind.
• Für die Implementierung eines JavaScript-Parsers und -Interpreters in speicherbeschränkten Umgebungen wurde eine kompakte AST-Struktur verwendet.