ASTs und die Verflachung von Compiler-Datenstrukturen

• Wenn man einen AST nicht als über Pointer verbundenen Objektgraphen, sondern als ein einzelnes Array plus Indizes darstellt, werden Speicherlayout und Verwaltung compilerartiger Datenstrukturen einfacher
• Das Rust-Beispiel implementiert einen verflachten AST mit nur kleinen Änderungen: Box<Expr> wird durch ExprRef ersetzt und ExprPool um add/get ergänzt
• In einem Mikrobenchmark, der etwa 100 Millionen AST-Knoten erzeugt und sofort interpretiert, braucht die normale Implementierung 3,1 Sekunden, die verflachte 1,3 Sekunden und ist damit 2,4× schneller
• Der Leistungsunterschied ergibt sich aus Lokalität durch zusammenhängendes Speicherlayout, kleineren Referenzen durch 32-Bit-Indizes statt 64-Bit-Pointern sowie günstiger Allokation und Freigabe auf Pool-Ebene
• Nutzt man die Eigenschaft, dass Kinder im Array vor ihren Eltern liegen, wird aus einer rekursiven Baumtraversierung eine lineare Ausführung, die einem Bytecode-Interpreter nahekommt

---

Grundidee der Verflachung

• Arenas oder Regions sind in modernen Sprachimplementierungen weit verbreitet; der hier behandelte Ansatz ist Datenstruktur-Verflachung, bei der eine Arena für nur einen Typ wie ein einfaches Array verwendet wird
• Es handelt sich um eine Technik, bei der Pointer in pointerlastigen Datenstrukturen durch Array-Indizes ersetzt werden; das zentrale Beispiel ist ein AST, sie ist aber auch auf andere Compiler-Datenstrukturen anwendbar
• Der Beispielcode liegt im flatcalc-Repository, und die Unterschiede zwischen normaler und verflachter Implementierung sind im Branch-Vergleich zu sehen
• Der Code-Änderungsumfang ist klein, im Mikrobenchmark zeigt sich aber eine 2,4× höhere Geschwindigkeit; neben Performance gibt es auch Vorteile bei der Nutzbarkeit des Codes

Übliche AST-Darstellung

• Die Beispielsprache ist eine sehr einfache Sprache für arithmetische Ausdrücke, die nur Integer-Literale und vier binäre arithmetische Operatoren unterstützt
  • Mögliche Programmbeispiele sind 42, 0 + 14 * 3, (100 - 16) / 2
• Die Rust-Darstellung besteht aus den Enums BinOp und Expr
  • Expr::Binary(BinOp, Box<Expr>, Box<Expr>)
  • Expr::Literal(i64)
• Rusts Box<Expr> entspricht einem Pointer auf ein Expr und spielt eine ähnliche Rolle wie Expr* in C
• Parser, Ausgabeformatierer und Interpreter sind typisch aufgebaut; der Interpreter ist als rekursive Methode auf Expr geschrieben
• Die arithmetische Semantik ist so angelegt, dass jeder Ausdruck am Ende zu einem i64 ausgewertet wird
  • Addition, Subtraktion und Multiplikation verwenden Wrapping-Operationen
  • Division durch 0 wird mit checked_div so behandelt, dass 0 zurückgegeben wird
• Ein Generator für Zufallsprogramme mit festem PRNG-Seed misst die Performance der AST-Manipulation, ohne Parsing- und Ausgabekosten

AST durch Array und Indizes ersetzen

• Verflachung besteht aus zwei Änderungen
  • Expr-Objekte werden nicht einzeln auf dem Heap allokiert, sondern in einem zusammenhängenden Array gespeichert
  • Kindknoten werden nicht per Pointer, sondern über Indizes innerhalb des Arrays referenziert
• Im Rust-Beispiel wird ExprPool als Newtype für Vec<Expr> definiert

struct ExprPool(Vec<Expr>);

• Die Rolle des bisherigen Pointers übernimmt ExprRef auf Basis eines 32-Bit-Integers

struct ExprRef(u32);

• Die zentrale Typänderung ist, die Kindfelder von Binary von Box<Expr> auf ExprRef umzustellen

enum Expr {
    Binary(BinOp, ExprRef, ExprRef),
    Literal(i64),
}

• ExprPool erhält die Hilfsfunktionen add zum Einfügen eines neuen Expr und get zum Finden eines Expr per ExprRef
• Der Parser gibt nicht direkt ein Expr zurück, sondern fügt den Knoten in ExprPool ein und gibt danach eine ExprRef zurück
• Auch der Interpreter wird nicht mehr eine Expr-Methode, sondern eine ExprPool-Methode; vor dem Pattern Matching dereferenziert er die Referenz mit self.get(expr)
• Insgesamt ist die Änderung klein: Box<Expr> wird durch ExprRef ersetzt und an den nötigen Stellen werden add und get eingefügt

Performance-Vorteile

• Der typische Vorteil eines verflachten AST ist Speicherlokalität
  • Ein gewöhnliches pointerbasiertes Expr birgt das Risiko von Speicherfragmentierung
  • Verflachte Exprs liegen dicht in einem zusammenhängenden Speicherbereich, wodurch Daten-Cache und Prefetcher besser arbeiten können
  • Ein ausreichend intelligenter Speicherallokator kann möglicherweise ähnliche Effekte erzielen, aber ein dichtes Array reduziert die Unsicherheit
• Auch die Referenzgröße sinkt
  • Normale Pointer sind auf modernen Architekturen 64 Bit groß
  • Wenn höchstens 4.294.967.295 AST-Knoten benötigt werden, reicht eine 32-Bit-Referenz
  • Pro Referenz ist eine Platzersparnis von 50 % möglich, was bei pointerlastigen ASTs den gesamten Speicherverbrauch senken kann
  • Für kleinere Datenstrukturen sind auch 16-Bit- oder 8-Bit-Referenzen möglich
• Die Allokationskosten sinken
  • Es muss nicht für jeden Knoten malloc aufgerufen werden
  • Wenn genügend Speicher vorab reserviert wurde, kann per Bump Allocation durch Erhöhen eines Tail-Pointers Platz für ein neues Expr geschaffen werden
• Die Freigabe kann auf Pool-Ebene erfolgen
  • Dabei gilt die Annahme, dass einzelne Exprs nicht separat freigegeben werden
  • In vielen Sprachimplementierungen werden ASTs gemeinsam erzeugt und verschwinden gemeinsam wieder
  • Ein normaler AST muss durch das Folgen von Pointern Knoten für Knoten freigegeben werden, während ein verflachter AST den gesamten ExprPool auf einmal freigeben kann
• In Einführungen zu Arena Allocation wird günstige Freigabe oft als Hauptgrund hervorgehoben, in Compiler-Umgebungen kann ein AST aber bis zum Ende der Kompilierung erhalten bleiben, sodass Freigabe womöglich der am wenigsten wichtige Grund ist

Vorteile für die Nutzbarkeit des Codes

• Verflachung vereinfacht Lifetime-Management
  • Einen AST mit n Knoten kann man als einen AST-Lifetime statt als n Lifetimes betrachten
  • In Rust wirkt sich diese Vereinfachung direkt auf die Lifetime-Darstellung im Code aus
  • Statt die Lifetimes von &Exprs zu verwalten, kann man ein u32-basiertes ExprRef weitergeben und sich auf die Lifetime von ExprPool stützen
• Dieselbe Einfachheit kann auch in Sprachen mit manueller Speicherverwaltung wie C++ gelten
• Ein verflachtes Array macht Deduplizierung leichter umzusetzen
  • Mit hash consing oder einem einfacheren Verfahren lässt sich vermeiden, identische Ausdrücke mehrfach zu erzeugen
  • Beispielsweise kann man die häufig genutzten Literal-Ausdrücke von 0 bis 127 in den ersten 128 Slots von ExprPool reservieren
  • Wird das Integer-Literal 42 benötigt, kann ExprRef(42) zurückgegeben werden, ohne ein neues Expr zu erstellen
• In pointerbasierten Darstellungen ist Ähnliches ebenfalls möglich, dürfte aber eher zusätzliche Datenstrukturen erfordern

Ergebnisse des Mikrobenchmarks

• Der Benchmark erzeugt ein Zufallsprogramm mit etwa 100 Millionen AST-Knoten und gibt es direkt an den Interpreter weiter
  • Parser und Ausgabeformatierer sind nicht enthalten
  • Weil ein Programm erzeugt und sofort ausgeführt wird, ist es kein realistischer Benchmark
• Die Versuchsbedingungen haben mehrere Einschränkungen
  • Für Vec<Expr> wird vorab genügend Platz für das gesamte Programm reserviert
  • In realen Umgebungen braucht es mehr Abschätzung der Arena-Größe
  • Da außer Erzeugung und Ausführung kaum Arbeit anfällt, können die Vorteile günstiger Allokation und Freigabe übertrieben erscheinen
  • Da das Programm zu groß ist, um in den CPU-Cache zu passen, könnte der Lokalitätseffekt unterschätzt werden
• Mit Hyperfine wurden auf einem Laptop Durchschnittswerte über 10 Läufe verglichen
  • Die Umgebung ist ein M1 Max mit 10 Kernen bei 3,2 GHz, 32 GB Speicher, macOS 13.3.1 und Rust 1.69.0
• Die normale Implementierung braucht 3,1 Sekunden, die verflachte 1,3 Sekunden und zeigt damit eine 2,4× höhere Geschwindigkeit
• Um die Freigabekosten separat zu betrachten, wurde für beide Implementierungen eine Version erstellt, die Deallocation überspringt
  • Bei der verflachten Implementierung sind die Zeiten der No-Free-Version und der Standardversion fast gleich, sodass die Freigabezeit nicht groß war
  • Die normale Implementierung sinkt von 3,1 auf 1,9 Sekunden, sie verbrachte also etwa 38 % mit Speicherfreigabe
  • Selbst beim Vergleich der No-Free-Versionen ist die verflachte Implementierung 1,5× schneller als die normale

Ein Interpreter, der die verflachte Darstellung direkt nutzt

• Verflachung wurde zunächst wie eine interne Implementierungsänderung eingesetzt, die normale Allokation und Pointer ersetzt, aber man kann die Eigenschaften der Array-Darstellung auch direkt nutzen
• Wenn Expr unveränderlich ist, müssen Kindknoten zuerst und Elternknoten später erzeugt werden
  • Beim Erzeugen von a * b liegen a und b im ExprPool vor dem *, der auf sie verweist
  • Referenzpfeile zeigen im Array immer von hinten nach vorn, und der Datenfluss läuft nach vorn
• Mit dieser Invariante kann man statt eines rekursiven Abstiegs von der Wurzel einen Interpreter bauen, der ExprPool von Anfang bis Ende scannt
  • Die Traversierung besucht Kinder immer vor ihren Eltern
  • Das Ergebnis jedes Ausdrucks wird in einem state-Vektor gespeichert
  • Ein binärer Ausdruck holt sich seine Werte, indem er state über die Indizes der Kind-ExprRefs abfragt
  • Am Ende wird das Ergebnis zurückgegeben, das zur angefragten root gehört
• Dieser „extra-flat“ Interpreter hat kein Stack-Management für rekursive Aufrufe und kann ExprPool linear durchlaufen
• Umgekehrt muss er zufällig auf einen großen state-Vektor zugreifen, was für die Lokalität nachteilig sein kann
• Im Ergebnis braucht der extra-flat Interpreter 1,2 Sekunden, der rekursionsbasierte verflachte Interpreter 1,3 Sekunden, also eine Verbesserung um 8,2 %

Verbindung zu Bytecode-Interpretern

• Bob Nystroms Reddit-Kommentar sieht in diesem Ansatz im Grunde eine Neuerfindung der Idee eines Bytecode-Interpreters
• Die Expr-Struktur verhält sich wie eine Bytecode-Instruktion, und Variablenreferenzen liegen wie als u32 codierte Referenzen darin
• Ersetzt man die einfache state-Tabelle durch eine stackartige Struktur, unterscheidet sich das kaum von einem von Grund auf entworfenen Bytecode-Interpreter
• Obwohl nur die AST-Datenstruktur geändert wurde, bewegt man sich bei der Baumtraversierung ganz natürlich in Richtung Bytecode-Ansatz

Verwandte Materialien

• Materialien zur Verflachung im Compiler-Kontext
  • Mike Pall führt einen Teil der LuaJIT-Performance auf eine „linear, pointer-free IR“ zurück
  • Ein Artikel zur Performance des Sorbet-Typecheckers für Ruby hebt die Vorteile von Packed Arrays und der Umstellung von 64-Bit-Pointern auf 32-Bit-Indizes hervor
  • Das Oil-Shell-Projekt stellt eine Linksammlung zu kompakter AST-Darstellung bereit
• Ähnliche Ideen tauchen auch in performanceorientierten Bereichen außerhalb der Sprachimplementierung auf
  • Gibbon von Purdue und Indiana ähnelt der Arbeit, Programme, die wie normaler Code aussehen, in eine verflachte Implementierung zu übertragen
  • Andrew Kelley behandelt in einem Vortrag zu data-oriented design den Ansatz, Indizes statt Pointer zu verwenden
  • Ein Übersichtsartikel zu Rust-Arena-Bibliotheken behandelt die Lifetime-Nutzbarkeit rund um Arenas
  • Ein Artikel zu Handles vs. Pointern in der Spieleentwicklung argumentiert dafür, Objekte desselben Typs in Arrays zu sammeln und per Index zu referenzieren
  • Artikel zu ECS behandeln Themen rund um Lokalität
• Inanna Malicks Artikel über eine Rust-Taschenrechnersprache als Toy-Projekt wendet dieselbe Technik an und nutzt zugleich Ideen aus der Welt der Haskell Recursion Schemes

[GN⁺]

Meinungen auf Hacker News

• Blender (3D-Modellierungssoftware) ist ein interessantes Beispiel für diesen Ansatz. Um das Laden/Speichern von Dateien schnell und verlustfrei zu machen, wird dieselbe Darstellung auf der Festplatte und im Speicher verwendet.
  Das heißt, alles liegt in einer Arena, und Speichern/Laden kommt im Wesentlichen einem memcpy der gesamten Arena nahe. Angesichts der potenziellen Komplexität des Blender-Projekts und der Probleme rund um Serialisierung/Deserialisierung wirkt das wie ein hervorragendes Design.
  Der Nachteil ist, dass sich das Design der Datenstrukturen leicht festfährt, weil auch Dateien aus älteren Versionen geöffnet werden können müssen.

  • Der fehlende Baustein bei „das Design der Datenstrukturen fährt sich fest, weil alte Versionsdateien geöffnet werden können müssen“ ist eine Methode, Datenstrukturen über die Zeit weiterzuentwickeln, ähnlich wie bei Datenbankmigrationen.
    Solche Transformationen führt man nur beim Laden von Daten aus alten App-Versionen aus; danach speichert man sie sofort in der aktualisierten Version wieder auf die Festplatte, sodass dieselben Kosten nicht erneut anfallen.
    https://www.inkandswitch.com/cambria/, entstanden im CRDT-Kontext, ist ein Implementierungsbeispiel für dieses Konzept und kann, selbst wenn es nicht direkt anwendbar ist, eine gute Inspiration sein.
  • Ich habe einmal an einer großen kommerziellen App gearbeitet, die auf einem selbstgebauten I/O-Framework nach einem ähnlichen Prinzip basierte, und es war wirklich schmerzhaft.
    Ob einem das I/O-Framework gefiel oder nicht: Es serialisierte Strukturen einfach unverändert, sodass man wusste, für immer an diese Struktur gebunden zu sein, und Datenstrukturen immer zukunftssicher entwerfen musste. Das waren finstere Zeiten.
  • Ich glaube, Microsoft Word in der alten „doc“-Ära hat Strukturen ebenfalls einfach direkt auf die Festplatte gedumpt.
    Deshalb wurde das Schreiben von Konvertern zu einem großen Problem, und ich erinnere mich, dass man undokumentierte interne Datenstrukturen von Word entschlüsseln musste.
  • Ein PlayStation-Spiel, an dem ich gearbeitet habe, funktionierte genau so, und da alles signiert war, machte man sich überhaupt keine Sorgen um Angreifer.
    Wenn man die Dateien auf der Disc ändern konnte, bedeutete das ohnehin, dass man das Gerät bereits übernommen hatte. Dadurch war das Laden absurd schnell: Alles wurde in den Speicher gelesen, danach wurden nur noch die Pointer-Positionen auf die tatsächlich geladenen Adressen gepatcht.
  • Soweit ich weiß, hat Microsoft Word anfangs ebenfalls diesen Ansatz verwendet, und als sich das Dateiformat weiterentwickelte, wurde das sehr schmerzhaft.

• Ich mag abgeflachte abstrakte Syntaxbäume. Besonders gefällt mir der Ansatz, der in pulldown-cmark für die Verarbeitung von Inline-Markup verwendet wird. Eine kurze Erklärung gibt es unter https://fullyfaithful.eu/pulldown-cmark/.
  Die Roheingabe wird in eine Sequenz von Nodes zerlegt; Dinge wie * können zu Hervorhebungen werden oder, wenn es kein Gegenstück gibt, als Text stehen bleiben, also werden sie zu MaybeEmphasis-Nodes.
  Im nächsten Schritt läuft man mit einem Stack der Reihe nach durch die Nodes und sucht mögliche Paare. Wird ein Paar gefunden, wird der MaybeEmphasis-Node in den passenden Hervorhebungs-Node umgewandelt, und die gesamte Node-Sequenz zwischen öffnendem und schließendem Node wird ausgeschnitten und zum Teilbaum des neuen Nodes gemacht.
  Diese Baumtransformation ist ziemlich ungewöhnlich; eine naive Implementierung kann leicht O(n) werden, aber mit einer abgeflachten AST-Darstellung lässt sie sich unabhängig von der Zahl der Nodes oder der Stack-Tiefe in O(1) erledigen.
  Die genaue Baumdarstellung findet sich unter https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...; im Wesentlichen gibt es neben dem Node-Body die Indizes child und next. Der Code für die Baumchirurgie beim Emphasis-Matching steht unter https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6....
  Die Performance ist hervorragend. pulldown-cmark ist vielleicht nicht der einzelne schnellste CommonMark-Parser, aber er ist absolut konkurrenzfähig und zum Beispiel deutlich schneller als Ansätze, die pro Node eine Allokation vornehmen.

• Ich erinnere mich an einen GDC-Vortrag, in dem Rust gelobt wurde. Es ging darum, dass Rust einen wegen des Borrow Checkers entweder in den Wahnsinn treibt oder einen dazu bringt, den Code als Entity-Component-System zu strukturieren.
  Interessant ist, dass der Wert des Borrow Checkers in realen Fällen mit komplexen Lifetime-Problemen letztlich darin liegt, dass man dazu gebracht wird, alles in Arrays zu packen und per Index zu referenzieren, um dem Borrow Checker möglichst aus dem Weg zu gehen.

  • Nach meiner kurzen Erfahrung mit der Bevy-Game-Engine von Rust fühlte sich ein Entity-Component-System an wie sehr anspruchsvoller Spaghetti-Code.
    Weil Objekte einander nicht mehr direkt referenzieren, nimmt der Nutzen des Typsystems stark ab, und der Code wird sehr schwer nachvollziehbar. Ich glaube, dass es in sehr großen Systemen nützlich sein kann, aber in dem kleinen Programm, das ich schrieb, war es eher ein Hindernis.
  • Stimmt. Rusts Lifetimes verlieren in bestimmten Bereichen der Hochleistungsprogrammierung an Wirkung, in denen man den Heap vermeidet oder es gar keinen Heap gibt.
    Dazu gehören Spiele, Datenbanken, Embedded, batchartige High-Performance-Computing-Workloads und sogar Compiler.
    Natürlich gibt es weiterhin Alias-Beschränkungen, sodass keine Data Races entstehen, aber Bugs, die im Kern denselben Charakter haben wie Bugs durch rohe Pointer, können weiterhin auftreten.
  • Anders gesagt kann man es so sehen, dass langlebige Entitäten Speicher besitzen und gezwungen werden, ihn an kurzlebige Objekte auszuleihen.
    Dabei lebt der Entleiher immer kürzer als der Besitzer und kann nur auf den Speicher zugreifen, der ihm im Besitzkontext zugewiesen ist. Wenn der Besitzer stirbt, wird freigegeben; danach kann niemand ihn verwenden oder erneut freigeben, wodurch use-after-free, doppelte Freigaben und Zugriffe auf nicht zugewiesenen Speicher vermieden werden.
  • Stimmt. Ich sehe immer wieder, dass bei Arenen oder abgeflachten Baum-/Graphstrukturen die Speichersicherheit ausgeklammert wird.
    Es gibt auch die seltsame Behauptung, Arenen würden in C Probleme der Speichersicherheit lösen; je nach Programm können sie aber genauso gut Dangling Pointer oder use-after-free usw. verursachen.
    Dasselbe Problem zeigt sich in C/C++ und Rust jeweils auf etwas unterschiedliche Weise.
    Mein Kommentar zu diesem Artikel von vor zwei Monaten: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
    Kurz gesagt: Die Vorteile sind sehr real, aber die Nachteile sollte man ebenfalls nennen. Arenen schieben Speichersicherheit nach hinten; Ownership kann knifflig sein, Änderungen und das Hinzufügen von Listen/Vektoren werden ebenfalls komplexer, und Pointer-Darstellungen sind debuggerfreundlicher.
    Unten in diesem Artikel ist meine Wiki-Seite verlinkt; ich fand sie dank der echten Codebeispiele und Messwerte hilfreich: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
  • Pointer sind lediglich Indizes in einen Speicherraum. Wenn Rust allgemeine Programmierprobleme lösen will, scheint der Borrow Checker nicht nur mit speicherraumspezifischen Indizes umgehen können zu müssen, sondern mit allen Indizes.

• Prolog-Terme werden in der Warren Abstract Machine (WAM) ebenfalls auf diese Weise auf dem Heap dargestellt. Schreibt man den Prolog-Term +(*(a,b), c) aus dem Beispiel des Artikels in Operatornotation, sieht das so aus:
  expr(E) :- E = a*b + c.
  Dann entsteht auf dem globalen Stack der virtuellen Maschine eine abgeflachte Darstellung. In Scryer Prolog kann man sich die WAM-Instruktionen mit ?- wam_instructions(expr/1, Is), maplist(portray_clause, Is). ansehen.
  Das Ergebnis sieht etwa so aus: put_structure(*,2,x(3))., set_constant(a)., set_constant(b)., put_structure(+,2,x(2))., set_value(x(3))., set_constant(c)., execute(=,2).
  Beide zusammengesetzten Terme werden linearisiert und liegen auf dem Heap in der Form Funktor gefolgt von Argumenten; jedes davon belegt genau eine Speicherzelle der WAM. Argumente können auf andere Speicherzellen zeigen.
  Der Heap ist ein Array solcher Zellen, und alle Zellen haben denselben konkreten Typ. Scryer Prolog verwendet zum Beispiel 8 Byte pro Zelle, wodurch Zugriff und Modifikation von Zellen auf 64-Bit-Architekturen sehr effizient sind.

• „Statt Expr-Objekte wild auf dem Heap zu allozieren, legt man sie in einem einzigen zusammenhängenden Array ab und referenziert Kinder per Index in dieses Array statt per Pointer“ ist weniger Abflachung als vielmehr eine alternative Heap-Darstellung. Die Form des AST selbst hat sich nicht geändert.
  Das ist ein Ansatz, den viele Sprachen schon lange verfolgen, etwa Lisp-artige Systeme, die Cons-Zellen und andere Objekte in ein Array legen und Bump Allocation sowie Index-Pointer verwenden.
  Wenn Objekte in einem Array liegen, kann der Garbage Collector nach der Mark-Phase in der Sweep-Phase bequem darüber iterieren. Die Mark-Phase läuft durch den Graphen und findet erreichbare Objekte; die Sweep-Phase geht durch das flache Array, löscht GC-Bits und markiert nicht erreichbare Objekte zur Wiederverwendung.
  Man wird kaum eine halbwegs ernsthafte Lisp-Implementierung finden, die für jede Cons-Zelle separat malloc aufruft. Dann müsste man sie für die Sweep-Phase des GC in eine globale verkettete Liste einhängen oder ein globales Array haben, das nur Pointer enthält.
  Ich habe mindestens zweimal Spielzeug-Lisp-Projekte gesehen, die an einem Wochenende entstanden waren, Cons-Zellen per malloc allozierten, sie leakten und den GC als riesiges TODO stehen ließen.
  Selbst wenn Zellen aus einem kompakten Array-Heap kommen, kann am Ende trotzdem ein globales Array entstehen. Wenn man zum Beispiel in einem nicht kopierenden Allocator generationelle Garbage Collection implementiert, kann man junge Objekte in ein Hilfsarray eintragen, um sie in schnellen GC-Zyklen zu sweepen; dieses Array repräsentiert dann die Nursery.

• Ein guter Artikel, aber er hat zwei Fallstricke

  1. Wenn man Nodes in einem größenveränderbaren Array speichert, braucht der Compiler mit wachsendem Eingabeprogramm einen immer größeren zusammenhängenden Speicherblock. Den Block gibt es vielleicht, vielleicht auch nicht. Man kann das umgehen, indem man Blöcke in Seitengröße alloziert und als Pool verwendet
  2. Man muss darauf achten, wie AST-Nodes im Code repräsentiert werden. Speichert man Nodes zum Beispiel als Union-Typ, wird die Union so groß wie ihr größtes Member, und da nicht alle AST-Nodes gleich groß sind, werden kleine Nodes unnötig auf die Größe des größten Nodes aufgepolstert
  • Dass kleine AST-Nodes wegen der Größe des größten AST-Nodes unnötig gepolstert werden, ist ein wirklich guter Punkt, den ich auch in meinem Blogbeitrag zu benutzerdefinierten Integer-Typen mit Bitbreite erwähnt habe: https://alic.dev/blog/custom-bitwidth
    Tagged Unions sind ebenfalls möglich, aber man muss den Speicherverbrauch geschickt handhaben
  • Manchmal denke ich, es wäre schön, wenn wir nicht bei einem flachen Adressraum gelandet wären
    Die Technik der „virtuellen Speicherverwaltung“ ermöglicht es, fragmentierte physische Speicherbereiche zu einem zusammenhängenden virtuellen Speicherbereich zusammenzufügen. Wenn der virtuelle Adressraum segmentiert gewesen wäre, wäre er von vornherein nicht fragmentiert worden, und jeder Speicherbereich hätte stets an Ort und Stelle wachsen können, ohne mit einem anderen Bereich zu kollidieren
    Dann hätte eine realloc()-Implementierung den memcpy()-Pfad weglassen können – schade
  • Das lässt sich mit einer Rope-ähnlichen Struktur, die Vektoren in Chunks fester Größe aufteilt, und echten Pointern abmildern. Reallokation wird dadurch überflüssig
    Intern wäre das zwar unsicher, aber eine sichere, nur lesende Schnittstelle scheint möglich. Das Freigeben wäre O(n), aber immer noch deutlich schneller als bei einem Baum

• Ich war überrascht, dass in den Nodes noch zwei Pointer („Referenzen“) verbleiben, obwohl man nun wissen kann, dass der erste Pointer immer genau auf den nächsten Node zeigt
  Ich habe gesehen, dass https://github.com/rswier/c4 so vorgeht. Die Lesbarkeit des Codes ist natürlich nicht gut, aber er ist kleiner und schneller

• Wenn man bei Speicherverwaltung von Arena spricht, denke ich eher an einen Arena-Allocator als an „Flattening“
  Dabei alloziert man viele Elemente mit gleicher Lebensdauer effizienter aus einem oder mehreren großen Speicherblöcken und gibt, wenn die gemeinsame Lebensdauer endet, statt der einzelnen Elemente die großen Blöcke frei
  Da man den Speicher im übergeordneten Block nur sequenziell verbrauchen muss, braucht man keine Free Lists wie bei einem allgemeinen Heap-Allocator; auch die Allokation kann dadurch effizienter sein
  In diesem Kontext kann man das „Flattening“, bei dem Indizes statt Pointer verwendet werden, auch als relative Pointer zum übergeordneten Block auffassen, also als Offsets

• Bei der Implementierung von V7 (https://github.com/cesanta/v7), einem JavaScript-Parser und -Interpreter für extrem speicherbeschränkte Embedded-Umgebungen, haben wir eine solche kompakte AST-Struktur verwendet
  Später haben wir auf einen Schritt umgestellt, der vom AST in Bytecode kompiliert, aber eine Zeit lang haben wir den impliziten AST während der Interpretation direkt durchlaufen

• In meinem Yaml-to-Sql-Compiler unter https://yaml2sql.netlify.app habe ich etwas Ähnliches gemacht
  Der Flattening-Prozess ist etwas seltsam, aber interessant, und am Ende war er den Aufwand wert
  Zum Beispiel ist das Flattening boolescher Ausdrücke eine gute Übung für alle, die es ausprobieren möchten: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...