Wie man einen schnellen Interpreter für dynamische Sprachen baut

• Selbst ein Interpreter mit direktem AST-Traversal kann allein durch Werte-Repräsentation, Inline-Caches, Objektmodell, Watchpoints und wiederholte Detailoptimierungen große Leistungsgewinne erzielen
• Die Zef-Baseline, bei der Performance fast keine Rolle spielte, war 35-mal langsamer als CPython 3.10, 80-mal langsamer als Lua 5.4.7 und 23-mal langsamer als QuickJS-ng 0.14.0, erreichte aber nach 21 Optimierungsschritten eine Beschleunigung um das 16,646-Fache
• Der größte Sprung entstand durch die Kombination aus Neuentwurf des Objektmodells und Inline-Caches; darauf folgte eine weitere 4,55-fache Verbesserung durch Storage- und Offsets-basierten Zugriff, gecachte AST-Spezialisierung und Watchpoints zur Überwachung von Namensüberschreibungen
• Weitere Verbesserungen summierten sich durch Entfernung stringbasierter Dispatches, Einführung von Symbolen, Änderung der Struktur der Argumentübergabe, Spezialisierung von Gettern und Settern, Fast Paths für Hashtabellen sowie Spezialisierungen für Array-Literale und sqrt·toString
• Einschließlich des Yolo-C++-Portings wurde eine Geschwindigkeit von 66,962-mal der Baseline erreicht; damit ist es 1,889-mal schneller als CPython 3.10 und 2,968-mal schneller als QuickJS-ng 0.14.0, wegen fehlender Speicherfreigabe jedoch für langfristige Workloads ungeeignet

---

Einführung und Evaluierungsmethodik

• Das Ziel der Optimierung ist ein Interpreter mit direktem AST-Traversal; Ziel ist es, die aus Spaß entwickelte dynamische Sprache Zef auf ein mit Lua, QuickJS und CPython konkurrenzfähiges Niveau zu bringen
  • Im Fokus stehen nicht JIT-Compiler oder Feintuning eines ausgereiften GC, sondern Optimierungen, die auch von einem Ausgangspunkt ohne solides Fundament anwendbar sind
  • Behandelt werden Werte-Repräsentation, Inline-Caching, Objektmodell, Watchpoints und die wiederholte Anwendung naheliegender Optimierungen
• Allein mit den im Text beschriebenen Verfahren wurde ohne SSA, GC, Bytecode oder Maschinencode eine starke Leistungssteigerung erreicht
  • Nach Maßgabe des Haupttexts eine 16-fache Beschleunigung
  • Einschließlich des unvollständigen Yolo-C++-Portings eine 67-fache Beschleunigung
• Für die Performance-Auswertung wurde die Benchmark-Suite ScriptBench1 verwendet
  • Enthaltene Benchmarks sind der OS-Scheduler Richards, der Constraint-Solver DeltaBlue, die Physik-Simulation N-Body und der Binärbaum-Test Splay
  • Verwendet wurden bestehende Ports für JavaScript, Python und Lua
  • Die Python- und Lua-Ports von Splay wurden mit Claude erzeugt
• Die Testumgebung bestand aus Ubuntu 22.04.5, Intel Core Ultra 5 135U, 32 GB RAM und Fil-C++ 0.677
  • Lua 5.4.7 wurde mit GCC 11.4.0 kompiliert
  • Für QuickJS-ng 0.14.0 wurde das Binary aus den GitHub-Releases verwendet
  • CPython 3.10 stammt aus der Standardauslieferung von Ubuntu
• Für alle Experimente wurde der Mittelwert aus 30 zufällig durchmischten Läufen verwendet
• Die meisten Vergleiche wurden zwischen dem mit Fil-C++ kompilierten Zef-Interpreter und anderen mit dem Yolo-C-Compiler gebauten Interpretern durchgeführt

Der ursprüngliche Zef-Interpreter

• Er wurde mit nahezu keiner Rücksicht auf Performance geschrieben; ausdrücklich genannt werden nur zwei performancebewusste Entscheidungen

• Werte-Repräsentation

  • Verwendung eines 64-Bit-tagged value
    • Darstellbare Werte sind double, 32-Bit-Integer und Object*
  • double wird über ein 0x1000000000000-Offset dargestellt
    • Vorgestellt als Technik, die aus JavaScriptCore übernommen wurde
    • In der Literatur als NuN tagging bezeichnet
  • Integer und Pointer verwenden ihre native Darstellung
    • Das beruht auf der Annahme, dass Pointer-Werte nicht kleiner als 0x100000000 sind
    • Das wird ausdrücklich als riskante Entscheidung bezeichnet
    • Als Alternative wird erwähnt, dass man Integer mit dem High-Bit-Tag 0xffff000000000000 hätte markieren können
  • Mit dieser Darstellung lassen sich für numerische Operationen Fast Paths auf Basis von Bit-Tests implementieren
  • Noch wichtiger ist der Vorteil, Heap-Allokationen für Zahlen zu vermeiden
  • Beim Bau eines neuen Interpreters ist es wichtig, früh eine gute grundlegende Werte-Repräsentation zu wählen; spätere Änderungen sind sehr schwierig
  • Als Ausgangspunkt für die Implementierung einer dynamisch typisierten Sprache werden 32-Bit- oder 64-Bit-tagged values vorgeschlagen

• Wahl der Implementierungssprache

  • Gewählt wurde eine C++-artige Sprache, die genügend Spielraum für Optimierungen bietet
  • Es wird ausdrücklich gesagt, dass man Java wegen seiner Grenze bei Low-Level-Optimierungen nicht wählen würde
  • Rust wird ebenfalls ausgeschlossen, da die Implementierung einer Sprache mit GC globale veränderliche Zustände und eine Heap-Darstellung mit zyklischen Referenzen benötigt
    • Wenn man eine mehrsprachige Architektur in Kauf nimmt oder viel unsafe-Code zulässt, sei ein teilweiser oder vollständiger Einsatz von Rust aber denkbar

• Falsche Entscheidungen aus Sicht des Performance-Engineerings

  • Verwendung von Fil-C++
    • Damit ließ sich schnell entwickeln und GC wurde kostenlos mitgeliefert
    • Verletzungen der Speichersicherheit werden mit Diagnosedaten und Stack-Traces gemeldet
    • Es gibt kein undefiniertes Verhalten
    • Die Performance-Kosten liegen meist bei etwa dem Vierfachen
  • Rekursiver AST-Walking-Interpreter
    • Struktur mit an vielen Stellen überschriebenen virtuellen Methoden vom Typ Node::evaluate
  • Übermäßiger Gebrauch von Strings
    • Ein Get-AST-Knoten speichert ein std::string, das den Variablennamen beschreibt
    • Bei jedem Variablenzugriff wird dieser String verwendet
  • Übermäßiger Gebrauch von Hashtabellen
    • Bei der Ausführung von Get wird in einer std::unordered_map mit einem String-Key nachgeschlagen
  • Scope-Auflösung über rekursive Aufrufketten
    • Erlaubt ist Verschachtelung fast aller Strukturen sowie Closures
    • Bei Verschachtelungen wie Funktion F mit Klasse A und Funktion G in Klasse B können Methoden von A A-Felder, lokale Variablen von F, B-Felder und lokale Variablen von G sehen
    • Die ursprüngliche Implementierung behandelte das mit rekursiven C++-Funktionen, die verschiedene Scope-Objekte abfragen

• Eigenschaften der ursprünglichen Implementierung

  • Trotz der falschen Entscheidungen ließ sich mit wenig Code ein ziemlich komplexer Sprachinterpreter bauen
  • Das größte Modul ist der Parser
  • Der Rest ist eher einfach und klar gehalten

• Anfangs-Performance

  • Der ursprüngliche Interpreter ist 35-mal langsamer als CPython 3.10

  • 80-mal langsamer als Lua 5.4.7

    • 23-mal langsamer als QuickJS-ng 0.14.0

Gesamte Optimierungsübersicht

• Die Tabelle fasst die Performance-Änderungen von Zef Baseline bis Zef Change #21: No Asserts sowie Zef in Yolo-C++ zusammen
  • Vergleichsspalten sind vs Zef Baseline, vs Python 3.10, vs Lua 5.4.7 und vs QuickJS-ng 0.14.0
• In der letzten Zeile ist Zef Change #21: No Asserts gegenüber der Baseline 16,646-mal schneller

  • 2,13-mal langsamer als Python 3.10

  • 4,781-mal langsamer als Lua 5.4.7

    • 1,355-mal langsamer als QuickJS-ng 0.14.0

• Zef in Yolo-C++** ist gegenüber der Baseline** 66,962-mal schneller

  • 1,889-mal schneller als Python 3.10

  • 1,189-mal langsamer als Lua 5.4.7

    • 2,968-mal schneller als QuickJS-ng 0.14.0

Frühe Optimierungsphase

• Optimierung #1: Operatoren direkt aufrufen

  • Der Parser erzeugt Operatoren nicht mehr als DotCall-Knoten mit einem Operatornamen, sondern erstellt für jeden Operator separate AST-Knoten
  • In Zef sind a + b und a.add(b) identisch
    • Ursprünglich wurde a + b als DotCall(a, "add") mit Argument b geparst
    • Bei jeder arithmetischen Operation fiel ein Lookup des Stringnamens der Operatormethode an
    • DotCall übergibt den String an Value::callMethod
    • Value::callMethod führt mehrfache Stringvergleiche aus
  • Nach der Änderung erzeugt der Parser Binary<>- und Unary<>-Knoten
    • Mit Templates und Lambdas werden für jeden Operator unterschiedliche Node::evaluate-Overrides bereitgestellt
    • Jeder Knoten ruft direkt den schnellen Value-Pfad des jeweiligen Operators auf
    • Zum Beispiel ruft a + b erst Binary<lambda for add>::evaluate und dann Value::add auf
  • Der Performance-Effekt beträgt 17,5 % Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 30-mal langsamer als CPython 3.10
    • 67-mal langsamer als Lua 5.4.7
    • 19-mal langsamer als QuickJS-ng 0.14.0

• Optimierung #2: RMW-Operatoren direkt aufrufen

  • Normale Operatoren wurden schneller, aber RMW-Formen wie a += b verwendeten weiterhin stringbasierten Dispatch
  • Der Parser wurde so geändert, dass er für jeden RMW-Fall separate Knoten erzeugt
  • Der Parser fordert LValue-Knoten auf, sich über einen virtuellen Aufruf von makeRMW selbst durch RMW zu ersetzen
  • Zu RMW werdende LValues sind Get, Dot und Subscript
    • Get entspricht dem Variablenlesen id
    • Dot entspricht expr.id
    • Subscript entspricht expr[index]
  • Jeder virtuelle Aufruf verwendet das Makro SPECIALIZE_NEW_RMW
    • SetRMW steht für id += value
    • DotSetRMW steht für expr.id += value
    • SubscriptRMW steht für expr[index] += value
  • Die Operatorspezialisierung aus Änderung #1 verwendet Lambda-Dispatch
  • RMW verwendet ein enum
    • Gewählt wurde es, weil alle drei Pfade get, dot und subscript behandelt werden und das enum an mehrere Stellen weitergereicht werden muss
    • Letztlich übernimmt die Template-Funktion Value::callRMW<> den eigentlichen Dispatch des RMW-Operatoraufrufs
  • Der Performance-Effekt beträgt 3,7 % Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 29-mal langsamer als CPython 3.10
    • 65-mal langsamer als Lua 5.4.7
    • 18,5-mal langsamer als QuickJS-ng 0.14.0
    • 1,22-mal schneller als der Ausgangspunkt

• Optimierung #3: IntObject-Prüfung vermeiden

  • Ein Engpass war, dass der schnelle Pfad von Value isInt() nutzt und dessen internes isIntSlow() einen virtuellen Aufruf von Object::isInt() ausführt
  • In der ursprünglichen Werte-Repräsentation gab es vier Fälle
    • tagged int32
    • tagged double
    • IntObject für int64, die nicht als int32 darstellbar sind
    • alle übrigen Objekte
  • Auch im Fall von IntObject übernahm Value den Dispatch der Integer-Methoden
    • Damit alle Implementierungen arithmetischer Operationen an einer Stelle bleiben, nämlich in Value
  • Nach der Optimierung berücksichtigt der schnelle Pfad von Value nur noch int32 und double
    • Die Logik zur Verarbeitung von IntObject wurde in IntObject selbst verschoben
    • Der bisher bei jedem Methoden-Dispatch anfallende isInt()-Aufruf entfällt
  • Der Performance-Effekt beträgt 1 % Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 29-mal langsamer als CPython 3.10
    • 65-mal langsamer als Lua 5.4.7
    • 18-mal langsamer als QuickJS-ng 0.14.0
    • 1,23-mal schneller als der Ausgangspunkt

• Optimierung #4: Symbol

  • Der ursprüngliche Interpreter verwendete std::string fast überall
  • Kostspielige Einsätze von Strings gab es in Context::get, Context::set, Context::callFunction, Value::callMethod, Value::dot, Value::setDot, Value::callOperator<> sowie in der Object::callMethod-Familie
  • In dieser Struktur handelte es sich nicht um einfache Hash-Tabellen-Lookups, sondern um Hash-Tabellen-Lookups mit String-Schlüsseln, sodass zur Laufzeit String-Hashing und -Vergleiche wiederholt wurden
  • Die Optimierung ersetzt stringbasierte Lookups durch hash-consed Symbol-Objektpointer
  • Eine neue Symbol-Klasse wurde hinzugefügt
    • Implementiert in symbol.h und symbol.cpp
    • Symbol und String lassen sich gegenseitig umwandeln
    • Bei der Umwandlung von String zu Symbol erfolgt Hash Consing über eine globale Hash-Tabelle
    • Dadurch reicht letztlich ein Identitätsvergleich von Symbol*-Pointern, um festzustellen, ob es sich um dasselbe Symbol handelt
  • Anstelle von String-Literalen werden vorab vorbereitete Symbole verwendet
    • Zum Beispiel Symbol::subscript statt "subscript"
  • Viele Funktionssignaturen wurden von const std::string& auf Symbol* umgestellt
  • Der Performance-Effekt beträgt 18 % Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 24-mal langsamer als CPython 3.10
    • 54-mal langsamer als Lua 5.4.7
    • 15-mal langsamer als QuickJS-ng 0.14.0
    • 1,46-mal schneller als der Ausgangspunkt

• Optimierung #5: Value inline setzen

  • Im Kern geht es darum, Inlining wichtiger Funktionen zu ermöglichen
  • Im Zentrum fast aller Änderungen steht die Einführung des neuen Headers valueinlines.h
  • Der Grund für die Trennung von value.h in einen separaten Header ist, dass Header verwendet werden, die value.h einbinden müssen
  • Der Performance-Effekt beträgt 2,8 % Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 24-mal langsamer als CPython 3.10
    • 53-mal langsamer als Lua 5.4.7
    • 15-mal langsamer als QuickJS-ng 0.14.0
    • 1,5-mal schneller als der Ausgangspunkt

Neugestaltung von Objektmodell und Cache-Struktur

• Optimierung #6: Objektmodell, Inline-Cache, Watchpoint

  • Die Funktionsweise von Object, ClassObject und Context wurde umfassend umgebaut, um die Kosten der Objektallokation zu senken und beim Zugriff Hash-Tabellen-Lookups zu vermeiden
  • Diese Änderung kombiniert drei Funktionen: Objektmodell, Inline-Cache und Watchpoint

• Objektmodell

  • Zuvor wurde für jeden lexikalischen Scope ein Context-Objekt alloziert
    • Jeder Context besaß eine Hash-Tabelle, die die Variablen dieses Scopes enthielt
  • Objekte hatten eine komplexere Struktur
    • Jedes Objekt besaß eine Hash-Tabelle, die die Klassen, deren Instanz es ist, auf Context abbildet
  • Diese Struktur war wegen Vererbung und verschachtelter Scopes nötig
    • Wenn Bar von Foo erbt, schließen Bar und Foo jeweils unterschiedliche Scopes ein
    • Sie können auch unterschiedliche private Felder mit demselben Namen haben
  • Die neue Struktur führt das Konzept von Storage ein
    • Daten werden anhand von Offsets gespeichert
    • Welcher Offset verwendet wird, bestimmt ein Context
  • Context existiert weiterhin, wird aber nicht bei der Erzeugung von Objekt oder Scope erstellt, sondern vorab im resolve-Pass des AST
  • Wenn tatsächlich ein Objekt oder Scope erzeugt wird, wird nur Storage entsprechend der von diesem Context berechneten Größe alloziert

• Inline-Cache

  • Eine Technik, bei der an einer Codeposition wie expr.name der zuletzt gesehene dynamische Typ von expr und der zuletzt aufgelöste Offset von name gespeichert werden
  • Eine klassische Technik, die meist im JIT-Kontext erklärt wird, hier aber auf einen Interpreter angewendet wird
  • Die gespeicherten Informationen werden umgesetzt, indem auf gewöhnlichen AST-Knoten per Placement-Konstruktion spezialisierte AST-Knoten erzeugt werden

• Bestandteile des Inline-Cache

  • CacheRecipe
    • Verfolgt, was ein bestimmter Zugriff getan hat und ob er cachebar ist
  • An vielen Stellen in Context, ClassObject und Package werden Aufrufe von CacheRecipe eingefügt
    • Damit werden Informationen über den Zugriffsvorgang gesammelt
  • AST-Auswertungsfunktionen wie Dot::evaluate übergeben das CacheRecipe, das sie aus der von ihnen ausgeführten polymorphen Operation erhalten haben, zusammen mit this an constructCache<>
  • constructCache
    • Kompiliert je nach CacheRecipe eine neue Spezialisierung des AST-Knotens
    • Erzeugt über einen Template-Mechanismus verschiedene spezialisierte AST-Knoten
    • Bei Zugriff auf lokale Variablen erfolgt ein direkter Load aus dem übergebenen storage
    • Führt einen class check aus, um zu prüfen, ob die Klasse noch der zuletzt gesehenen entspricht
    • Führt danach einen direkten Funktionsaufruf auf die zuletzt gesehene Funktion aus
    • Kombiniert bei Bedarf chain step und watchpoint
  • AST-Knoten, die gecacht werden können, besitzen jeweils eine cached variant
    • Zuerst wird ein schneller Aufruf über das cache-Objekt versucht
    • Den Typ des cache-Objekts bestimmt constructCache<>

• Watchpoint

  • Es wird ein Beispiel gezeigt, in dem in einem lexikalischen Scope eine Variable x existiert, darin eine Klasse Foo definiert ist und eine Methode von Foo auf x zugreift
  • Wenn es innerhalb von Foo keine Funktion oder Variable namens x gibt, scheint es, als könne direkt das äußere x gelesen werden
  • Allerdings kann eine Subklasse einen Getter x hinzufügen
  • In diesem Fall muss das Ergebnis des Zugriffs nicht das äußere x, sondern der Getter sein
  • Um solche Änderungsmöglichkeiten zu verarbeiten, richtet der Inline-Cache zur Laufzeit einen Watchpoint ein
  • Im Beispiel wird ein Watchpoint verwendet, der überwacht, ob dieser Name überschrieben wurde

• Warum die drei Funktionen gleichzeitig implementiert wurden

  • Mit dem neuen Objektmodell allein ist ohne gut funktionierende Inline-Caches kaum eine nennenswerte Verbesserung zu erreichen
  • Inline-Caches allein haben ohne Watchpoints wenig praktischen Nutzen, weil viele Cache-Bedingungen dann schwer sicher zu behandeln sind
  • Neues Objektmodell und Watchpoints müssen gut zusammenspielen

• Implementierungsverlauf und schwierige Teile

  • Begonnen wurde mit einer einfachen CacheRecipe-Version sowie mit dem Entwurf von Storage und Offsets, die schon nah an der endgültigen Form waren
  • Eine der schwierigsten Arbeiten war der Austausch der Implementierungsweise intrinsischer Klassen
  • Beispiel Array
    • Zuvor implementierte ArrayObject::tryCallMethod alle Methoden, indem es den virtuellen Aufruf von Object::tryCallMethod abfing
    • Im neuen Objektmodell hat Object weder eine vtable noch virtuelle Methoden
    • Stattdessen delegiert Object::tryCallMethod an object->classObject()->tryCallMethod(object, ...)
    • Um also Array-Methoden bereitzustellen, musste eine Array-Klasse selbst erzeugt werden, die diese Methoden besitzt
  • Dadurch wurde ein großer Teil der intrinsischen Funktionalität aus einer über die gesamte Implementierung verstreuten Struktur nach makerootcontext.cpp verlagert
  • Das wurde positiv bewertet, weil dadurch Inline-Caches auch auf native/intrinsische Funktionen von Objekten unverändert angewendet werden können
  • Der Performance-Effekt beträgt 4,55-fache Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 5,2-mal langsamer als CPython 3.10
    • 11,7-mal langsamer als Lua 5.4.7
    • 3,3-mal langsamer als QuickJS-ng 0.14.0
    • Gegenüber dem Ausgangspunkt 6,8-mal schneller
    • Es wird bewertet, dass sich der Rückstand von Fil-C++ gegenüber anderen Interpretern weitgehend auf das Niveau der Fil-C-Kosten verringert hat

Optimierung von Aufrufen und Zugriffspfaden

• Optimierung Nr. 7: Verbesserung der Struktur zur Argumentübergabe

  • Vor der Änderung übergab der Zef-Interpreter Funktionsargumente als const std::optional<std::vector<Value>>&
  • optional war nötig, weil in einigen Randfällen die folgenden beiden Fälle unterschieden werden mussten
    • o.getter
    • o.function()
  • In Zef sind beides meist Funktionsaufrufe, es gibt aber als Ausnahme den folgenden Code
    • o.NestedClass
    • o.NestedClass()
  • Ersteres gibt das NestedClass-Objekt selbst zurück
  • Letzteres erzeugt eine Instanz
  • Daher muss zwischen einem Funktionsaufruf ohne Argumente und einem getterartigen Aufruf mit leerem Argument-Array unterschieden werden
  • Die bisherige Struktur war jedoch ineffizient
    • Der Aufrufer führte eine vector-Allokation aus
    • Der Aufgerufene allokierte anschließend erneut einen arguments scope, der diesen Vektor kopierte
  • Die Änderung führt einen Arguments-Typ ein
    • Seine Form ist exakt identisch mit dem arguments scope, den zuvor der Aufgerufene erzeugte
    • Nun allokiert der Aufrufer direkt in diesem Format
  • Auch in Yolo-C++ verringerte das Entfernen von malloc für den vector backing store die Zahl der Allokationen
  • In Fil-C++ führt bereits std::optional selbst zu Heap-Allokationen
    • Auch ohne std::optional führt die Übergabe von const std::vector<>& ebenfalls zu Allokationen
    • Es wird erwähnt, dass als Stack-allokiert markierte Daten auf dem Heap allokiert werden
    • Zudem wurde angesprochen, dass der Aufrufer den Vektor nicht vorab dimensionierte und es daher zu mehrfachen Reallokationen kam
  • Ein großer Teil der Änderung bestand darin, Funktionssignaturen durch Arguments* zu ersetzen
  • Der Performance-Effekt beträgt 1,33x Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 3,9x langsamer als CPython 3.10
    • 8,8x langsamer als Lua 5.4.7
    • 2,5x langsamer als QuickJS-ng 0.14.0
    • 9,05x schneller als der Ausgangspunkt

• Optimierung Nr. 8: Getter-Spezialisierung

  • Zef hat ähnlich wie Ruby standardmäßig private Instanzfelder
  • Beispiel: class Foo { my f fn (inF) f = inF }
    • Der im Konstruktor empfangene Wert wird in der nur für die Instanz sichtbaren lokalen Variable f gespeichert
  • Selbst Instanzen desselben Typs können nicht auf das f eines anderen Objekts zugreifen
    • Beispiel: fn nope(o) o.f
    • println(Foo(42).nope(Foo(666)))
    • o.f innerhalb von nope kann nicht auf f von o zugreifen
  • Der Grund ist, dass Felder so funktionieren, dass sie in der Scope-Kette von Klassenmitgliedern erscheinen
    • o.f ist kein Feldzugriff, sondern eine Anfrage zum Aufruf einer Methode namens f
  • Deshalb kommt das folgende Muster häufig vor
    • my f
    • fn f f
    • also eine Methode namens f, die die lokale Variable f zurückgibt
  • Mit kürzerer Syntax als readable f
    • eine Kurzform von my f und fn f f
  • Viele Methodenaufrufe sind in Wirklichkeit Getter-Aufrufe
  • Es ist Verschwendung, wenn jeder Getter durch Auswertung eines AST arbeitet
  • Die Optimierung ist eine Getter-Spezialisierung
    • Im Zentrum steht UserFunction
    • Mit der neuen Methode Node::inferGetter wird abgeleitet, ob ein Funktionsrumpf ein einfacher Getter ist
  • Regeln der Ableitung
    • Block::inferGetter wird als Getter abgeleitet, wenn alles, was es enthält, als Getter ableitbar ist
    • Get::inferGetter leitet sich selbst als Getter ab und gibt den zu ladenden offset zurück
    • Context::tryGetFieldOffsets gibt nur dann ein nicht leeres Offsets zurück, wenn das Feld im lexikalischen Scope, in dem der Getter ausgeführt wird, sicher existiert
    • UserFunction wird, wenn sich der Funktionsrumpf als Getter ableiten lässt, in eine spezielle Function-Unterklasse aufgelöst, die nur noch direkt vom bekannten Offset liest
  • Der Performance-Effekt beträgt 5,6 % Verbesserung
    • Zu diesem Zeitpunkt ist die Performance 3,7x langsamer als CPython 3.10
    • 8,3x langsamer als Lua 5.4.7
    • 2,4x langsamer als QuickJS-ng 0.14.0
    • 9,55x schneller als der Ausgangspunkt

• Optimierung Nr. 9: Setter-Spezialisierung

  • Für die Setter-Ableitung ist Pattern-Matching des Musters fn set_fieldName(newValue) fieldName = newValue nötig
  • In der Ableitungsphase von UserFunction muss der Parametername des Setters übergeben werden
  • In der Ableitungsphase von Set muss geprüft werden, dass kein Schreibzugriff auf ein ClassObject vorliegt; außerdem muss geprüft werden, ob der Setter-Parameter als Quelle des Setzens verwendet wird
  • Der Performance-Effekt beträgt 3,4 % Verbesserung
    • Zu diesem Zeitpunkt ist Zef 3,6x langsamer als CPython 3.10
    • 8x langsamer als Lua 5.4.7
    • 2,3x langsamer als QuickJS-ng 0.14.0
    • 9,87x schneller als der Ausgangspunkt

• Optimierung Nr. 10: Inlining von callMethod

  • Eine wichtige Funktion wurde mit einer einzeiligen Änderung inline gemacht
  • Der Performance-Effekt beträgt 3,2 % Verbesserung
    • Zu diesem Zeitpunkt ist Zef 3,5x langsamer als CPython 3.10
    • 7,8x langsamer als Lua 5.4.7
    • 2,2x langsamer als QuickJS-ng 0.14.0
    • 10,2x schneller als der Ausgangspunkt

• Optimierung Nr. 11: Hashtabelle

  • Wenn ein inline-cache miss bei einem Methodenaufruf auftrat, musste bis zu ClassObject::tryCallMethod und ClassObject::TryCallMethodDirect hinabgestiegen werden; beide Pfade waren groß und komplex
  • Die bisherigen Suchkosten betrugen O(Hierarchietiefe)
    • Für jede Klasse der Hierarchie wurde per Hashtabellen-Lookup geprüft, ob der Aufruf als Member-Funktion aufgelöst wird
    • Für jede Klasse der Hierarchie wurde außerdem per Hashtabellen-Lookup geprüft, ob der Aufruf als verschachtelte Klasse aufgelöst wird
  • Die neue Änderung führt eine globale Hashtabelle ein, die receiver class und symbol als Schlüssel verwendet
    • Mit einem einzigen Lookup wird der callee direkt zurückgegeben
    • In classobject.h wird diese globale Tabelle abgefragt, bevor in das vollständige tryCallMethodSlow hinabgestiegen wird
    • In classobject.cpp wird ein erfolgreiches Lookup-Ergebnis in die globale Tabelle eingetragen
    • Die globale Hashtabelle selbst ist eine vergleichsweise einfache Implementierung
  • Der Performance-Effekt beträgt 15 % Verbesserung
    • Zu diesem Zeitpunkt ist Zef 3x langsamer als CPython 3.10
    • 6,8x langsamer als Lua 5.4.7
    • 1,9x langsamer als QuickJS-ng 0.14.0
    • 11,8x schneller als der Ausgangspunkt

• Optimierung Nr. 12: Vermeidung von std::optional

  • In Fil-C++ benötigt std::optional aufgrund unionsbezogener Compiler-Pathologien Heap-Allokationen
  • Normalerweise behandelt LLVM Typen bei Speicherzugriffen auf Unions locker, doch das kollidiert mit invisicaps
    • Es kommt vor, dass Pointer in einer Union auf aus Programmierersicht schwer vorhersagbare Weise ihre Capability verlieren
    • Das Ergebnis sind Panics durch Dereferenzierung von Objekten mit null capability in Fil-C, auch ohne Programmierfehler
  • Um dies abzumildern, fügt der Fil-C++-Compiler Intrinsics ein, damit LLVM bei lokalen Variablen vom Union-Typ konservativ vorgeht
  • Anschließend versucht der Pass FilPizlonator, per eigener escape analysis lokale Variablen vom Union-Typ dennoch für Register-Allokation geeignet zu machen
    • Diese Analyse ist allerdings nicht so vollständig wie die allgemeine SROA-Analyse von LLVM
  • Infolgedessen führt die Übergabe von Klassen mit enthaltenen Unions wie std::optional in Fil-C++ häufig zu Speicherallokationen
  • Diese Änderung umgeht Codepfade, die im hot path zu std::optional führen
  • Der Performance-Effekt beträgt 1,7 % Verbesserung
    • Zu diesem Zeitpunkt ist Zef 3x langsamer als CPython 3.10
    • 6,65x langsamer als Lua 5.4.7
    • 1,9x langsamer als QuickJS-ng 0.14.0

• 12-mal schneller als der Ausgangspunkt

• Optimierung #13: spezialisierte Argumente

  • Alle built-in-Funktionen von Zef nehmen 1 oder 2 Argumente entgegen; in nativen Implementierungen ist daher keine Zuweisung eines Arguments-Objekts nötig, um diese zu übergeben
  • Auch Setter nehmen immer ein Argument entgegen; wenn Setter-Inferenz erfolgt ist, reicht auch die spezialisierte Setter-Implementierung aus, den Wert direkt ohne Arguments-Objekt entgegenzunehmen
  • Mit dieser Änderung wurden die spezialisierten Argumenttypen ZeroArguments, OneArgument und TwoArguments eingeführt
    • Wenn der Callee sie nicht benötigt, kann der Caller die Zuweisung eines Arguments-Objekts vermeiden
  • ZeroArguments ist nötig, um es von (Arguments*)nullptr zu unterscheiden
    • Bisher wurde (Arguments*)nullptr verwendet, um einen Getter-Aufruf zu bedeuten, und diese Logik bleibt erhalten
    • Jetzt bedeutet ZeroArguments einen Funktionsaufruf ohne Argumente
  • Ein großer Teil der Änderungen bestand darin, Funktionen mit Argumenten zu templatisieren
    • Für ZeroArguments, OneArgument, TwoArguments und Arguments* wurde jeweils eine explizite Instanziierung durchgeführt
    • Ein erheblicher Teil des bestehenden Codes nutzte Value::getArg als Helfer zum Extrahieren von Argumenten; hierfür wurden Overloads für spezialisierte Argumente ergänzt
    • Die Änderungen am nativen Code, der Argumente verwendet, waren vergleichsweise geradlinig
  • Der Performance-Effekt beträgt 3,8 % Verbesserung
    • Zu diesem Zeitpunkt ist Zef 2,9-mal langsamer als CPython 3.10
    • 6,4-mal langsamer als Lua 5.4.7
    • 1,8-mal langsamer als QuickJS-ng 0.14.0
    • 12,4-mal schneller als der Ausgangspunkt

Umgehung von Fil-C-Pathologien und Detail-Spezialisierung

• Optimierung #14: Verbesserter Value-Slow-Path

  • Eine weitere Umgehung eines Fil-C-Pathologieeffekts brachte einen großen Geschwindigkeitsschub
  • Vor der Änderung war der Out-of-Line-Slow-Path von Value eine Member-Funktion von Value und benötigte ein implizites Argument vom Typ const Value*
  • In dieser Struktur musste der Caller Value auf dem Stack allokieren
  • In Fil-C++ werden jedoch alle Stack-Allokationen zu Heap-Allokationen
    • Daher allokierte der Code, der den Slow-Path aufruft, Value auf dem Heap
  • Danach wurden diese Methoden zu static gemacht und Value wurde per Wert übergeben
    • Dadurch war keine separate Allokation mehr nötig
  • Leistungseffekt: 10 % schneller
    • Zu diesem Zeitpunkt war Zef 2,6-mal langsamer als CPython 3.10
    • 5,8-mal langsamer als Lua 5.4.7
    • 1,65-mal langsamer als QuickJS-ng 0.14.0
    • 13,6-mal schneller als der Ausgangspunkt

• Optimierung #15: Deduplizierung von DotSetRMW

  • Es wurde ein Teil des duplizierten Codes entfernt
  • Erwartet wurde, dass weniger Maschinencode in Template-Funktionen hilfreich sein könnte, die durch constructCache<> spezialisiert werden
  • Das tatsächliche Ergebnis war kein Einfluss auf die Performance

• Optimierung #16: sqrt-Spezialisierung

  • Der Inline-Cache leitet Aufrufe zwar gut an die gewünschte Funktion weiter, funktioniert aber nur für Objekte
  • Bei Nicht-Objekten verlassen sich die Fast-Paths von Binary<>, Unary<> und Value::callRMW<> darauf zu prüfen, ob der Receiver int oder double ist
  • Diese Methode gilt nur für Operatoren, die der Parser erkennt
    • Auf Formen wie value.sqrt trifft das nicht zu
  • Mit dieser Änderung kann Dot nun für value.sqrt spezialisiert werden
  • Leistungseffekt: 1,6 % schneller
    • Zu diesem Zeitpunkt war Zef 2,6-mal langsamer als CPython 3.10
    • 5,75-mal langsamer als Lua 5.4.7
    • 1,6-mal langsamer als QuickJS-ng 0.14.0
    • 13,8-mal schneller als der Ausgangspunkt

• Optimierung #17: toString-Spezialisierung

  • Auf nahezu dieselbe Weise wie bei der vorherigen Optimierung wurde eine toString-Spezialisierung umgesetzt
  • Diese Änderung enthält auch Logik zur Reduzierung der Anzahl von Allokationen, wenn int in einen String umgewandelt wird
  • Leistungseffekt: 2,7 % schneller
    • Zu diesem Zeitpunkt war Zef 2,5-mal langsamer als CPython 3.10
    • 5,6-mal langsamer als Lua 5.4.7
    • 1,6-mal langsamer als QuickJS-ng 0.14.0
    • 14,2-mal schneller als der Ausgangspunkt

• Optimierung #18: Spezialisierung von Array-Literalen

  • Code wie my whatever = [1, 2, 3] erfordert in Zef die Allokation eines neuen Arrays, weil Arrays aliasfähig und veränderbar sind
  • Vor der Änderung wurde bei jeder Ausführung im AST nach unten traversiert und 1, 2, 3 wurden jedes Mal rekursiv ausgewertet
  • Mit dieser Änderung wird der Knoten ArrayLiteral für Fälle der Allokation konstanter Arrays spezialisiert
  • Leistungseffekt: 8,1 % schneller
    • Zu diesem Zeitpunkt war Zef 2,3-mal langsamer als CPython 3.10
    • 5,2-mal langsamer als Lua 5.4.7
    • 1,5-mal langsamer als QuickJS-ng 0.14.0
    • 15,35-mal schneller als der Ausgangspunkt

• Optimierung #19: Verbesserung von Value::callOperator

  • Dieselbe Optimierung, die zuvor zu einem Geschwindigkeitsschub geführt hatte, weil Value nicht per Referenz übergeben wurde, wurde auch auf den Slow-Path von callOperator angewendet
  • Leistungseffekt: 6,5 % schneller
    • Zu diesem Zeitpunkt war Zef 2,2-mal langsamer als CPython 3.10
    • 4,9-mal langsamer als Lua 5.4.7
    • 1,4-mal langsamer als QuickJS-ng 0.14.0
    • 16,3-mal schneller als der Ausgangspunkt

• Optimierung #20: Bessere C++-Optionen

  • In Fil-C++ wurden unnötiges RTTI und libc++-Hardening deaktiviert
  • Am C++-Code selbst gab es keine Änderungen, nur Anpassungen an den Build-System-Einstellungen
  • Leistungseffekt: 1,8 % schneller
    • Zu diesem Zeitpunkt war Zef 2,1-mal langsamer als CPython 3.10
    • 4,8-mal langsamer als Lua 5.4.7
    • 1,35-mal langsamer als QuickJS-ng 0.14.0
    • 16,6-mal schneller als der Ausgangspunkt

• Optimierung #21: Deaktivierung von Assertions

  • Als letzte Optimierung wurden Assertions standardmäßig deaktiviert
  • Der bestehende Code verwendete das Fil-C-spezifische Makro ZASSERT
    • eine Struktur, die Assertions immer ausführt
  • Nach der Änderung wird das interne Makro ASSERT verwendet
    • Assertions werden nur ausgeführt, wenn ASSERTS_ENABLED gesetzt ist
  • Diese Änderung enthält auch andere Anpassungen, damit der Code mit Yolo-C++ gebaut werden kann
  • Entgegen den Erwartungen gab es keinen Geschwindigkeitsgewinn

Ergebnisse und Grenzen von Yolo-C++

• Beim Kompilieren des Codes mit Yolo-C++ wurde ein 4-facher Geschwindigkeitsschub erzielt
• Allerdings ist dieser Ansatz nicht sound und suboptimal
  • Nicht sound ist er, weil die bestehenden Fil-C++-GC-Aufrufe durch calloc-Aufrufe ersetzt werden
  • Dadurch wird Speicher nicht freigegeben, und bei lange genug laufenden Workloads erreicht der Interpreter schließlich eine Speichererschöpfung
  • In ScriptBench1 tritt das nicht auf, weil die Testdauer kurz ist
• Suboptimal ist der Ansatz, weil der tatsächliche GC-Allokator schneller ist als calloc von glibc 2.35
• Daher wird angemerkt, dass das Hinzufügen eines echten GC zum Yolo-C++-Port möglicherweise einen noch größeren Geschwindigkeitsschub als das 4-Fache bringen könnte
• Für dieses Experiment wurde GCC 11.4.0 verwendet
• Zu diesem Zeitpunkt war Zef

  • 1,9-mal schneller als CPython 3.10

  • 1,2-mal langsamer als Lua 5.4.7

  • 3-mal schneller als QuickJS-ng 0.14.0

    • 67-mal schneller als der Ausgangspunkt

Rohdaten der Benchmarks

• Die Zeiteinheit für die Benchmark-Ausführung ist Sekunden
• Die Tabelle enthält für jeden Interpreter nbody, splay, richards, deltablue, geomean

• Python 3.10

  • nbody 0.0364
  • splay 0.8326
  • richards 0.0822
  • deltablue 0.1135
  • geomean 0.1296

• Lua 5.4.7

  • nbody 0.0142
  • splay 0.4393
  • richards 0.0217
  • deltablue 0.0832
  • geomean 0.0577

• QuickJS-ng 0.14.0

  • nbody 0.0214
  • splay 0.7090
  • richards 0.7193
  • deltablue 0.1585
  • geomean 0.2036

• Zef Baseline

  • nbody 2.9573
  • splay 13.0286
  • richards 1.9251
  • deltablue 5.9997
  • geomean 4.5927

• Zef Änderung #1: Direkte Operatoren

  • nbody 2.1891
  • splay 12.0233
  • richards 1.6935
  • deltablue 5.2331
  • geomean 3.9076

• Zef Änderung #2: Direkte RMWs

  • nbody 2.0130
  • splay 11.9987
  • richards 1.6367
  • deltablue 5.0994
  • geomean 3.7677

• Zef Änderung #3: IntObject vermeiden

  • nbody 1.9922
  • splay 11.8824
  • richards 1.6220
  • deltablue 5.0646
  • geomean 3.7339

• Zef Änderung #4: Symbole

  • nbody 1.5782
  • splay 9.9577
  • richards 1.4116
  • deltablue 4.4593
  • geomean 3.1533

• Zef Änderung #5: Value Inline

  • nbody 1.4982
  • splay 9.7723
  • richards 1.3890
  • deltablue 4.3536
  • geomean 3.0671

• Zef Änderung #6: Objektmodell und Inline-Caches

  • nbody 0.3884
  • splay 3.3609
  • richards 0.2321
  • deltablue 0.6805
  • geomean 0.6736

• Zef Änderung #7: Argumente

  • nbody 0.3160
  • splay 2.6890
  • richards 0.1653
  • deltablue 0.4738
  • geomean 0.5077

• Zef Änderung #8: Getter

  • nbody 0.2988
  • splay 2.6919
  • richards 0.1564
  • deltablue 0.4260
  • geomean 0.4809

• Zef Änderung #9: Setter

  • nbody 0.2850
  • splay 2.6690
  • richards 0.1514
  • deltablue 0.4072
  • geomean 0.4651

• Zef Änderung #10: callMethod inline

  • nbody 0.2533
  • splay 2.6711
  • richards 0.1513
  • deltablue 0.4032
  • geomean 0.4506

• Zef Änderung #11: Hashtabelle

  • nbody 0.1796
  • splay 2.6528
  • richards 0.1379
  • deltablue 0.3551
  • geomean 0.3906

• Zef Änderung #12: std::optional vermeiden

  • nbody 0.1689
  • splay 2.6563
  • richards 0.1379
  • deltablue 0.3518
  • geomean 0.3839

• Zef Änderung #13: Spezialisierte Argumente

  • nbody 0.1610
  • splay 2.5823
  • richards 0.1350
  • deltablue 0.3372
  • geomean 0.3707

• Zef Änderung #14: Verbesserte langsame Pfade für Value

  • nbody 0.1348
  • splay 2.5062
  • richards 0.1241
  • deltablue 0.3076
  • geomean 0.3367

• Zef Änderung #15: Dedupliziertes DotSetRMW::evaluate

  • nbody 0.1342
  • splay 2.5047
  • richards 0.1256
  • deltablue 0.3079
  • geomean 0.3375

• Zef Änderung #16: Schnelles sqrt

  • nbody 0.1274
  • splay 2.5045
  • richards 0.1251
  • deltablue 0.3060
  • geomean 0.3322

• Zef Änderung #17: Schnelles toString

  • nbody 0.1282
  • splay 2.2664
  • richards 0.1275
  • deltablue 0.2964
  • geomean 0.3235

• Zef Änderung #18: Spezialisierung von Array-Literalen

  • nbody 0.1295
  • splay 1.6661
  • richards 0.1250
  • deltablue 0.2979
  • geomean 0.2992

• Zef Änderung #19: callOperator-Optimierung für Value

  • nbody 0.1208
  • splay 1.6698
  • richards 0.1143
  • deltablue 0.2713
  • geomean 0.2810

• Zef Änderung #20: Bessere C++-Konfiguration

  • nbody 0.1186
  • splay 1.6521
  • richards 0.1127
  • deltablue 0.2635
  • geomean 0.2760

• Zef Änderung #21: Keine Asserts

  • nbody 0.1194
  • splay 1.6504
  • richards 0.1127
  • deltablue 0.2619
  • geomean 0.2759

• Zef in Yolo-C++

  • nbody 0.0233
  • splay 0.3992
  • richards 0.0309
  • deltablue 0.0784
  • geomean 0.0686

[GN⁺]

Hacker-News-Kommentare

• In einem ähnlichen Zusammenhang fand ich diese Seite zur Performance des Wren-Interpreters ziemlich interessant.
  Wenn sich der Zef-Artikel auf Implementierungstechniken konzentriert, zeigt Wren aus meiner Sicht eher, wie schon das Sprachdesign selbst zur Performance beiträgt.
  Besonders interessant fand ich, dass Wren auf dynamic object shapes verzichtet, wodurch copy-down inheritance möglich wird und die Methodensuche viel einfacher ausfällt.
  Für mich wirkt das wie ein ziemlich guter Trade-off. Wie oft muss man in der Praxis einer Klasse wirklich noch Methoden hinzufügen, nachdem sie erstellt wurde?

  • Ich denke, die Geschwindigkeit eines Interpreters oder JITs wird enorm stark vom Sprachdesign bestimmt.
    Es gibt viele stark optimierte VMs für dynamische Sprachen, aber LuaJIT ist aus meiner Sicht vor allem deshalb so stark, weil Lua eine sehr kleine Sprache ist, die sich gut optimieren lässt.
    Es gibt zwar auch dort ein paar Features, die schwer zu optimieren sind, aber davon gibt es nur wenige, sodass sich der Aufwand lohnt.
    Python ist dagegen aus meiner Sicht ein ganz anderer Fall. Leicht überspitzt gesagt wirkt es fast so, als sei die Sprache darauf ausgelegt, die Möglichkeit eines schnellen JITs zu minimieren, und die vielen Schichten an Dynamik machen Optimierungen wirklich schwierig.
    Dass der CPython-3.15-JIT selbst nach so langer Arbeit auf x86_64 nur etwa 5 % schneller als der Standardinterpreter ist, zeigt das meiner Meinung nach ziemlich deutlich.
  • Dieser Ansatz erinnert an Dinge, die in Sprachen mit idiomatisch akzeptiertem monkey patching, besonders in Ruby, ständig gemacht werden.
    Gleichzeitig fällt einem dabei natürlich auch ein, dass Ruby nicht gerade als Sprache mit kompromisslosem Fokus auf Geschwindigkeit bekannt ist.
    Umgekehrt wirkt die Vorstellung, dass ein Typ eine geschlossene Menge an anwendbaren Funktionen besitzt, auf mich auch etwas fragwürdig.
    Es gibt etliche Sprachen, in denen man beliebige Funktionen definieren und sie bei passendem Typ des ersten Arguments mit Punktnotation quasi wie Methoden verwenden kann.
    Beispiele wären Makros in Nim, implicit classes und type classes in Scala, extension functions in Kotlin oder traits in Rust.
  • Meiner Erfahrung nach lässt sich ein Ausdruck meist ziemlich effizient kompilieren, wenn man ihm einen statischen Typ zuordnen kann.
    Komplexe dynamische Sprachen zerstören diese Möglichkeit auf verschiedene Weise sehr aktiv, was Optimierungen entsprechend erschwert.
    Rückblickend wirkt das eigentlich ziemlich selbstverständlich.

• Beim Übergang von Änderung #5 zu #6 fand ich es bemerkenswert, dass inline caches und das hidden-class-Objektmodell den Großteil des Performancegewinns ausmachen — historisch wirkt das sehr ähnlich zu dem, wie V8 oder JSC schnell geworden sind.
  Der Punkt, an dem ein naiver Interpreter letztlich scheitert, ist eben der dynamische Dispatch bei Property-Zugriffen; der Rest wirkt im Vergleich fast wie ein rounding error.
  Ich fand auch gut, dass aufgeschlüsselt wurde, wie viel jede einzelne Stufe beigetragen hat. Bei Performance-Artikeln bekommt man oft nur die Endzahlen hingeworfen.

  • Ein besonders interessantes Implementierungsdetail in #6 war für mich, wie inline caching in einem Interpreter umgesetzt wird, der den AST direkt traversiert.
    Bei Bytecode-Interpretern ist die Stelle für IC-Rewrites naheliegend, weil man einfach stabile Offsets im Bytecode-Stream patchen kann.
    Hier liegt die Cache-Position aber im AST-Knoten selbst, und ich fand es beeindruckend, dass @pizlonator über constructCache<> spezialisierte AST-Knoten direkt an Ort und Stelle über generische Knoten legt.
    Im Ergebnis wirkt das wie Self-Modifying Code auf AST-Ebene.
    Dafür verlangt der Ansatz allerdings mutable AST nodes und kollidiert damit mit der bei vielen Compilern erwarteten Annahme unveränderlicher ASTs, etwa für Subtree-Sharing oder parallele Kompilierung.
    Für einen Single-Threaded-Interpreter ist das elegant, aber problematisch wäre es wohl, wenn der Interpreter Knoten verändert, während derselbe AST im Hintergrund von einem anderen Thread JIT-kompiliert wird.
  • Grundsätzlich stimme ich der Richtung zu, aber als kleine Einschränkung sollte man im Kopf behalten, dass es sich letztlich um Ergebnisse für genau einen bestimmten Benchmark handelt.
    Ich bin mir nicht sicher, ob das den Großteil echter Produktions-Workloads gut repräsentiert.
    Auf den Gedanken brachte mich die Stelle, an der die sqrt-Optimierung 1,6 % Verbesserung brachte.
    Damit das überhaupt möglich ist, muss der Benchmark ja von vornherein mindestens 1,6 % seiner Laufzeit dort verbringen, was ich ziemlich überraschend fand.
    Ein Blick ins Git-Repo legt nahe, dass das im nbody-Simulationsbenchmark tatsächlich so war.

• Ich fand das auch deshalb besonders spannend, weil ich gerade erst die erste Version meines eigenen AST-walking interpreter veröffentlicht habe.
  Mein Ziel war es, auf einem grundlegenden Niveau zu verstehen, was man braucht, um eine interpretierte Sprache zu bauen.
  Optimierungskomplexität wollte ich bewusst außen vor lassen und mich einfach darauf konzentrieren, meinen Rust-Code selbst gut zu verstehen.
  Trotzdem war ich überrascht, dass allein die Wahl meiner Lieblingssprache Rust schon zu ziemlich guter Performance geführt hat.
  Dazu kam als Bonus, dass Rust dank Ownership und Lifetimes keinen separaten garbage collector braucht.
  Natürlich verlasse ich mich im Moment an Stellen wie Closures noch recht konservativ auf Clones, um der Lifetime-Hölle zu entgehen, aber selbst so sind Geschwindigkeits- und Speicherprofil aus meiner Sicht mehr als ordentlich.
  Wer an einem einfachen, gut verständlichen tree-walking interpreter auf Rust-Basis interessiert ist, kann sich meinen Interpreter gluonscript ansehen.

• Ein wirklich großartiger Artikel.
  Besonders der Arguments-Bogen, also der Weg von #7 zu #13, traf sich stark mit meinen eigenen Erfahrungen.
  Als ich einmal in Rust einen async Step-Evaluator gebaut habe, war ich fest davon überzeugt, dass Borrowing mir Vorteile bringen würde, und habe mich tief in Cow<'_, Input> vergraben.
  In Microbenchmarks sah das gut aus, aber in realen Workloads breiteten sich der Discriminant von Cow und die lifetimebezogene Komplexität nach dem ersten await in alle Combinators aus, das Inlining brach stark ein, und damit verschwand letztlich auch der Grund, überhaupt Cow zu verwenden.
  Am Ende bin ich an der Evaluator-Grenze auf NoInput / OneInput / MultiInput(Vec) umgestiegen, und obwohl das grober aussieht, landete ich damit praktisch an derselben Stelle wie hier mit der Aufteilung in ZeroArguments / OneArgument / TwoArguments.
  Was mich noch interessieren würde: Wurde im nativen Pfad über die Arity-Spezialisierung hinaus auch Type Specialization ausprobiert?
  Bei einem binären Stil könnte man damit zum Beispiel vielleicht schon den isInt-Check komplett eliminieren.
  Meine Vermutung wäre, dass entweder die Codegrößenrechnung nicht aufging oder dass die ICs auf der Objektseite die heißen Pfade bereits weitgehend abgedeckt haben, sodass der native Fast Path nicht mehr viel ausmachte.
  Mich würde interessieren, was davon zutrifft.

• Das ist wirklich interessante und gelungene Arbeit.
  Ich habe etwas Ähnliches gemacht, allerdings eher auf der funktionalen Seite mit Scheme.
  Hier brachten Objektoptimierungen den größten Gewinn, bei mir waren dagegen closures der entscheidende Hebel.
  Lustigerweise waren die Optimierungsmethoden selbst ziemlich ähnlich.
  Wie man Scheme ausreichend schnell bekommt, steht meiner Meinung nach fast vollständig in Three implementation models for scheme.
  Der Unterschied ist nur, dass dort ein gewisser Kompilierungsschritt vorausgesetzt wird und nicht das ursprüngliche AST direkt interpretiert wird.

• Sehr interessant, danke fürs Teilen.
  Das hat bei mir den Wunsch geweckt, mich irgendwann selbst einmal genauer in dieses Thema einzuarbeiten.
  Und dass das Repo laut GitHub aus 99,7 % HTML und 0,3 % C++ besteht, fand ich auch ziemlich witzig und einprägsam.
  Das schien ein guter Hinweis darauf zu sein, wie klein der Interpreter wirklich ist.

  • Das liegt daran, dass die statisch generierte Website mit eingecheckt wurde.
    Durch die Art, wie der Code für den Browser erzeugt wird, ist die Website-Seite unnötig groß geworden.
    Trotzdem ist der Interpreter selbst wirklich sehr klein.

• Ich habe mich gefragt, ob man bei dieser Arbeit Dinge gelernt hat, mit denen sich fil c selbst noch verbessern ließe.

  • Definitiv habe ich dabei gelernt, dass wir eine bessere Lösung für den Umgang mit unions brauchen.
    Und ich habe auch gelernt, dass die Kosten, Methoden auf Value Objects als Outline-Call zu behandeln, ziemlich hoch sind.

• Ich habe gesehen, dass Lua enthalten ist, aber ich hätte mir gewünscht, dass auch LuaJIT dabei gewesen wäre.

  • Meine Erwartung wäre, dass LuaJIT Zef komplett schlagen würde.
    Eigentlich sollte das angesichts des Engineering-Aufwands dahinter sogar so sein.
    Es gab viele weitere Laufzeitumgebungen, die man hätte aufnehmen können, aber ich habe nicht alle einbezogen.
    Und dass PUC Lua deutlich schneller als QuickJS oder Python ist, fand ich ebenfalls ziemlich beeindruckend.

• Mich würde interessieren, wie die praktische Erfahrung mit Fil-C ist und ob es in der Praxis eine reale Nützlichkeit hat.

  • Vorweg: Ich bin Fil selbst, also bin ich in dieser Frage selbstverständlich voreingenommen.
    Trotzdem war es für dieses Projekt ziemlich praktisch nützlich.
    Es hat mehrere Probleme der Speichersicherheit deterministisch gefunden, wodurch das Design des Objektmodells sehr viel einfacher wurde, als es sonst gewesen wäre.
    Außerdem fühlte sich C++ mit präzisem GC für mich wie ein wirklich gutes Programmiermodell an.
    Verglichen mit normalem C++ hatte ich den Eindruck, etwa 1,5-mal produktiver zu sein, und selbst gegenüber anderen GC-Sprachen fühlte es sich noch nach ungefähr 1,2-mal schnellerer Entwicklung an.
    Ich denke, das liegt daran, dass das API-Ökosystem von C++ reichhaltig ist und Lambdas, Templates und das Klassensystem sehr ausgereift sind.
    Natürlich ist mir bewusst, dass ich in vieler Hinsicht voreingenommen bin.
    Ich habe Fil-C++ selbst gebaut und benutze C++ nun seit ungefähr 35 Jahren.

• Ich habe mich gefragt, was mit dem im Artikel erwähnten YOLO-C/C++-Compiler gemeint ist.
  Bei der Suche findet man kaum etwas, und auch ChatGPT schien nichts dazu zu wissen.

  • Der Autor von Fil-C und dieser Sprache benutzt den Ausdruck Yolo-C/C++, um normales C/C++ ohne Fil-C zu bezeichnen.