Visualisaties van Rust Vtables: Hoe dyn Trait werkt in het geheugen

Ik ben begonnen met Rust en het is tegelijkertijd bevredigend en verbijsterend. Tot nu toe heb ik geleerd uit het officiële boek en het boek van Mara Bos, maar ik kreeg de drang om zelf wat dissecties uit te voeren. Mijn aanvankelijke doel met deze experimenten was om de aanpak van polymorfisme in Rust te vergelijken met die van C++.

Uiteindelijk ben ik er echter achter gekomen dat het een valkuil is om een nieuwe taal te proberen te begrijpen via een andere door 1:1 parallellen te trekken. Het lijkt misschien te helpen, maar uiteindelijk kunnen we Rust niet behandelen als C++ met een andere syntaxis. Als dat wel zo was, zou er niets revolutionairs aan zijn.

Dat gezegd hebbende, geloof ik dat er waarde zit in het onderzoeken van het 'waarom'. Dus, als jij net als ik bent en precies wilt weten wat er in het geheugen gebeurt om het gevoel te hebben dat je de concepten echt begrijpt, hoop ik dat je dit artikel nuttig vindt.

(Ter info: de thumbnail afbeelding is een foto van de roestschimmel, waaraan Rust zijn naam ontleent. Credits: gailhampshire via Wikimedia Commons.)

Introductie: De kern van de zaak

Wat we proberen te bereiken is vrij eenvoudig. Stel dat we een verzameling vormen hebben: cirkels, vierkanten en driehoeken, en we willen voor elke vorm de methode draw() aanroepen.

C++ Aanpak #1: Virtuele functies

De eerste manier die in C++ in ons opkomt is via virtuele functies, wat gebruikmaakt van runtime polymorfisme. De vtable-pointer bevindt zich in het object; de virtuele dispatch gebeurt automatisch.

std::vector<Shape*> shapes = { new Circle(), new Square() };
for (auto* s : shapes)
    s->draw();

Het equivalent in Rust zou dyn Trait zijn, en dat is wat we uiteindelijk willen begrijpen. Maar laten we eerst kijken naar een andere manier waarop we dit in C++ zouden kunnen oplossen.

C++ Aanpak #2: CRTP

Men zou ook de weg van CRTP (Curiously Recurring Template Pattern) kunnen bewandelen, wat in essentie compile-time polymorfisme is.

template<typename Derived>
struct Shape {
    void draw() {
        static_cast<Derived*>(this)->draw();
    }
};

In essentie zijn er geen vtables en wordt dit op compile-time opgelost, waarbij de leesbaarheid wordt opgeofferd (het is een mondvol).

Rust biedt een veel directer en eenvoudiger equivalent voor CRTP, namelijk monomorfisatie. Dit is de aanpak die we eerst zullen uitdiepen om ons mentale model van Rust op te bouwen.

Statische Dispatch

Statische dispatch, ook bekend als generics, bereikt een vergelijkbaar resultaat als CRTP: de compiler genereert een aparte kopie van de functie voor elk type waarmee deze wordt aangeroepen. Er zijn nul runtime-kosten, maar de types moeten bekend zijn op compile-time.

trait Draw {
    fn draw(&self) -> &str;
}

struct Circle;
struct Square;

impl Draw for Circle {
    fn draw(&self) -> &str {
        "Drawing a circle"
    }
}

impl Draw for Square {
    fn draw(&self) -> &str {
        "Drawing a square"
    }
}

fn draw_shape<T: Draw>(shape: T) {
    println!("{}", shape.draw());
}

fn main() {
    let circle = Circle;
    let square = Square;
    draw_shape(circle);
    draw_shape(square);
}

Onder de motorkap genereert de compiler twee aparte functies: drawshape::<Circle> en drawshape::<Square>.

Hoe verhoudt dit zich tot de templates van C++?

Het verschil zit in de filosofie. C++ maakt de beperkingen impliciet; een template accepteert elk type T dat toevallig een .draw() methode heeft. In Rust schrijf je het contract expliciet uit: je "implementeert de Draw trait voor Square."

Wanneer is dit niet voldoende? Voordat we die vraag beantwoorden, maken we een kleine zijstap.

Zijstap: De Zero-Sized Types van Rust

Ik probeerde naar de grootte van Circle en Square te kijken omdat ik de vergelijking wilde maken met wide pointers, maar dit leidde me naar een onverwachte ontdekking. In C++ schrijft de standaard voor dat elk object een grootte van minimaal 1 byte heeft, zelfs als het leeg is. Dit is zodat twee verschillende objecten altijd verschillende adressen hebben, wat betekent dat &obj1 anders moet zijn dan &obj2.

Toen ik zag dat Rust 0 teruggeeft, was ik totaal verrast. Dit zijn de kleine momenten die mij veel plezier geven tijdens het verkennen van Rust, omdat het mijn mentale model deconstrueert.

println!("{}", std::mem::size_of::<Circle>()); // 0 WAT???
println!("{}", std::mem::size_of::<Square>()); // 0

Zo ontdekte ik dat Rust de garantie voor unieke adressen anders afhandelt. Zero-sized types (ZST) zijn structs die geen velden bevatten, waardoor er geen geheugen hoeft te worden gealloceerd. Rust volgt identiteit via ownership, niet via adressen. Elke waarde heeft op één moment precies één eigenaar; dit wordt op compile-time afgedwongen door de borrow-checker.

In C++ zouden we dit doen om te controleren of twee pointers naar hetzelfde object verwijzen: if (&a == &b) { // hetzelfde object }

In Rust wordt die vraag op compile-time beantwoord door de borrow-checker:

// de borrow checker weet al dat dit verschillende bindings zijn
// je hoeft adressen niet te vergelijken om ze uit elkaar te houden
let a = Circle;
let b = Circle;

De compiler houdt a en b bij als verschillende namen met verschillende eigenaren.

Ik vroeg me vervolgens af: wat gebeurt er als we het adres van een ZST pakken?

let a = Circle;
let b = Circle;
println!("{:p}", &a as *const Circle);
println!("{:p}", &b as *const Circle);

De output: 0x7ffdda99aece 0x7ffdda99aecf

Vreemd... ze krijgen verschillende stack-adressen met 1 byte verschil. Het lijkt alsof de compiler een byte voor elk heeft gealloceerd, precies zoals C++ zou doen, maar dit is simpelweg gedrag in de debug-modus. De compiler wijst lokale ZST-variabelen een dummy stack-slot toe, puur zodat debuggers ze via referentie kunnen volgen en inspecteren.

Als we dit in release-modus proberen, krijgen we ander gedrag: cargo run --release --bin 01staticdispatch

De adressen vallen hier inderdaad samen: 0x7ffdf74afa6f 0x7ffdf74afa6f

Mijn conclusie hiervan is dat de compiler geen garanties geeft over ZST-adressen, en dat identiteit wordt gevolgd door de borrow-checker via ownership, niet via geheugenadressen.

Dynamische Dispatch

Laten we terugkeren naar onze hoofdquest en kijken hoe dynamische dispatch eruit zou zien voor ons eerdere voorbeeld:

fn draw_shape(shape: &dyn Draw) {
    println!("{}", shape.draw());
}

fn main() {
    let circle = Circle;
    let square = Square;
    draw_shape(&circle);
    draw_shape(&square);
}

Het ziet er bijna identiek uit als de statische dispatch-versie; het enige verschil is &dyn Draw in plaats van <T: Draw>. Maar er gebeurt iets fundamenteel anders onder de motorkap. Laten we kijken naar de grootte:

println!("&Circle size:   {}", std::mem::size_of::<&Circle>());   // 8
println!("&dyn Draw size: {}", std::mem::size_of::<&dyn Draw>()); // 16

&dyn Draw is twee keer zo groot als een normale pointer. Dit wordt een wide pointer genoemd: het zijn eigenlijk twee pointers. De ene wijst naar de data, de andere naar een vtable. Die vtable vertelt Rust welke draw() methode er op runtime moet worden aangeroepen.

We kunnen inspecteren hoe die pointers eruitzien:

fn inspect(shape: &dyn Draw) {
    let (data_ptr, vtable_ptr) = unsafe {
        std::mem::transmute::<&dyn Draw, (usize, usize)>(shape)
    };
    println!("data ptr:      {:#x}", data_ptr);
    println!("vtable ptr:    {:#x}", vtable_ptr);
}

std::mem::transmute maakt een bit-voor-bit kopie van het brontype (&dyn Draw) naar het doeltype ((usize, usize)). Dit vereist unsafe omdat de compiler niet kan garanderen dat willekeurige bitpatronen geldige waarden vormen voor het doeltype.

We zien dat objecten van hetzelfde type een vtable delen en dat de data-pointer per instantie verschilt:

=== circle ===
data ptr:      0x7ffdcae73286
vtable ptr:    0x55f23cbe5338   <-- vtable van circle
=== circle2 ===
data ptr:      0x7ffdcae732ec
vtable ptr:    0x55f23cbe5338   <-- dezelfde vtable als circle!!
=== square ===
data ptr:      0x7ffdcae73287
vtable ptr:    0x55f23cbe5358

Waarom is dynamische dispatch nodig?

Wanneer is statische dispatch niet genoeg? Laten we een scenario bekijken. Als we een Vec<T> wilden maken die een mix van zowel Square als Circle bevat, lopen we met generics alleen vast.

// compileert niet!!
let shapes = vec![Circle, Square];

Een Vec<T> vereist dat elk element exact hetzelfde type en dezelfde grootte heeft. Circle en Square zijn volledig ongerelateerd en kunnen verschillende groottes hebben. Er is geen "basisklasse" zoals in C++, waar je zou schrijven: std::vector<Shape*> shapes = { new Circle(), new Square() };

Dit is waar we dynamische dispatch nodig hebben, oftewel dyn Trait. Box<T> is de manier van Rust om een waarde op de heap te alloceren en deze via een pointer te bezitten.

let shapes : Vec<Box<dyn Draw>> = vec![ // Box -> [ data ptr | vtable ptr ]
    Box::new(Circle),
    Box::new(Square),
];

Box<dyn Draw> lost het grootteprobleem op. Een Box is altijd dezelfde grootte, aangezien het slechts een wide pointer is.

Vec<Box<dyn Draw>> in het geheugen: [ 16 bytes | 16 bytes ] ↓ ↓ [data|vtable] [data|vtable] ↓ ↓ Circle Square

Een belangrijk verschil met de C++ filosofie is dat in C++ de keuze tussen dynamische en statische dispatch wordt gemaakt op klassen-niveau. Als je een methode als virtual markeert, zal die klasse altijd dynamische dispatch gebruiken. In het geval van vector<Shape*> werkt dit omdat de vtable-pointer deel uitmaakt van het object.

In Rust wordt de keuze gemaakt op de plek van de aanroep (call site). Circle is gewoon Circle; het weet niets van dispatch. Jij beslist of je statische of dynamische dispatch gebruikt, afhankelijk van hoe je er naar verwijst: &Circle voor statisch, &dyn Draw voor dynamisch.

Eén Vtable per (Type, Trait) Paar

Laten we zien wat er gebeurt als we verschillende traits combineren voor één type. We willen dat onze Duck zowel kan vliegen (Fly) als zwemmen (Swim).

trait Fly {
    fn fly(&self) -> &str;
}

trait Swim {
    fn swim(&self) -> &str;
}

struct Duck;

impl Fly for Duck {
    fn fly(&self) -> &str {
        "Duck flies!"
    }
}

impl Swim for Duck {
    fn swim(&self) -> &str {
        "Duck swims!"
    }
}

Hoe ziet dit eruit in het geheugen:

let fly_obj: &dyn Fly = &duck;
let swim_obj: &dyn Swim = &duck;

let (data_fly, vtable_fly) = unsafe {
    std::mem::transmute::<&dyn Fly, (usize, usize)>(fly_obj)
};
let (data_swim, vtable_swim) = unsafe {
    std::mem::transmute::<&dyn Swim, (usize, usize)>(swim_obj)
};

println!("fly_obj  -> data: {:#x}  vtable: {:#x}", data_fly,  vtable_fly);
println!("swim_obj -> data: {:#x}  vtable: {:#x}", data_swim, vtable_swim);
println!("size of duck: {}", std::mem::size_of_val(&duck));

Output: flyobj -> data: 0x7ffe769558df vtable: 0x5573a247ea48 swimobj -> data: 0x7ffe769558df vtable: 0x5573a247ea68 size of duck: 0

We kunnen opnieuw bewonderen hoe de grootte van Duck 0 is omdat het een ZST is. We zien ook dat flyobj en swimobj dezelfde data-pointer delen, wat logisch is omdat ze beide dynamische traits zijn van hetzelfde onderliggende duck-object. Het interessante deel hier is echter hoe de vtable-pointers verschillen.

Dit bevestigt ons kernidee: de vtable is niet ingebed in het object (zoals in C++), maar is externe statische data die aan het object wordt gekoppeld wanneer je vraagt om dynamische dispatch. Een Duck blijft een Duck, ongeacht of hij zwemt of vliegt, of hoeveel traits hij implementeert.

Objectveiligheid: Waarom niet elke Trait dyn kan zijn

Het is belangrijk om ook de beperkingen te begrijpen. Niet elke trait in Rust kan worden gebruikt als dyn Trait. Een trait moet voldoen aan zogenaamde object safety rules om als een trait-object te kunnen worden gebruikt:

1. Methoden mogen geen Self retourneren.
2. Methoden mogen geen generieke parameters hebben.

Methoden mogen geen Self retourneren

Clone is het klassieke voorbeeld, omdat het fn clone(&self) -> Self heeft. Self is in essentie een placeholder voor het type dat op dat moment de trait implementeert.

Voor Circle die de Clone trait implementeert, lost Self op naar Circle. Omdat het Self retourneert, moet de aanroeper het concrete type kennen om te weten hoeveel geheugen er moet worden gealloceerd voor de retourwaarde. Via een vtable kent de aanroeper het concrete type niet, dus wijst de compiler dit af.

C++ heeft dit probleem niet, aangezien virtuele dispatch altijd via pointers gaat en retourtypes daarom ook altijd pointers zijn. Rust werkt direct met waarden, dus wanneer je Self bij waarde retourneert, moet je de grootte weten.

Methoden mogen geen generieke parameters hebben

trait Serialize {
    fn serialize<T>(&self, output: &mut T);
}

In dit geval zou de compiler een aparte vtable-entry nodig hebben voor elke mogelijke T: serialize::<File> serialize::<String> serialize::<Vec<u8>> ... en zo verder. De lijst zou in essentie oneindig zijn. Daarom zal dit niet compileren: let s: Box<dyn Serialize> = ...; // COMPILE ERROR

Wat betreft C++: deze loopt tegen dezelfde muur aan, aangezien je om dezelfde reden geen template virtuele methode kunt hebben:

class Serialize {
public:
    template<typename T>
    virtual void serialize(T& output); // COMPILE ERROR!!
};

Samenvatting

We begonnen met een eenvoudige vraag: hoe roep je draw() aan op een verzameling vormen in Rust, zonder overerving?

• Monomorfisatie (statische dispatch) in Rust en CRTP in C++ zijn beide compile-time polymorfisme. Ze hebben geen runtime-kosten, maar het nadeel is de code-grootte. In essentie is monomorfisatie een native taalfunctie voor wat CRTP probeert te bereiken als een soort workaround.
• dyn Trait en virtuele functies in C++ gebruiken beide een vtable voor dynamische dispatch. Het verschil is dat in C++ de vtable-pointer in het object leeft, wat overhead toevoegt aan elke instantie, of je nu polymorfisme gebruikt of niet. In Rust verschijnt de vtable-pointer alleen wanneer je expliciet &dyn Trait of Box<dyn Trait> gebruikt.
• Zero-sized types (ZSTs): In C++ moet elk object minimaal 1 byte innemen omdat identiteit op runtime via geheugenadressen wordt gevolgd. In Rust wordt identiteit op compile-time via ownership gevolgd, wat het mogelijk maakt om types met nul grootte te hebben.