Crust of Rust: Dispatch, Fat Pointers, and Vtables

In Rust, polymorphism is handled through two distinct mechanisms: static dispatch via monomorphization and dynamic dispatch via trait objects (dyn Trait). Understanding the trade-offs between these approaches requires looking into Rust's memory layout, the Sized marker trait, fat pointer architecture, and the object-safety rules governing virtual dispatch tables (vtables).

1. Monomorphization and Static Dispatch

By default, generic functions and types in Rust utilize static dispatch. The compiler translates generic code into concrete code by generating dedicated copies of the function or struct for every concrete type used at compile time. This process is called monomorphization.

Code Evolution: From Generic Abstraction to Monomorphized Machine Code

Consider a generic function that computes the length of any type implementing AsRef<str>:

// Generic abstraction using an implicit trait bound
pub fn sterlin<S: AsRef<str>>(s: S) -> usize {
    s.as_ref().len()
}

pub fn demo() {
    let len1 = sterlin("hello world");            // Called with &'static str
    let len2 = sterlin(String::from("norway"));   // Called with String
}

During compilation, Rust inspects every call site and monomorphizes sterlin into type-specific instances:

// Monomorphized compiler outputs (conceptual equivalent)
fn sterlin_str(s: &str) -> usize {
    s.as_ref().len()
}

fn sterlin_string(s: String) -> usize {
    s.as_ref().len()
}

pub fn demo_monomorphized() {
    let len1 = sterlin_str("hello world");
    let len2 = sterlin_string(String::from("norway"));
}

Advantages and Disadvantages of Monomorphization

2. The Sized Trait and Dynamically Sized Types (DSTs)

To manage stack allocation and pass arguments efficiently, the Rust compiler must know the precise size of data types at compile time.

The Sized Marker Trait

Sized is an auto-implemented marker trait in the Rust standard library (std::marker::Sized).

pub trait Sized {}

Virtually every generic type parameter in Rust implicitly includes a Sized bound:

// What you write:
fn process<T>(item: T) {}

// What the compiler sees:
fn process<T: Sized>(item: T) {}

Why Functions Require Sized Arguments

At the machine level, function call ABIs rely on fixed frame layouts. Stack frame allocation and CPU register assignment require the caller and callee to know the exact byte offsets of parameters and return values:

If an argument's size is unknown at compile time, the compiler cannot generate fixed stack frame offsets or array index arithmetic ($O(1)$ address lookup: $\text{Base} + i \times \text{Size}$).

Unsized Types (Dynamically Sized Types / DSTs)

A type whose size is only known at runtime is a Dynamically Sized Type (DST). Key examples include:

1. Slices: [T] or str (an un-sized sequence of elements/bytes).
2. Trait Objects: dyn Trait (an abstract representation of any type implementing Trait).

To opt out of the implicit Sized constraint, Rust provides the relaxed bound syntax ?Sized:

// T may be Sized OR Unsized (DST)
pub struct Cow<'a, B: ?Sized + 'a> 
where
    B: ToOwned,
{
    pub ptr: &'a B,
}

3. Dynamic Dispatch and Trait Objects (dyn Trait)

When a program needs to store heterogeneous types in a single collection or avoid compiling thousands of monomorphized instances, dynamic dispatch is used.

Real-Life Analogy

Think of a graphical user interface (GUI) rendering loop. A Canvas contains a list of shapes to draw: Button, Image, TextBox, and Slider. Rather than monomorphizing separate canvas render loops for every distinct array of concrete components, the canvas maintains a list of pointers to "anything that implements the Draw trait." The canvas calls .draw() on each pointer, leaving the underlying shape to execute its specific drawing logic at runtime.

Monomorphization Failure with Heterogeneous Collections

pub trait High {
    fn hi(&self);
}

impl High for str {
    fn hi(&self) { println!("{}", self); }
}

impl High for String {
    fn hi(&self) { println!("{}", self); }
}

// Fails to compile: Heterogeneous array elements must have uniform size!
// let items = [ "hello", String::from("world") ];

To erase concrete types and store these objects together, we turn them into Trait Objects using the dyn keyword:

// Indirection behind a pointer makes the overall reference Sized!
pub fn say_all_hi(items: &[&dyn High]) {
    for item in items {
        item.hi(); // Dynamic dispatch call
    }
}

4. Fat Pointers: Memory Layout and Architecture

Because a DST (str, [T], dyn Trait) does not have a static size, a bare pointer (*const DST or &DST) cannot point solely to a raw memory address. Instead, pointers to DSTs are stored as Fat Pointers (also called Wide Pointers).

A fat pointer is twice the size of a standard pointer ($2 \times \text{usize}$, or 16 bytes on a 64-bit architecture).

Memory Architecture Comparison

5. The Vtable Mechanics and Memory Architecture

When a type is cast or coerced to a trait object (e.g., &String to &dyn High), the compiler builds a static Virtual Dispatch Table (Vtable) for that specific type-trait pair.

Structural Breakdown of a Vtable

A vtable is a statically allocated structure in the read-only data section (.rodata) of the executable. It contains pointers to the trait's virtual methods along with object cleanup metadata:

// Conceptual mental model of a compiler-generated Vtable layout
#[repr(C)]
struct TraitVTable {
    // 1. Destructor pointer for running Drop logic
    drop_in_place: fn(*mut ()),
    
    // 2. Size of the concrete object instance (in bytes)
    size: usize,
    
    // 3. Memory alignment of the concrete object instance
    align: usize,
    
    // 4. Function pointers for each trait method
    method_1: fn(*const ()),
    method_2: fn(*const ()),
}

Vertical Dynamic Call Walkthrough

When executing item.hi() on a &dyn High fat pointer:

Caller Execution
   |
   | 1. Reads Fat Pointer (Data Pointer + Vtable Pointer)
   v
Vtable Pointer
   |
   | 2. Dereferences Vtable pointer to locate function address `hi`
   v
Function Pointer Entry in Vtable
   |
   | 3. Passes Data Pointer as `self` receiver argument
   v
Executes Concrete Implementation: String::hi(data_ptr)

Note: The inclusion of drop_in_place, size, and align inside the vtable is mandatory. When a Box<dyn Trait> goes out of scope, the heap deallocator must clean up memory and invoke the underlying type's destructor without knowing the concrete type. It retrieves the object size, alignment, and drop function pointer directly from the vtable.

6. Object Safety Rules and Restrictions

Not all traits can be turned into trait objects. A trait is declared Object Safe by the compiler only if its vtable can be safely constructed and resolved at runtime.

Rule Summary Matrix

Code Example: Combining Traits via Supertraits

Attempting to instantiate &dyn (High + AsRef<str>) directly fails compilation because a fat pointer holds only two words (data reference + single vtable reference).

To bypass this restriction, declare a combined supertrait:

pub trait High: AsRef<str> {
    fn hi(&self);
}

// Now `dyn High` includes method entries for both `hi` AND `as_ref` inside one vtable!
pub fn process_supertrait(item: &dyn High) {
    println!("As string slice: {}", item.as_ref());
    item.hi();
}

7. Selective Object Safety via where Self: Sized

A trait can contain non-object-safe methods and still remain an object-safe trait overall, provided those non-object-safe methods are explicitly excluded from the vtable using a where Self: Sized bound.

The Standard Library Iterator Pattern

The standard library Iterator trait contains object-safe methods (like next) alongside non-object-safe generic methods (like chain or collect).

pub trait Iterator {
    type Item;

    // OBJECT SAFE: Can be placed in the vtable
    fn next(&mut self) -> Option<Self::Item>;

    // NON-OBJECT SAFE: Excluded from vtable using `where Self: Sized`
    fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter>
    where
        Self: Sized,
        U: IntoIterator<Item = Self::Item>,
    {
        // ...
        todo!()
    }
}

When Iterator is used as a trait object (&mut dyn Iterator<Item = u32>), the type parameter Self becomes the unsized type dyn Iterator<Item = u32>.

Because dyn Iterator does not implement Sized, methods marked where Self: Sized automatically drop out of the vtable, keeping the trait object safe to compile.

pub fn consume_next(iter: &mut dyn Iterator<Item = u32>) {
    let _ = iter.next(); // Compiles fine!
    
    // ERROR: `iter.chain(...)` cannot be called on a trait object 
    // because `Chain` requires `Self: Sized`.
}

8. Function Trait Taxonomy: fn(), impl Fn(), dyn Fn()

Function invocation abstractions in Rust differ fundamentally across operational efficiency and pointer representations:

// 1. Function Pointer: Thin pointer (8 bytes). Cannot capture environment variables.
pub fn call_fn_ptr(f: fn(i32) -> i32, val: i32) -> i32 {
    f(val)
}

// 2. Monomorphized Closure: Zero cost runtime, monomorphized per closure type.
pub fn call_impl_fn(f: impl Fn(i32) -> i32, val: i32) -> i32 {
    f(val)
}

// 3. Dynamic Closure Trait Object: Fat pointer (16 bytes). Erases closure context.
pub fn call_dyn_fn(f: &dyn Fn(i32) -> i32, val: i32) -> i32 {
    f(val)
}

Technical Synthesis Table

9. Advanced Applications: Manual Vtables and Pointer Metadata

Standard Library Case Study: RawWaker

In asynchronous Rust, std::task::Waker relies on dynamic dispatch. To avoid requiring heap allocations (Box) for runtime wakers on embedded systems, Rust constructs a vtable manually via standard raw pointers and C-style function tables:

pub struct RawWakerVTable {
    clone: unsafe fn(*const ()) -> RawWaker,
    wake: unsafe fn(*const ()),
    wake_by_ref: unsafe fn(*const ()),
    drop: unsafe fn(*const ()),
}

This bypasses dyn Trait fat pointer syntax while reproducing low-level dynamic dispatch manually using lightweight function pointer tables.

RFC 2580 (ptr_meta / Custom DSTs)

Under RFC 2580, Rust standardizes fat pointer introspection. Instead of treating fat pointers as compiler internal magic, pointers expose metadata via the Pointee trait:

// Conceptual API from RFC 2580
pub trait Pointee {
    type Metadata: Copy + Send + Sync + Ord + Hash;
}

// For Sized types: Metadata = ()
// For Slices [T]: Metadata = usize (length)
// For dyn Trait: Metadata = DynMetadata<dyn Trait> (opaque pointer to vtable)

Runtime Downcasting via std::any::Any

The std::any::Any trait enables dynamic type reflection. The vtable constructed for dyn Any includes a unique compiler-generated TypeId hash:

use std::any::Any;

pub fn print_if_string(value: &dyn Any) {
    if let Some(s) = value.downcast_ref::<String>() {
        println!("Extracted string: {}", s);
    } else {
        println!("Not a string instance.");
    }
}

Internally, downcast_ref queries the type ID from the vtable metadata. If the type ID matches TypeId::of::<String>(), it safely converts the fat pointer back into a concrete &String reference.

Summary and Key Takeaways

• Monomorphization converts generic Rust abstractions (T) into type-specific machine code at compile time, trading larger binary sizes and cache efficiency for optimized runtime performance.
• Sized is an implicit bound (T: Sized) on almost all generics. Types with unknown compile-time sizes (str, [T], dyn Trait) are Dynamically Sized Types (DSTs) and must live behind pointers.
• Fat Pointers double pointer width ($16$ bytes on 64-bit systems) to store required runtime metadata alongside memory addresses.
• Slice Fat Pointers consist of (data_ptr, len), whereas Trait Object Fat Pointers consist of (data_ptr, vtable_ptr).
• Vtables store pointers to instance method implementations alongside metadata needed for object cleanup (drop_in_place, size, and align).
• Object Safety enforces that traits used with dyn must have known vtable footprints. Traits with generic methods, methods returning Self, or unbound associated types are not object-safe.
• where Self: Sized allows non-object-safe methods to be excluded selectively from vtables, allowing traits like Iterator to remain object-safe for their primary methods.