Rust verwendet die Nischenwertoptimierung (auch als Nischenfüllung bezeichnet), um die Speicherung des Unterscheidungswertes für Enums zu eliminieren, wenn ein Variantentyp ungültige Bitmuster enthält. Für Option<&T> wird die None-Variante durch den Nullzeigerwert dargestellt – ein Bitmuster, das für &T ungültig ist, da Referenzen immer nicht-null sein müssen. Dies ermöglicht es dem Compiler, den Unterscheidungswert implizit im Zeiger selbst zu speichern, sodass Option<&T> genau ein Maschinenwort einnimmt. Diese Optimierung gilt für jeden Typ, der Nischenwerte aufweist – ungültige Bitmuster wie 0 für NonZeroU32, Werte außerhalb von 0 oder 1 für bool, oder spezifische Sentinel-Werte in #[repr(C)]-Structs.
Bei der Entwicklung eines leistungsstarken abstrakten Syntaxbaums (AST) für einen Compiler, der Millionen von Knoten verarbeitet, hatten wir erheblichen Speicherbedarf durch Eltern- und Kindzeiger. Jeder Knoten benötigte optionale Verweise auf seinen Elternknoten, linken Kindknoten und rechten Kindknoten, die zunächst als Option<Box<Node>> implementiert waren.
Die Verwendung von Option<Box<Node>> erforderte 16 Bytes pro Zeiger auf 64-Bit-Systemen – 8 Bytes für den Box-Zeiger und 8 Bytes für den Unterscheidungswert und das Padding. Bei einem Baum mit 10 Millionen Knoten summierte sich dies auf 480 Megabyte allein für Verknüpfungszeiger, was unser Speicherbudget überschritt.
Wir betrachteten drei Ansätze. Zuerst waren wir versucht, Option<Box<Node>> durch rohe Zeiger (*mut Node) zu ersetzen und null für None zu verwenden. Dies beseitigte den Overhead, erforderte jedoch unsafe-Blöcke im gesamten Code, was riskante Dangling-Zeiger und Verletzungen von Rust's Sicherheitsgarantien mit sich brachte. Zweitens, die Verwendung eines Arena-Allocators mit Indizes (usize) anstelle von Zeigern. Obwohl dies speicherfreundlich war, benötigte Option<usize> aufgrund fehlender Nischen in usize immer noch 16 Bytes, und die Indizesarithmetik komplizierte die API.
Wir wählten den dritten Ansatz: Option<NonNull<Node>> umschlossen in einer sicheren ParentPtr-Abstraktion. NonNull<T> hat eine Nische an Adresse 0, was es Option<NonNull<Node>> ermöglicht, bei 8 Bytes zu bleiben. Wir kapselten die unsafe-Dereferenzierung innerhalb der Wrapper-Methoden, um die Speichersicherheit zu bewahren und gleichzeitig eine Nullkostenabstraktion zu erreichen. Dies reduzierte die Größe des AST-Speichers um 50% und passte innerhalb unseres 256MB-Limits, ohne die Sicherheit zu opfern.
Warum bleibt Option<Option<bool>> ein Byte groß, während Option<Option<usize>> auf 16 Bytes anwächst?
bool hat 254 Nischenwerte, da nur die Bitmuster 0 und 1 gültig sind. Die erste Option-Ebene verbraucht eine Nische (z. B. 2), um None darzustellen, wobei 253 Nischen übrig bleiben. Die zweite Option-Ebene verbraucht eine weitere Nische (z. B. 3) für ihre None-Variante. Folglich passt Option<Option<bool>> weiterhin in ein Byte. Im Gegensatz dazu hat usize keine ungültigen Bitmuster – alle 2^64 Werte sind gültige Speicheradressen oder Daten. Ohne Nischen muss Option<usize> ein Unterscheidungsbyte anhängen, was zu 16 Bytes führt (8 für Daten, 8 für die Ausrichtung). Geschachtelte Option-Ebenen können nicht weiter optimiert werden, solange keine verfügbaren Nischen vorhanden sind, sodass Option<Option<usize>> bei 16 Bytes mit interner Unterscheidungslogik bleibt.
Warum lehnt der Compiler die Nischenoptimierung für Enums ab, die mit #[repr(C)] markiert sind, selbst wenn der Nutzlasttyp Nischen enthält?
Das #[repr(C)]-Attribut gewährleistet ein C-kompatibles Speicherlayout mit stabiler Feldordnung und expliziter Unterscheidungsspeicherung an einem vorhersehbaren Offset. Der C-Standard unterstützt keine überlappenden Unterscheidungswerte mit Nutzlastdaten – Unterscheidungswerte müssen an bestimmten Speicherorten gespeichert werden, um FFI-Kompatibilität zu gewährleisten. Während eine Struktur wie NonNull<T> Nischen enthält (Nullzeiger), können #[repr(C)]-Enums diese nicht nutzen, um sich mit dem Unterscheidungswert zu überlappen, da externes C-Code erwartet, einen bestimmten Unterscheidungswert an einem festen Offset zu lesen. Diese Einschränkung bewahrt die Interoperabilität auf Kosten der Speichereffizienz, sodass sizeof(Option<&T>) gleich sizeof(&T) + sizeof(discriminant) unter #[repr(C)] bleibt, typischerweise 16 Bytes statt 8.
Wie funktioniert std::mem::discriminant für Typen wie Option<&T>, die keine explizite Unterscheidungsspeicherung im Speicher haben?
std::mem::discriminant gibt einen undurchsichtigen Discriminant<T>-Wert zurück, der die Enum-Variante eindeutig identifiziert, unabhängig von der zugrunde liegenden Speicherrepräsentation. Für Option<&T> generiert der Compiler Code, der den Unterscheidungswert ableitet, indem er den Zeigerwert überprüft – es wird eine Konstante zurückgegeben, die Some darstellt, wenn der Zeiger nicht null ist, und eine Konstante, die None darstellt, wenn er null ist. Obwohl kein separater Speicherort einen Unterscheidungswert speichert, abstrahiert der Discriminant-Typ diese Berechnung, sodass der Vergleich von Varianten über == möglich ist, ohne die Nischenkodierungsdetails offenzulegen. Dies zeigt, dass discriminant auf der semantischen Variantenidentität und nicht auf dem physischen Speicherlayout basiert, was konsistentes Verhalten über optimierte und nicht optimierte Enum-Repräsentationen ermöglicht.