🦀Understanding Rust’s Trait Objects

Fat-pointers, Vtables, and dynamic dispatch in Rust

Photo by Andrea Qoqonga on Unsplash

This article investigates how Rust handles dynamic dispatch using trait objects and vtables. We will also explore how the Rust compiler can sometimes optimize tail calls in the context of dynamic dispatch.

To illustrate these concepts, we will work with the following example code:

pub trait Shape {
    type T;
    fn area(&self) -> Self::T;
}

pub trait Draw: Shape {
    fn draw(&self);
}

// The function operates with a trait object reference
pub fn draw_dynamic(a: &dyn Draw<T = f64>) {
    a.draw();
}

// Invokes the draw method and then the area method on the trait object
pub fn draw_and_report_area_dynamic(a: &dyn Draw<T = f64>) -> f64 {
    a.draw();
    a.area()
}

Before we proceed, let us learn about fat-pointers vtables in Rust.

Trait object fat pointer and the vtable

“Under the hood, trait objects in Rust are implemented using fat pointers. Let’s explore this concept with an example involving the Draw trait.

A fat pointer consists of two components: the first pointer references the data of the concrete type that implements the Draw trait. In contrast, the second pointer refers to the vtable (virtual function table) associated with that concrete type. The vtable is a data structure containing pointers to the methods implemented by the concrete type. It also stores crucial metadata about the concrete type, including its destructor, alignment, and size.

The diagram below illustrates the structure of a trait object’s fat pointer, highlighting the byte offsets for both the fat pointer and the vtable.

Now that we understand fat pointers and vtablesLet us look at the generated assembly for the draw_dynamic.

Assembly output for draw_dynamic

pub fn draw_dynamic(a: &dyn Draw<T = f64>) {
    a.draw();
}

The generated assembly code for the draw_dynamic function includes a jump to the vtable's address of the draw function instead of a typical call. This optimization, called tail call optimization (TCO), avoids creating a new stack frame and return address for the final function in the call chain.

In this example, the draw function returns directly to the caller of draw_dynamic using the existing return address on the stack. This is feasible because the rdi register already points to the concrete object that implements the Draw trait, meeting the self parameter requirement for the draw function.

Assembly output for draw_and_report_area_dynamic

Let us look at the generated assembly when two trait methods are called.

pub fn draw_and_report_area_dynamic(a: &dyn Draw<T = f64>) -> f64 {
    a.draw();
    a.area()
}

The generated assembly code for the draw_and_report_area_dynamic function is more complex than that of draw_dynamic. It first retrieves the addresses of the draw and area methods from the vtable, using offsets of 32 and 24, respectively. The draw method uses a call instruction, which creates a new stack frame and return address.

In contrast, the area method uses a jump instruction, signaling that it qualifies for tail call optimization (TCO). Since the area method is the final function call in draw_and_report_area_dynamic, the compiler can optimize it by replacing the call with a jump. This optimization removes the overhead of creating a new stack frame and return address. Additionally, the area method's return value directly becomes the return value of draw_and_report_area_dynamic, ensuring the correctness of the code remains unaffected by the optimization.

What We Learned

This post explored how Rust handles dynamic dispatch through trait objects, fat pointers, and vtables. We learned that:

• Trait Objects and Fat Pointers: Rust uses fat pointers to enable dynamic dispatch. These pointers contain pointers to both the concrete data and the associated vtable. This allows for polymorphic behavior without sacrificing safety.
• Role of the Vtable: The vtable is a key data structure that stores method addresses, type metadata, and information about the concrete type’s destructor, alignment, and size.
• Dynamic Dispatch in Assembly: We examined how Rust’s compiler generates assembly for functions using dynamic dispatch, observing optimizations like tail call optimization (TCO), which can improve performance by eliminating unnecessary stack frames.
• Practical Examples: Through our draw_dynamic and draw_and_report_area_dynamic For example, we saw the differences in assembly-level implementation and how the compiler decides when to apply optimizations.

Rust Under the Hood

If you enjoyed this deep dive into vtables and fat pointers, you’ll love my book, Rust Under the Hood. It explores the internals of Rust with clear explanations and detailed assembly-level insights. It is available in paperback, eBook, and PDF formats.

Paperback and eBook

Rust Under the Hood: A deep dive into Rust internals and generated assembly

PDF

Rust Under the Hood