1.15.1. Static Dispatch

What happens when we compile generic code?

The compiler copies part of the type or function for each T (for each concrete type), so that each type has its own function. This process is called monomorphization. (Calling methods on a dyn Trait is different: that uses dynamic dispatch, covered later in this article.)

When you build Vec<i32> or HashMap<String, bool>, the compiler copies the generic type and all of its implementation blocks. For example, Vec<i32> replaces the T in Vec<T> with i32, effectively making a full copy of Vec, with every T replaced by i32.

In other words, the compiler replaces the generic parameters of an instance with concrete types. Note that the compiler does not literally duplicate and paste everything; it only copies the code you actually use.

Look at this example:

impl String {
    pub fn contains(&self, p: impl Pattern) -> bool {
        p.is_contained_in(self);
    }
}

Enter fullscreen mode Exit fullscreen mode

  • This example implements a contains method for String
  • The second parameter p of contains is constrained by Pattern. p has no concrete type of its own, only a trait bound, so p is effectively a generic parameter

When p is used in practice, it may be different types. The method is copied for each concrete type, because we need to know the address of is_contained_in so that it can be called. The CPU needs to know where to jump and continue execution.

For any given p, the compiler knows that the address belongs to a method implementation for the Pattern trait. There is no universal address that works for any type.

PS: I know you may be thinking of Python’s dynamic typing, but in Python a variable is fundamentally a **reference* to an object, not a value stored directly.*

Because of this, the compiler needs to produce one copy of the method body for each type, and each copy has its own address for jumping to. That is called static dispatch, because for any given copy of the method, the address we “dispatch to” is known statically.

  • Static in programming usually refers to things known at compile time, or things that can be treated as such

1.15.2. Monomorphization

Monomorphization means the process of turning one generic type into many non-generic types. Rust traits have this property.

After the compiler finishes optimizing the code, it is as if there were no generics at all. Each instance is optimized separately with all known types, so the is_contained_in call in the example above runs just as efficiently as if the trait did not exist at all — there is no performance loss.

The compiler fully understands the types involved, and in the appropriate cases, it can even inline them.

  • “Fully understands the types involved” means Rust is a statically typed language, so the types of all variables and functions can be determined at compile time, without type inference at run time.
  • “Inline them” means expanding the function body directly at the call site to avoid function-call overhead. 
#[inline(always)]
fn add(a: i32, b: i32) -> i32 {
    a + b
}

fn main() {
    let x = add(2, 3);  // The compiler may optimize this into `let x = 2 + 3;`
}

Enter fullscreen mode Exit fullscreen mode

1.15.3. The Cost of Monomorphization

  • Every instance must be compiled separately, which increases compilation time if the compiler cannot optimize it away
  • Each monomorphized function has its own machine code, which makes the program larger
  • Instructions cannot be shared across different instances of a generic method, so CPU instruction-cache efficiency drops because it must hold multiple copies of the same instruction

1.15.4. Dynamic Dispatch

Dynamic dispatch allows code to call trait methods on a generic type without knowing the concrete type.

We can make a small change to the code above to achieve dynamic dispatch:

impl String {
    pub fn contains(&self, p: &dyn Pattern) -> bool {
        p.is_contained_in(self);
    }
}

Enter fullscreen mode Exit fullscreen mode

In this example, dynamic dispatch requires the caller to provide two pieces of information:

  • The data pointer for Pattern
  • The address of is_contained_in

Why does impl Pattern need & in front of it?

  • Dynamic dispatch depends on a trait object, and a trait object is essentially a wide pointer (a fat pointer, as discussed in the previous article), so the data must be passed by reference (because Rust cannot know the memory size of the dynamic dispatch type, it can only use a reference)

1.15.5. Vtable

In practice, the caller provides a pointer to a block of memory called a virtual method table, or vtable for short.

In the example above, it holds the addresses of all trait-method implementations for that type, including the address of is_contained_in.

When the code wants to call a trait method on the provided type, it looks up the implementation address of is_contained_in in the vtable and calls it. This lets us use the same function body without caring which type the caller wants to use.

Each vtable also includes layout and alignment information for the concrete type, which is always needed together with the method information.

1.15.6. Object Safety

The combination of a type implementing a trait and its vtable forms a trait object.

Most traits can be turned into trait objects, but not all. For example, Clone cannot (clone returns Self), and Extend cannot either. These examples are not object-safe.

The specific requirements for object safety are:

  • Trait methods must not be generic, and they must use a receiver that can be dispatched through a trait object
  • The trait cannot have static methods, because there is no instance on which to call them

1.15.7. self: Sized

self: Sized means self cannot be used on a trait object, because trait objects are !Sized.

Using self: Sized on a trait means that dynamic dispatch should never be used.

We can also use self: Sized on a specific method. In that case, the method becomes unavailable when the trait is accessed through a trait object.

When checking whether a trait object is safe, methods marked with where Self: Sized are exempt.

1.15.8. Pros and Cons of Dynamic Dispatch

Advantages Disadvantages
Shorter compilation time The compiler cannot optimize for a specific type
Better CPU instruction-cache efficiency Functions can only be called through the vtable
Method calls have extra overhead
Every method call on a trait object must look up the vtable

1.15.9. How to Choose Between Static and Dynamic Dispatch

Static Dispatch Dynamic Dispatch
Use static dispatch in libraries Use dynamic dispatch in binaries
You cannot know the user’s needs A binary is the final code
If dynamic dispatch is used, the user is stuck with it Dynamic dispatch keeps the code cleaner by removing generic parameters
If static dispatch is used, the user can choose for themselves Compiles faster
At the cost of marginal performance