Der Artikel dokumentiert eine Optimierung des Interpreters der dynamisch typisierten Programmiersprache Plush, bei der die zentrale Werte-Repräsentation (Value) von einem 16-Byte (128-Bit) breiten Rust-enum auf ein manuell verpacktes 64-Bit-Wort (u64) umgestellt wurde. Durch die Implementierung eines Niedrigbit-Tagging-Schemas (Low-Bit Tagging) in Kombination mit Float-Self-Tagging konnte der maximale Speicherverbrauch (RSS) bei speicherintensiven Benchmarks um bis zu 37 % gesenkt und die Ausführungsgeschwindigkeit über alle Benchmarks hinweg um bis zu 17 % gesteigert werden. Die Leistungsgewinne resultieren vorrangig aus einer verbesserten CPU-Cache-Effizienz sowie einer optimalen Registerbelegung, welche speicherintensive Stack-Spills bei Maschinencode-Verzweigungen eliminiert.
Wichtigste Punkte
Speicher-Alignment-Problem: Das ursprüngliche Rust-Tagged-Enum verbrauchte aufgrund von Alignment-Vorgaben 16 Byte Speicher, da neben dem 64-Bit-Payload zusätzliche 8 Bit für den Tag benötigt wurden; dies führte zu hohem Speicherverschnitt in Arrays und Objektstrukturen.
64-Bit Low-Bit Tagging Scheme: Das neue System kodiert fünf Werttypen innerhalb eines 64-Bit-Wortes: 62-Bit Fixnums (vorzeichenbehaftete Ganzzahlen), Flonums (Gleitkommazahlen), Immediates (mit 5-Bit-Subtag für nil, true, false, undef und Host-Funktionen) sowie zwei Zeigertypen.
Effiziente Fixnum-Arithmetik: Ganzzahlen nutzen die untersten Bitmuster 00 (gespeichert als n << 2), wodurch Addition, Subtraktion und Bit-Operationen direkt ohne Entpacken (Untagging) ausgeführt werden können; Überläufe lassen sich direkt über native CPU-Flags (jo auf x86-64, bvs auf ARM64) abfangen.
Float Self-Tagging: Unter Einsatz des Verfahrens von Melançon et al. (arXiv:2411.16544) werden Floats mittels Bit-Rotation und eines BIAS-Wertes auf das Tag-Muster 10 abgebildet, wodurch die volle Mantissen-Präzision erhalten bleibt und nur zwei Exponenten-Bits opfert werden. Seltene Überlauf-Floats fallen auf ein Heap-Boxing zurück.
Speicher- und Performanzgewinne: Auf einem Apple M5 MacBook Air zeigte sich bei speicherintensiven Benchmarks (wie mlp oder binary_tree) eine RSS-Reduktion um bis zu 37 %. Die Ausführungsgeschwindigkeit stieg durchgehend an, selbst bei Fließkomma-intensiven Tests (nbody, mlp), obwohl hier Re-Boxing-Schritte anfallen.
Compiler-Codegenerierung (Codegen): Die Befehlsanalyse des add-Instruktionspfads zeigte, dass der neue 64-Bit-Wert vollständig in einem einzigen CPU-Register Platz findet. Dadurch sank der Aufwand des Fast-Paths von 52 Instruktionen, 24 Speicherzugriffen und 4 Verzweigungen auf 36 Instruktionen, 9 Speicherzugriffe und 1 Verzweigung.
Diskussions-Highlights
Architekturänderung statt Compiler-Unzulänglichkeit: Mehrere Kommentatoren betonen, dass der Leistungssprung nicht auf Fehler im Rust-Compiler zurückzuführen ist, sondern auf ein geändertes Architekturdesign (Domain-Encoding), welches seltene Spezialwerte auf den Heap auslagert, um den Hot-Path in ein 64-Bit-Register zu passen.
Lesbarkeit vs. Hot-Path-Performanz: Es wird diskutiert, dass Rust-Enums zwar aus Wartbarkeitssicht überlegen sind, in Hot-Paths von Interpretern jedoch bitweise Operationen und unleserlicherer Code aufgrund der massiven Geschwindigkeitsgewinne alternativlos sein können.
Grenzen des Typensystems: Diskussionen über Rusts Optimierungspotenzial zeigen, dass der Compiler ohne explizite Unsafe-Blöcke oder manuelle Bit-Operationen keine komplexen Tagging-Schemata (wie NaN-Boxing oder benutzerdefinierte Bit-Nischen) automatisch generieren kann, da dies semantische Garantien verletzen würde.
Verifizierung und Safe-Abstraktion: Vorgeschlagen wird die Isolierung von unsafe-Bitmanipulationen in separaten Modulen oder Crates (z. B. inspiriert durch triomphe::ArcUnion), um den Code mittels Miri und herkunftsersparenden Zeigeroperationen (provenance-preserving pointers) formal zu testen.
Branchenstandards: Verweise auf Sprachen wie OCaml (mit 63-Bit-Integern) verdeutlichen, dass das Ausborgen von Niedrig-Bits für VM-Typen-Tags eine etablierte Praxis im Compilerbau darstellt.
Glossar
Fixnum: Eine direkt in ein Tagged-Word gepackte Ganzzahl fester Breite (hier 62 Bit), die ohne Speicherallokation auf dem Heap auskommt.
Flonum: Eine innerhalb einer virtuellen Maschine gepackte oder getaggte Fließkommazahl (Floating-Point Number).
NaN Boxing: Ein Speicherverfahren für 64-Bit-Fließkommazahlen, das die ungenutzten Bitmuster von NaN-Werten (Not-a-Number) verwendet, um Zeiger oder andere Datentypen direkt im Float-Wort zu speichern.
Float Self-Tagging: Ein Verfahren zur Kodierung von Gleitkommazahlen mittels Bit-Rotation und Bias-Offset, um Tag-Bits in den niedrigsten Positionen zu platzieren, ohne die Mantisse zu beschneiden.
Tagged Enum: Eine Datenstruktur (Summentyp), die neben den eigentlichen Nutzdaten einen expliziten Indikator (Tag) enthält, um den aktiven Datentyp zur Laufzeit zu bestimmen.
RSS (Resident Set Size): Der Anteil des Hauptspeichers (RAM), der von einem Prozess aktuell im physischen Speicher gehalten wird.
Bump Allocator: Ein Hochleistungs-Speicherallokator, der neuen Speicherplatz durch einfaches Inkrementieren eines Zeigers reserviert, jedoch nur eine kollektive Freigabe erlaubt.
Stack-Spill: Das ungewollte Auslagern von Daten aus schnellen CPU-Registern in den Hauptspeicher (Stack), wenn die Anzahl der benötigten Variablen die Registerkapazität übersteigt.
Miri: Ein offizieller Interpreter für Rusts Zwischenrepräsentation (MIR), der zur Erkennung von undefiniertem Verhalten (Undefined Behavior) in unsafe-Code genutzt wird.