Maxime Chevalier-Boisvert beschreibt die Optimierung seines in Rust geschriebenen Sprachinterpreters und der virtuellen Maschine (Plush), bei der ein 16 Byte (128 Bit) breites tagged Enum durch ein maßgeschneidertes, 64 Bit breites Wort mit Low-Bit-Tagging ersetzt wurde. Diese Umstrukturierung reduzierte den Speicherverbrauch bei speicherintensiven Benchmarks und steigerte die Ausführungsgeschwindigkeit des Interpreters durch verbesserte Cache-Lokalität und deutlich effizienteren, von LLVM generierten Assemblercode um 17 %.
Wichtigste Punkte
Enum-Overhead: Das ursprüngliche Rust-Enum war aufgrund von Ausrichtungsbeschränkungen (Alignment) 16 Bytes breit, was in Arrays zu erheblichem Speicherverlust durch ungenutzte Bytes führte.
64-Bit-Tagging-Schema: Das neue Value-Newtype passt in ein einzelnes 64-Bit-Wort (u64) und kodiert Fixnums, Flonums, Immediates und zwei Zeigertypen durch Ausnutzung ungenutzter niederwertiger Bits.
Fixnum-Optimierung: 62-Bit-Ganzzahlen nutzen das Format n << 2 (untere Bits 00), wodurch arithmetische Operationen und Überlaufprüfungen als native Maschinenbefehle (adds, b.vs) direkt ausgeführt werden können.
Flonum-Selbst-Tagging: Übernahme des Self-Tagging-Verfahrens nach Melançon et al. (arXiv:2411.16544) mittels eines Bias-Wertes (0x6810_0000_0000_0000), wodurch die volle Mantissenpräzision bei Gleitkommazahlen ohne Heap-Allokation erhalten bleibt.
Leistungssteigerung: Benchmark-Ergebnisse zeigen eine durchschnittliche Leistungssteigerung von 17 %, angetrieben durch reduzierte Cache-Zugriffe bei zeigerintensiven Benchmarks (binary_tree, linked_list) sowie den Wegfall von Stack-Spills, die zuvor durch ineffizienten match-Dispatch-Code von Rusts Compiler verursacht wurden.
Diskussions-Highlights
Titeldiskussion: Kommentatoren merkten an, dass der Artikel-Titel irreführend ist, da der Leistungszuwachs nicht auf ein Versagen des Rust-Compilers zurückzuführen ist, sondern auf ein manuell entwickeltes, maßgeschneidertes Kodierungsschema, das ein Compiler unmöglich automatisch ableiten kann.
Sicherheit und Unsafe Rust: Es wurde diskutiert, dass solche Optimierungen in sicherem Rust nicht direkt umsetzbar sind und den Einsatz von unsafe-Blöcken sowie spezialisierten Union-Typen (unter Verwendung von Tools wie Miri zur Verifizierung der Zeiger-Provenienz) erfordern.
Abstraktion versus Leistung: Die Diskussion beleuchtete den klassischen Konflikt zwischen der Lesbarkeit und Wartbarkeit sauberer Enums versus der rohen Leistung manueller Bit-Manipulationen auf Hot-Paths.
Sprachvergleiche: Teilnehmer verwiesen auf andere Implementierungen in freier Wildbahn, wie etwa OCaml (das standardmäßig 63-Bit-Ganzzahlen verwendet) oder Ada (das seit Jahrzehnten statisch erzwungene Subbereiche unterstützt).
Glossar
Tagged Enum: Ein Datentyp in Programmiersprachen, der einen Wert darstellt, der eine von mehreren Varianten sein kann, ergänzt um ein Tag zur Typidentifizierung.
Low-Bit-Tagging: Eine Technik, bei der ungenutzte niederwertige Bits von zeiger- oder wertbasierten Adressen überschrieben werden, um Typmetadaten direkt im Datenwort zu speichern.
Fixnum: Eine Abkürzung für „Fixed-point number“ oder kleine Ganzzahlen, die direkt in einem Maschinenwort gespeichert werden, ohne Heap-Allokation zu erfordern.
Flonum: Eine Abkürzung für Gleitkommazahl (Floating-point number), die in diesem Kontext durch ein spezielles Selbst-Tagging-Schema repräsentiert wird.
NaN Boxing: Eine Technik zur Repräsentation verschiedener Datentypen innerhalb eines 64-Bit-Gleitkomma-Wortes durch Ausnutzung ungenutzter Bitmuster von „Not-a-Number“-Werten.
Heap-Boxing: Das Einpacken eines primitiven Wertes in ein Heap-alloziertes Objekt, wenn dieser Wert nicht in das native Speicherformat (wie ein 64-Bit-Wort) passt.
Cache-Lokalität: Ein Maß dafür, wie nah beieinander liegende Daten im Computerspeicher abgelegt sind, was die Effizienz von CPU-Caches direkt beeinflusst.
Stack-Spill: Ein Vorgang, bei dem Registerinhalte temporär auf den Stapelspeicher (Stack) ausgelagert werden müssen, weil nicht genügend freie Prozessorregister zur Verfügung stehen.
Miri: Ein experimenteller Interpreter für die Zwischendarstellung von Rust (MIR), der verwendet wird, um undefiniertes Verhalten und Verstöße gegen die Zeiger-Provenienz aufzudecken.