This is the third part of a series exploring how C, C++, and Rust manage memory at a low level. In Part I we examined how memory is organized at the hardware level. Part II explored ownership and lifetime, showing how the three languages answer the question of who is responsible for freeing memory and when access to that memory is valid.
Part III turns to representation: how abstract types become concrete bit patterns, and how polymorphism, the ability to write code that operates on many types, is implemented.
Table of Contents
Open Table of Contents
-
[The C Layout Algorithm](#the-c…
This is the third part of a series exploring how C, C++, and Rust manage memory at a low level. In Part I we examined how memory is organized at the hardware level. Part II explored ownership and lifetime, showing how the three languages answer the question of who is responsible for freeing memory and when access to that memory is valid.
Part III turns to representation: how abstract types become concrete bit patterns, and how polymorphism, the ability to write code that operates on many types, is implemented.
Table of Contents
Open Table of Contents
Type Layout and Memory Representation
In Part I we established that every type has a size and an alignment, and that compilers insert padding to satisfy alignment constraints. We showed how a poorly ordered struct in C could waste 8 bytes of padding where a well-ordered one used only 2. But we sidestepped a question: who decides the order?
In C and C++, the answer is straightforward: we do. The compiler lays out fields in declaration order, inserting padding as the alignment algorithm dictates. This predictability is essential for binary compatibility, memory-mapped I/O, and network protocols where byte offsets must match external specifications. It is also a constraint: we bear responsibility for field ordering, and a careless declaration can bloat a frequently-allocated struct.
Rust makes a different choice. By default, the compiler reserves the right to reorder fields.
The C Layout Algorithm
C specifies a deterministic algorithm for struct layout. Start with a current offset of zero. For each field in declaration order: add padding until the offset is a multiple of the field’s alignment, record the field’s offset, advance by the field’s size. Finally, round the struct’s total size up to its alignment.
struct Example {
char a; // offset 0, size 1
// 7 bytes padding (align to 8 for double)
double b; // offset 8, size 8
char c; // offset 16, size 1
// 7 bytes padding (struct size must be multiple of 8)
};
// sizeof(struct Example) == 24
The algorithm is mechanical. Given field types and their order, the layout is fully determined. This property is what makes C the lingua franca of FFI: any language that implements the same algorithm can share data structures with C code.
C++ inherits this layout for standard-layout types. The Itanium ABI, which governs most non-Windows C++ implementations, extends the algorithm to handle base classes, virtual functions, and virtual inheritance. For our purposes, a C++ struct without inheritance, virtual functions, or access specifiers mixing fields follows the same layout as C.
The [[no_unique_address]] attribute (C++20) allows the compiler to overlap a data member with another if the member has no members of its own. This enables empty base optimization for member objects:
struct Empty {};
struct WithoutAttribute {
Empty e;
int x;
};
// sizeof(WithoutAttribute) == 8 on typical platforms
// (Empty requires 1 byte in C++, padded to 4 for int alignment)
struct WithAttribute {
[[no_unique_address]] Empty e;
int x;
};
// sizeof(WithAttribute) == 4
Without the attribute, Empty occupies one byte (C++ mandates that different objects have different addresses, so even empty classes have nonzero size). With the attribute, e can share storage with padding or with x itself, reducing the struct to just sizeof(int).
repr(Rust): The Compiler’s Prerogative
Rust’s default representation, repr(Rust), makes minimal guarantees. The specification states only:
- Fields are properly aligned.
- Fields do not overlap (except for ZSTs, which may share addresses).
- The struct’s alignment is at least the maximum alignment of its fields.
There is no guarantee about field order. The compiler may reorder fields to minimize padding, and different compilations of the same source can produce different layouts. The same generic struct instantiated with different type parameters will typically have different field orderings.
Consider:
struct Foo<T, U> {
count: u16,
data1: T,
data2: U,
}
For Foo<u32, u16>, an efficient layout places count and data2 (both 2 bytes) adjacent, followed by data1 (4 bytes):
// Possible layout of Foo<u32, u16>: size 8, align 4
// count: offset 0, size 2
// data2: offset 2, size 2
// data1: offset 4, size 4
For Foo<u16, u32>, the same reordering achieves the same efficiency:
// Possible layout of Foo<u16, u32>: size 8, align 4
// count: offset 0, size 2
// data1: offset 2, size 2
// data2: offset 4, size 4
If Rust preserved declaration order, Foo<u32, u16> would require padding after count:
// Declaration-order layout of Foo<u32, u16>: size 12, align 4
// count: offset 0, size 2
// _pad: offset 2, size 2
// data1: offset 4, size 4
// data2: offset 8, size 2
// _pad: offset 10, size 2
The reordering saves 4 bytes per instance without any annotation or programmer attention.
The trade-off is unpredictability. We cannot assume field offsets. We cannot cast a *const Foo<A, B> to a byte pointer and read at a known offset to extract a field. We cannot send a repr(Rust) struct across a network or write it to a file and expect another compilation (or even the same compilation with different flags) to interpret it correctly.
repr(C): Predictable Layout for FFI
When we need C-compatible layout, we annotate the type with #[repr(C)]:
#[repr(C)]
struct ThreeInts {
first: i16,
second: i8,
third: i32,
}
With repr(C), Rust applies the C layout algorithm. Fields appear in declaration order. Padding follows the standard rules. The resulting layout is compatible with a C struct declared with the same field types and order:
struct ThreeInts {
int16_t first;
int8_t second;
int32_t third;
};
repr(C) is necessary for FFI correctness. It is also useful when we need stable layout for unsafe code that relies on field offsets, or when serializing data to a known binary format. The trade-off is that we accept whatever padding the declaration order implies.
For enums, repr(C) produces a layout compatible with C unions plus a tag. The exact representation depends on whether the enum has fields:
#[repr(C)]
enum MyEnum {
A(u32),
B(f32, u64),
C { x: u32, y: u8 },
D,
}
This is laid out as a repr(C) union of repr(C) structs, where each struct begins with a discriminant of the platform’s C int size:
// Equivalent repr(C) layout:
#[repr(C)]
union MyEnumRepr {
a: MyVariantA,
b: MyVariantB,
c: MyVariantC,
d: MyVariantD,
}
#[repr(C)]
struct MyVariantA { tag: u64, value: u64 }
#[repr(C)]
struct MyVariantB { tag: u64, _pad: u64, value0: f64, _pad2: u64, value1: u64 }
// ... and so on
The discriminant size for a fieldless repr(C) enum matches the C ABI’s enum size, which is implementation-defined. On most platforms, this is int (4 bytes), though some ABIs use smaller types for small enums.
Primitive Representations for Enums
When we need precise control over the discriminant, we can specify an integer type:
#[repr(u8)]
enum Opcode {
Nop = 0,
Load = 1,
Store = 2,
// ... up to 255 variants
}
This enum occupies exactly 1 byte. The discriminant is stored as a u8. This is essential for binary protocols where the tag must fit a specific field width.
For enums with fields, repr(u8) or similar sets the discriminant size but still uses C-style layout for the variant data:
#[repr(u8)]
enum Packet {
Ping,
Data([u8; 64]),
Error(u32),
}
// size: 72 bytes (1 byte tag + 7 padding + 64 data)
// The discriminant is guaranteed to be 1 byte
Combining repr(C) and a primitive representation, like #[repr(C, u8)], specifies both C layout and a specific discriminant type.
Adding an explicit repr to an enum with fields has a consequence: it suppresses niche optimization. This becomes clear after we discuss zero-sized types.
repr(packed): Eliminating Padding
Sometimes we need minimum size regardless of alignment. Network packet headers, binary file formats, and memory-mapped hardware registers often require tightly packed data. repr(packed) removes inter-field padding:
#[repr(packed)]
struct PackedExample {
a: u8,
b: u32,
c: u8,
}
// size: 6 bytes (1 + 4 + 1), no padding
// alignment: 1 byte
Compare with the default layout, which would require 12 bytes (1 + 3 padding + 4 + 1 + 3 padding). The packed version is half the size.
The penalty is that fields may be misaligned. On x86-64, misaligned loads incur a performance penalty. On stricter architectures like ARM without unaligned access support or older SPARC, they cause hardware exceptions. Even on tolerant architectures, misaligned atomics are often incorrect.
Rust addresses part of this problem by making it illegal to create a reference to a misaligned field:
#[repr(packed)]
struct Packed {
a: u8,
b: u32, // may be at offset 1, misaligned
}
let p = Packed { a: 1, b: 2 };
let r: &u32 = &p.b; // ERROR: reference to packed field
The compiler rejects this because a &u32 must point to a 4-byte-aligned address, but p.b may not be. The workaround is to copy the value first:
let value = p.b; // copies the unaligned bytes into a local
let r: &u32 = &value; // value is properly aligned on the stack
Or use raw pointer operations with explicit unaligned reads:
let ptr: *const u32 = std::ptr::addr_of!(p.b);
let value = unsafe { ptr.read_unaligned() };
repr(packed(n)) generalizes this by setting the maximum field alignment to n. Fields with natural alignment less than n are laid out normally; fields with natural alignment greater than n are treated as if their alignment were n. This allows partial packing, trading some space for better access patterns.
For FFI work, combining repr(C, packed) gives C-compatible layout with minimal size. This matches #pragma pack(1) in many C compilers.
repr(align): Preventing False Sharing
While repr(packed) reduces alignment, repr(align(n)) increases it. The attribute forces the type to have alignment of at least n bytes, where n must be a power of two.
Why would we want more alignment than necessary? The answer lies in cache architecture. On x86-64, the L1 cache operates on 64-byte cache lines. When one core writes to an address, the entire cache line containing that address is invalidated in all other cores’ caches. This is the MESI protocol (or variants like MESIF, MOESI) maintaining coherence.
Consider two atomic counters that different threads increment concurrently:
use std::sync::atomic::{AtomicU64, Ordering};
struct Counters {
a: AtomicU64, // offset 0, 8 bytes
b: AtomicU64, // offset 8, 8 bytes
}
Both counters fit in a single 64-byte cache line. When thread 1 increments a, it invalidates thread 2’s cache line. When thread 2 increments b, it invalidates thread 1’s cache line. Neither thread is accessing the other’s data, yet they are constantly invalidating each other’s caches. This is false sharing, and it can degrade performance by an order of magnitude on contended workloads.
The fix is to ensure each counter occupies its own cache line:
use std::sync::atomic::{AtomicU64, Ordering};
#[repr(align(64))]
struct CacheAligned(AtomicU64);
struct Counters {
a: CacheAligned, // offset 0, padded to 64 bytes
b: CacheAligned, // offset 64, padded to 64 bytes
}
Now sizeof::<Counters>() is 128 bytes instead of 16, but a and b cannot share a cache line. Each thread’s writes affect only its own cache line, and the coherence protocol stops bouncing the line between cores.
The trade-off is memory consumption. Padding a 8-byte counter to 64 bytes is an 8x increase. For a handful of hot counters in a concurrent data structure, this is negligible. For an array of thousands of counters, it becomes prohibitive. The choice depends on access patterns: if threads access disjoint counters, alignment helps. If threads frequently access the same counter, the contention is real, not false, and alignment does nothing.
repr(align) can combine with other representations. #[repr(C, align(64))] gives C-compatible field ordering with cache-line alignment. The align modifier applies to the struct as a whole, not to individual fields, so all fields remain at their natural offsets within the enlarged, aligned struct.
repr(transparent): Zero-Cost Wrappers
Sometimes we want a new type that has identical layout to an existing type. The newtype pattern wraps a single field:
struct Meters(f64);
struct Seconds(f64);
With repr(Rust), these types are not guaranteed to have the same layout or ABI as f64. A function returning Meters might use different registers than a function returning f64, even though the underlying data is identical.
repr(transparent) guarantees layout and ABI identity:
#[repr(transparent)]
struct Meters(f64);
#[repr(transparent)]
struct Seconds(f64);
Now Meters has exactly the same size, alignment, and function-call ABI as f64. We can pass a Meters where C expects a double. We can transmute between Meters and f64 (in either direction) without undefined behavior.
repr(transparent) requires that the type has exactly one field with non-zero size, and may have any number of zero-sized fields with alignment 1 (like PhantomData<T>).
This enables patterns like:
use std::marker::PhantomData;
#[repr(transparent)]
struct Id<T>(u64, PhantomData<T>);
Id<User> and Id<Post> are distinct types at compile time but have identical layout to u64. The PhantomData participates in the type system (for variance and drop checking) but not in the layout.
Zero-Sized Types
Rust permits types with size zero:
struct Nothing; // no fields
struct AlsoNothing { } // empty struct
struct MoreNothing(()); // contains unit type
struct AndNothing([u8; 0]); // zero-length array
All of these have size 0 and alignment 1 (the minimum). They occupy no memory. An array [Nothing; 1000000] has size 0.
ZSTs become useful in generic contexts. A HashMap<K, V> stores keys and values. What if we only care about keys? We could duplicate the code as HashSet<K>, or we could define:
type HashSet<K> = HashMap<K, ()>;
Because () is a ZST, HashMap<K, ()> stores no value data. The compiler eliminates loads, stores, and allocations for the values. We get a set implementation from a map implementation with no runtime overhead.
The standard library’s HashSet is implemented exactly this way:
pub struct HashSet<T, S> {
map: HashMap<T, (), S>,
}
Unsafe code must be careful with ZSTs. Pointer arithmetic on *const T where T is zero-sized is a no-op: ptr.add(1) returns ptr unchanged. This breaks the assumption that advancing a pointer produces a different address. Additionally, most allocators do not accept zero-size requests, so Box::new(ZST) uses special handling rather than calling the allocator.
One subtle property: references to ZSTs must be non-null and properly aligned (alignment 1 means any address is valid), but dereferencing them is defined to read zero bytes. A reference to a ZST at address 0x1 is valid; a reference at address 0 (null) is undefined behavior even though no actual memory access occurs.
Empty Types
Zero-sized types can be instantiated. We can create a value of type () or struct Nothing; and pass it around. Empty types go further: they cannot be instantiated at all.
enum Void {}
An enum with no variants has no valid values. We cannot construct a Void because there is no variant to construct. The type exists at the type level but can never exist at the value level.
This enables type-level reasoning about impossibility. Consider a trait for data sources that might fail:
trait DataSource {
type Error;
fn fetch(&self) -> Result<Data, Self::Error>;
}
Most implementations have a meaningful error type: network sources fail with I/O errors, parsers fail with syntax errors. But some sources are infallible. An in-memory cache cannot fail to read its own contents:
enum Infallible {}
struct MemoryCache { data: Data }
impl DataSource for MemoryCache {
type Error = Infallible;
fn fetch(&self) -> Result<Data, Infallible> {
Ok(self.data.clone())
}
}
The Error = Infallible communicates at the type level that fetch cannot return Err. Callers can use an irrefutable pattern:
fn use_cache(cache: &MemoryCache) {
let Ok(data) = cache.fetch(); // no Err case to handle
process(data);
}
The compiler optimizes based on this knowledge. Result<T, Infallible> has the same layout as T because the Err variant cannot exist and requires no discriminant:
use std::mem::size_of;
use std::convert::Infallible;
assert_eq!(size_of::<Result<u64, Infallible>>(), 8); // same as u64
The standard library provides std::convert::Infallible for this purpose. It is defined as an empty enum and used throughout the standard library to indicate operations that cannot fail.
Raw pointers to empty types are valid to construct but dereferencing them is undefined behavior. There is no value to read, so the dereference cannot produce a valid result. This makes empty types unsuitable for representing C’s void*. The recommended approach for opaque C pointers is *const () or a newtype wrapper around it, which can be safely dereferenced to read zero bytes.
Niche Optimization
An enum must somehow record which variant it currently holds. The naive approach stores a discriminant, a small integer that identifies the variant, alongside the variant’s data. For an enum with four variants, we need at least 2 bits to distinguish them; in practice, the discriminant occupies 1, 2, or 4 bytes depending on the number of variants and alignment constraints.
Consider Option<T>, which has two variants: Some(T) and None. The naive layout stores a discriminant plus the T:
// Naive Option<u64> layout:
// discriminant: 1 byte (0 = None, 1 = Some)
// padding: 7 bytes (to align u64)
// value: 8 bytes
// total: 16 bytes
This is wasteful when T is something like &u64. A reference is 8 bytes, so Option<&u64> would be 16 bytes: 8 for the pointer, plus padding and discriminant overhead. But here is the insight that enables optimization: a reference can never be null. Rust guarantees that &T always points to a valid T. The bit pattern consisting of all zeros, the null pointer, can never represent a valid reference.
The compiler exploits this. For Option<&T>, there is no separate discriminant. The Some variant stores the pointer as-is. The None variant is represented by the null pointer. Pattern matching becomes a null check:
// Actual Option<&u64> layout:
// pointer: 8 bytes
// total: 8 bytes
// None is represented as null (0x0000000000000000)
// Some(&x) is represented as the address of x
This is called niche optimization. A niche is a bit pattern that a type guarantees it will never hold. The compiler uses niches to encode enum discriminants without allocating additional space.
Which types have niches? Any type that forbids certain bit patterns:
References (&T, &mut T) forbid null. NonNull<T> exists specifically to be a non-null pointer. The NonZeroU32 type (and its siblings NonZeroU8, NonZeroI64, etc.) forbid zero. Box<T> contains a non-null pointer internally. Function pointers forbid null. bool only permits 0 and 1, so 254 other byte values are niches.
The optimization composes. Option<Box<T>> uses null for None. What about Option<Option<Box<T>>>? The outer Option needs a niche to represent its None, and the inner Option already used null for its None. Can we distinguish outer-None from Some(None)?
On x86-64 with 48-bit virtual addresses, pointers have constraints beyond non-nullness. The upper 16 bits must be a sign extension of bit 47. Most user-space pointers have the top bits all zeros (canonical lower-half addresses). The compiler can use a non-canonical address like 0x0000000000000001 (misaligned for any type with alignment > 1) to represent additional None variants:
use std::mem::size_of;
assert_eq!(size_of::<Box<i32>>(), 8);
assert_eq!(size_of::<Option<Box<i32>>>(), 8);
assert_eq!(size_of::<Option<Option<Box<i32>>>>(), 8);
All three types fit in 8 bytes. The compiler found two niches in the pointer: null for the inner None, and another invalid address for the outer None.
For types without niches, the discriminant requires additional space:
use std::mem::size_of;
assert_eq!(size_of::<u64>(), 8);
assert_eq!(size_of::<Option<u64>>(), 16);
Every bit pattern is a valid u64, so there is no niche. The compiler must store a separate discriminant, and alignment padding expands the total to 16 bytes.
Now we can return to the point we deferred earlier: why does #[repr(u8)] on an enum suppress niche optimization? The repr(u8) attribute guarantees that the discriminant is stored as an explicit u8 at a known location. This is a layout guarantee for FFI and binary serialization. If the compiler used niche optimization, there would be no explicit discriminant byte; the variant would be encoded in the payload’s bit pattern. These two requirements are incompatible. Explicit discriminant layout and niche optimization are mutually exclusive:
use std::mem::size_of;
enum WithNiche { Some(Box<i32>), None }
#[repr(u8)]
enum WithoutNiche { Some(Box<i32>), None }
assert_eq!(size_of::<WithNiche>(), 8); // niche used, no discriminant
assert_eq!(size_of::<WithoutNiche>(), 16); // explicit u8 discriminant + padding + pointer
The repr(u8) forces a 1-byte discriminant to exist, which with 7 bytes of padding and the 8-byte pointer yields 16 bytes total.
Visualizing Layouts
Rust provides std::mem::size_of::<T>() and std::mem::align_of::<T>() for inspecting type properties at runtime (they are const functions, so compile-time evaluation is also possible). For detailed layout information, the -Zprint-type-sizes flag on nightly rustc shows field ordering, padding, and discriminant placement:
RUSTFLAGS=-Zprint-type-sizes cargo +nightly build --release
For an enum like:
enum E {
A,
B(i32),
C(u64, u8, u64, u8),
D(Vec<u32>),
}
The output shows:
print-type-size type: `E`: 32 bytes, alignment: 8 bytes
print-type-size discriminant: 1 bytes
print-type-size variant `D`: 31 bytes
print-type-size padding: 7 bytes
print-type-size field `.0`: 24 bytes, alignment: 8 bytes
print-type-size variant `C`: 23 bytes
print-type-size field `.1`: 1 bytes
print-type-size field `.3`: 1 bytes
print-type-size padding: 5 bytes
print-type-size field `.0`: 8 bytes, alignment: 8 bytes
print-type-size field `.2`: 8 bytes
The compiler has reordered variant C’s fields to place the u8s before the padding, minimizing wasted space. The discriminant is only 1 byte despite four variants (2 bits suffice, but alignment constraints mean 1 byte is the minimum addressable unit).
Fat Pointers and Dynamically Sized Types
We saw how repr(Rust) gives the compiler freedom to reorder fields because it knows each field’s size and alignment at compile time. But this assumption does not always hold. Some types have sizes that can only be determined at runtime, and the way Rust handles them differs sharply from C++.
The Problem with C Arrays
In C, when we pass an array to a function, the type system loses information.
void process(int arr[], size_t len);
int main(void) {
int data[10] = {0};
process(data, 10); // must pass length separately
}
The parameter int arr[] is identical to int *arr. The array decays to a pointer, and the length vanishes from the type. Nothing in the language connects the pointer to its length. If we pass the wrong length, we get buffer overflows. If we forget to pass it entirely, the function cannot know where the array ends.
This decay happens implicitly. The expression data in the call site has type int[10], but by the time it reaches process, it is just int*. The compiler erases information that the programmer must then track manually.
Dynamically Sized Types in Rust
Rust solves this with dynamically sized types (DSTs), types whose size is not known at compile time. The language has three built-in DST categories.
The slice type [T] represents a contiguous sequence of T values of unknown length. Unlike [T; N], which has compile-time-known size N * size_of::<T>(), the type [T] could represent any number of elements. A [u8] might be 10 bytes or 10,000 bytes.
The string slice str is semantically a [u8] with a validity invariant requiring UTF-8 encoding. It shares the same dynamically-sized nature.
Trait objects dyn Trait represent values of unknown concrete type that implement Trait. A dyn Display might be a String at 24 bytes, an i32 at 4 bytes, or a custom type of arbitrary size. The concrete type is erased; only the interface remains.
However, all these types cannot exist directly on the stack or as struct fields (except as the last field). We cannot write let x: [u8]; because the compiler cannot determine how much stack space to allocate. DSTs exist only behind pointers.
Wide Pointers
A pointer to a sized type is a single machine word, 8 bytes on x86-64. A pointer to a DST must carry additional information, making it twice as wide.
For slices, a &[T] stores a pointer to the first element paired with the number of elements.
use std::mem::size_of;
assert_eq!(size_of::<&u8>(), 8); // thin pointer
assert_eq!(size_of::<&[u8]>(), 16); // wide pointer
assert_eq!(size_of::<&str>(), 16); // same representation as &[u8]
We can examine the actual representation using std::ptr::metadata:
let arr = [1i32, 2, 3, 4, 5];
let slice: &[i32] = &arr[1..4];
// The slice is (pointer to arr[1], length 3)
let ptr = slice.as_ptr();
let len = slice.len();
assert_eq!(len, 3);
assert_eq!(unsafe { *ptr }, 2); // first element of slice
The wide pointer solves the C problem. When we pass a &[T], the length travels with the pointer. There is no way to separate them, pass the wrong length or forget it.
The coercion from &[i32; 5] to &[i32] is an unsizing coercion. The compiler takes the thin pointer to the array, combines it with the statically-known length, and produces a wide pointer. This happens implicitly at coercion sites, including let bindings with explicit types, function arguments, and return values.
Trait Object Representation
For trait objects, the wide pointer contains different metadata. A &dyn Trait stores a pointer to the concrete value paired with a pointer to a vtable (virtual method table).
use std::mem::size_of;
trait Drawable {
fn draw(&self);
fn area(&self) -> f64;
}
impl Drawable for i32 {
fn draw(&self) { println!("{}", self); }
fn area(&self) -> f64 { 0.0 }
}
assert_eq!(size_of::<&i32>(), 8);
assert_eq!(size_of::<&dyn Drawable>(), 16);
The vtable is a static data structure generated by the compiler for each (concrete type, trait) pair. It contains function pointers for every method in the trait, plus metadata required for memory management.
For a trait Drawable with methods draw and area, the vtable looks roughly like this:
+0: drop_in_place::<ConcreteType>
+8: size_of::<ConcreteType>
+16: align_of::<ConcreteType>
+24: Drawable::draw for ConcreteType
+32: Drawable::area for ConcreteType
The size and alignment entries are essential for dropping boxed trait objects. When we call drop on a Box<dyn Drawable>, the runtime must know how many bytes to deallocate and what alignment the allocator expects.
Virtual Dispatch in Assembly
When we call a method on a trait object, the compiler generates an indirect call through the vtable. Consider this function:
fn call_draw(obj: &dyn Drawable) {
obj.draw();
}
On x86-64, this compiles to something like:
call_draw:
; rdi = data pointer (obj.data)
; rsi = vtable pointer (obj.vtable)
mov rax, [rsi + 24] ; load draw function pointer from vtable
mov rdi, rdi ; data pointer becomes first argument (self)
jmp rax ; tail call to draw implementation
The vtable lookup adds one memory indirection compared to a direct call. More significantly, the indirect call through a register prevents the CPU from predicting the branch target until the vtable load completes. Modern CPUs have indirect branch predictors, but they are less effective than direct branch prediction.
Compare this to a generic function with static dispatch:
fn call_draw_static<T: Drawable>(obj: &T) {
obj.draw();
}
Here the compiler monomorphizes the function for each concrete T, producing a direct call:
call_draw_static_for_i32:
jmp <i32 as Drawable>::draw
No vtable lookup, no indirect branch. The call target is known at compile time, enabling inlining. If draw is small, the compiler can inline it entirely, eliminating the call overhead and enabling further optimizations across the inlined code.
Performance Implications of Dynamic Dispatch
The overhead of virtual dispatch is not just the vtable lookup. The indirect call has cascading effects on the CPU pipeline.
Modern CPUs predict branch targets to keep the instruction pipeline full. For direct calls, the target is encoded in the instruction itself, and the predictor can fetch the target instructions immediately. For indirect calls through a register, the CPU must wait for the register value to be computed (the vtable load), then use an indirect branch predictor to guess the target. Indirect branch predictors maintain a table of recent indirect branch targets, but they are less accurate than direct branch prediction, especially when a call site dispatches to many different implementations.
When the predictor guesses wrong, the pipeline must be flushed and restarted from the correct target. On modern x86-64, this costs roughly 15-20 cycles. If a tight loop calls a trait object method that alternates between two implementations, the predictor may never stabilize, incurring the misprediction penalty on every other iteration.
The vtable itself must be in cache for the lookup to be fast. A vtable is small (typically 32-64 bytes for a trait with a few methods), but if we iterate over a heterogeneous collection of trait objects, each object may point to a different vtable. With many distinct implementations, the vtables compete for cache space. The first access to each vtable is a cache miss, adding 100+ cycles of memory latency.
Inlining is the most significant loss. When the compiler inlines a function, it can see both caller and callee code simultaneously. This enables constant propagation, dead code elimination, loop fusion, and SIMD vectorization across the boundary. In the general case, none of this is possible through a vtable; the compiler cannot see through the indirection, so each call becomes an optimization barrier.
In C++, modern compilers can sometimes devirtualize virtual calls. If the concrete type is visible at the call site (immediately after construction, or when the class is marked final), Clang/GCC may replace the indirect call with a direct one. With LTO and -fwhole-program-vtables, C++ compilers can devirtualize when only one implementation exists program-wide.
Rust’s situation is less favorable. As of 2024, rustc does not provide the metadata LLVM needs for whole-program devirtualization. Even when only a single type implements a trait in the entire binary, trait object calls remain indirect. LLVM can devirtualize in trivial cases where the concrete type is immediately visible (creating a trait object and calling a method in the same basic block), but this is rare in practice. The tracking issue rust-lang/rust#68262 has seen little progress. For now, if you need devirtualization in Rust, use generics or enums, the compiler will not rescue trait objects for you.
Consider a loop summing areas. Here we must be careful: the static and dynamic versions solve different problems.
// Static dispatch: all elements must be the same concrete type
fn sum_areas_static<T: Drawable>(shapes: &[T]) -> f64 {
shapes.iter().map(|s| s.area()).sum()
}
// Dynamic dispatch: elements can be different concrete types
fn sum_areas_dynamic(shapes: &[&dyn Drawable]) -> f64 {
shapes.iter().map(|s| s.area()).sum()
}
The static version requires a homogeneous slice, all Circles or all Rectangles, never mixed. The dynamic version accepts heterogeneous collections. These are not interchangeable; we choose based on whether we need polymorphism over a closed or open set of types.
For the homogeneous case, the compiler can inline the entire loop body, unroll the loop, and potentially vectorize with SIMD. For the heterogeneous case, each area() call is a function pointer load, an indirect call, and a return. The loop cannot be vectorized because the compiler cannot prove anything about what area() does.
When the set of types is closed and known at compile time, Rust offers a third approach that combines the benefits of both: enum dispatch.
enum Shape {
Circle(Circle),
Rectangle(Rectangle),
}
impl Shape {
fn area(&self) -> f64 {
match self {
Shape::Circle(c) => c.area(),
Shape::Rectangle(r) => r.area(),
}
}
}
fn sum_areas_enum(shapes: &[Shape]) -> f64 {
shapes.iter().map(|s| s.area()).sum()
}
The enum approach accepts a heterogeneous collection (circles and rectangles mixed), but the dispatch is a compile-time match expression rather than a vtable lookup. The compiler can inline each branch, and modern CPUs predict match arms more reliably than indirect calls. The slice is homogeneous at the type level (&[Shape]), so it is cache-friendly, no pointer chasing, no scattered vtables.
The trade-off is extensibility. Adding a new shape to an enum requires modifying the enum definition and every match. With trait objects, new types can implement the trait without touching existing code. Enums are closed; traits are open.
The rule of thumb is to use generics with trait bounds for performance-critical code paths where all elements share a concrete type. Use enums when the type set is closed and we need heterogeneous collections with predictable dispatch. Reserve trait objects for open extensibility where the flexibility is worth the cost, or for reducing compile times and binary size when performance is not critical.
The Vtable Location Trade-off
Rust and C++ made opposite design decisions about where to store the vtable pointer.
In C++, polymorphic objects embed a vptr directly in the object:
class Drawable {
public:
virtual void draw() = 0;
virtual double area() = 0;
virtual ~Drawable() = default;
int x;
};
// Memory layout of a Drawable subclass instance:
// +0: vptr (8 bytes, points to vtable)
// +8: x (4 bytes)
// +12: padding (4 bytes)
// Total: 16 bytes
Every instance of a polymorphic class carries the vptr. A Drawable* or Drawable& is 8 bytes, but each object is 8 bytes larger than it would be without virtual functions.
Rust places the vtable pointer in the reference, not the object:
struct Circle {
radius: f64,
}
impl Drawable for Circle {
fn draw(&self) { /* ... */ }
fn area(&self) -> f64 { std::f64::consts::PI * self.radius * self.radius }
}
// Memory layout of Circle:
// +0: radius (8 bytes)
// Total: 8 bytes (no vptr)
// Memory layout of &dyn Drawable pointing to Circle:
// +0: data pointer (8 bytes)
// +8: vtable pointer (8 bytes)
// Total: 16 bytes
The trade-off is memory allocation versus reference size. With a million objects and one reference each, C++ uses 8 MB for vptrs embedded in objects; Rust uses 8 MB for vtable pointers in references. With a million objects and ten references each, C++ still uses 8 MB; Rust uses 80 MB.
But Rust’s design enables something C++ cannot do. The same object can be viewed through multiple trait lenses simultaneously:
use std::fmt::Debug;
let circle = Circle { radius: 1.0 };
let drawable: &dyn Drawable = &circle;
let debug: &dyn Debug = &circle;
let any: &dyn std::any::Any = &circle;
Each reference carries its own vtable pointer, pointing to different vtables. The circle object itself is unchanged. In C++, the vptr embedded in the object determines its dynamic type at construction time. A Drawable* and a Base* pointing to the same object use the same embedded vptr (possibly adjusted for multiple inheritance).
Dyn Compatibility
Not every trait can be used as a trait object. The rules for dyn compatibility (formerly called object safety) restrict which traits work with dynamic dispatch.
A dyn-compatible trait must not require Self: Sized. Requiring Sized would contradict the purpose of trait objects, which exist to handle values of unknown size. The trait must have no associated constants, since constants require knowing the concrete type at compile time. It must have no associated types with generic parameters, which would require instantiation at compile time.
All methods must be dispatchable or explicitly non-dispatchable. A dispatchable method must have a receiver (&self, &mut self, Box<Self>, etc.), must not return Self by value, must not take Self by value as a parameter, and must not have type parameters.
// Dyn compatible
trait Compatible {
fn method(&self);
fn returns_ref(&self) -> &str;
}
// NOT dyn compatible
trait Incompatible {
fn returns_self(&self) -> Self; // Self in return position
fn takes_self(&self, other: Self); // Self as parameter
fn generic<T>(&self, x: T); // type parameter
const VALUE: i32; // associated constant
}
Dynamic dispatch requires a vtable entry for each method, and a vtable entry is a function pointer with a fixed signature. If a method returns Self, the return type depends on the concrete type, which is erased. If a method is generic over T, there would need to be infinitely many vtable entries, one for each T.
Methods that violate these rules can still exist on dyn-compatible traits if they have a where Self: Sized bound, making them unavailable through trait objects but callable on concrete types:
trait PartiallyCompatible {
fn dispatchable(&self);
fn not_dispatchable(&self) -> Self where Self: Sized;
}
// This works:
let obj: &dyn PartiallyCompatible = &some_value;
obj.dispatchable();
// This does not compile:
// obj.not_dispatchable();
Auto Traits and Lifetime Bounds
Trait objects can include auto traits and lifetime bounds. Unlike regular traits, where only one non-auto trait is allowed, auto traits can be added freely:
use std::fmt::Debug;
// All valid trait object types:
fn takes_debug(x: &dyn Debug) {}
fn takes_debug_send(x: &dyn Debug + Send) {}
fn takes_debug_send_sync(x: &(dyn Debug + Send + Sync)) {}
fn takes_debug_static(x: &(dyn Debug + 'static)) {}
The auto traits (Send, Sync, Unpin, etc.) do not add methods to the vtable. They are marker traits checked at compile time when the trait object is created. If we try to create a &dyn Debug + Send from a type that is not Send, the compiler rejects it:
use std::rc::Rc;
use std::fmt::Debug;
let rc: Rc<i32> = Rc::new(42);
// Error: Rc<i32> is not Send
// let obj: &(dyn Debug + Send) = &*rc;
Lifetime bounds constrain how long references inside the trait object can live. A dyn Trait + 'static contains no non-'static references. A dyn Trait + 'a may contain references that live at least as long as 'a. The default lifetime depends on context and follows elision rules.
Supertraits in the Vtable
When a trait has supertraits, the vtable includes method entries for the supertrait methods:
trait Shape {
fn area(&self) -> f64;
}
trait Circle: Shape {
fn radius(&self) -> f64;
}
The vtable for dyn Circle contains entries for both area and radius. When we call a supertrait method on a trait object, it goes through the same vtable lookup:
fn print_area(c: &dyn Circle) {
// This works because Shape::area is in the Circle vtable
println!("Area: {}", c.area());
}
Trait object upcasting allows converting &dyn Circle to &dyn Shape. The compiler generates a different vtable for dyn Shape that contains only area, and the conversion substitutes the vtable pointer:
fn use_as_shape(c: &dyn Circle) {
let shape: &dyn Shape = c; // upcasting coercion
println!("Area: {}", shape.area());
}
The ?Sized Bound
By default, all type parameters have an implicit Sized bound:
fn foo<T>(x: T) { }
// is equivalent to:
fn foo<T: Sized>(x: T) { }
This makes sense. To pass x by value, the compiler must know its size to copy it onto the stack. But sometimes we want to accept DSTs through references. The ?Sized bound relaxes the Sized requirement:
fn process<T: ?Sized>(x: &T) {
// T might be a DST
// x is a wide pointer if T is unsized
}
// Now this works:
process::<[u8]>(&[1, 2, 3][..]);
process::<str>("hello");
process::<dyn std::fmt::Debug>(&42);
The standard library uses ?Sized extensively. The signature of std::borrow::Borrow is:
pub trait Borrow<Borrowed: ?Sized> {
fn borrow(&self) -> &Borrowed;
}
This allows String to implement Borrow<str>, returning &str, a reference to a DST.
In trait definitions, Self has an implicit Self: ?Sized bound, the opposite of type parameters. This allows traits to be implemented for DSTs:
trait MyTrait {
fn method(&self);
}
impl MyTrait for str {
fn method(&self) {
println!("length: {}", self.len());
}
}
If traits required Self: Sized by default, we could not implement traits for str, [T], or dyn OtherTrait.
Custom DSTs
A struct can contain a DST as its last field, making the struct itself a DST:
struct MySlice {
header: u32,
data: [u8], // DST as last field
}
MySlice is now a DST. We cannot create it directly on the stack. The only supported construction method is through unsizing coercion from a sized variant:
struct MySized<const N: usize> {
header: u32,
data: [u8; N],
}
fn main() {
let sized = MySized::<4> { header: 42, data: [1, 2, 3, 4] };
let dynamic: &MySlice = unsafe {
// Requires ptr::from_raw_parts or careful transmutation
std::mem::transmute::<&MySized<4>, &MySlice>(&sized)
};
assert_eq!(dynamic.header, 42);
assert_eq!(dynamic.data.len(), 4);
}
This is awkward and requires unsafe code. The ptr::from_raw_parts API (stabilized in Rust 1.79) provides a safer way to construct custom DST pointers, but the ergonomics remain poor. Most code uses the built-in DST types ([T], str, dyn Trait) rather than defining custom ones.
To construct a DST, we must provide the metadata (length or vtable pointer) that completes the type. But the language provides no syntax for this at the value level. The standard library handles DST construction internally through careful unsafe code and compiler magic for types like str and [T].
Invalid Metadata is Undefined Behavior
The metadata in a wide pointer is not merely informational. The compiler trusts it for safety-critical operations. Providing invalid metadata is undefined behavior.
For slices, the length must not cause the slice to extend beyond its allocation:
let arr = [1, 2, 3];
let ptr = arr.as_ptr();
// UB: length 1000 exceeds the allocation
let bad_slice: &[i32] = unsafe {
std::slice::from_raw_parts(ptr, 1000)
};
For trait objects, the vtable must be a valid vtable for the trait that matches the actual dynamic type of the pointed-to object:
// UB: null is not a valid vtable
let data_ptr: *const () = &42i32 as *const i32 as *const ();
let vtable_ptr: *const () = std::ptr::null();
let bad: &dyn std::fmt::Debug = unsafe {
std::mem::transmute((data_ptr, vtable_ptr))
};
The Rust Reference explicitly lists invalid wide pointer metadata as undefined behavior. Calling a method through a corrupted vtable pointer could jump to arbitrary code. Using an invalid slice length could read or write out of bounds.
Polymorphism: Monomorphization vs Vtables
We saw how Rust represents pointers to dynamically sized types. A &dyn Draw carries both a data pointer and a vtable pointer, 16 bytes that enable runtime method dispatch. But this raises a question we have not yet answered: why does Rust need two polymorphism mechanisms at all? Templates and generics already let us write code that works across types. Why introduce vtables?
When we write a function that operates on “any type implementing trait X,” the compiler must decide how to generate code for it. Two strategies exist. The compiler can stamp out a separate copy of the function for each concrete type that actually gets used, a process called monomorphization. Alternatively, the compiler can generate a single copy of the function that dispatches method calls through a table of function pointers at runtime. Both C++ and Rust support both strategies. C, lacking native generics, provides only workarounds that approximate each approach with varying degrees of type safety.
Monomorphization eliminates runtime indirection entirely; every call is direct, every function body can be inlined, the optimizer sees through abstraction boundaries. But the binary contains a separate copy of the generic code for every type instantiation, which bloats both compile time and binary size. Dynamic dispatch through vtables produces a single copy of the code regardless of how many implementing types exist, but every method call requires loading a function pointer from memory and jumping through it, which the CPU cannot predict well and which prevents inlining.
C Without Generics
C has no built-in parametric polymorphism. We cannot write a function that operates on “any comparable type” and have the compiler generate type-safe, specialized versions. Historically, C programmers used three workarounds.
Preprocessor macros perform textual substitution before the compiler ever sees the code:
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int x = MAX(3, 5); // expands to ((3) > (5) ? (3) : (5))
double y = MAX(1.5, 2.5); // expands to ((1.5) > (2.5) ? (1.5) : (2.5))
Each use site expands to type-specific code, achieving something like monomorphization. But macros operate outside the type system. The preprocessor has no concept of what a and `b