Generics, Monomorphization, and Dynamic Dispatch

A trait says what a type can do. This chapter is about the two ways a program can use that fact, and about a choice that most languages make for you.

In Java, calling a method through an interface is a virtual call: the object carries a pointer to a table of method implementations, and the call goes through it at runtime. In C++, a template is expanded at compile time into a separate copy of the code for each type it is used with, and a virtual method is a table lookup, and the two mechanisms are entirely separate.

Rust has both and makes you pick, with a syntax difference of a few characters. Understanding what each one costs is the difference between writing code that is genuinely as fast as C and writing code that merely looks like it.

Generics are expanded, not shared

A generic function is a template. Nothing about it exists at runtime until it is used, and when it is used the compiler generates a copy specialized for the concrete types:

fn largest<T: PartialOrd>(items: &[T]) -> &T {
    let mut best = &items[0];
    for item in items {
        if item > best {
            best = item;
        }
    }
    best
}

fn main() {
    println!("{}", largest(&[3, 7, 2]));
    println!("{}", largest(&["pear", "apple"]));
}

The compiled binary contains two largest functions: one taking &[i32] and one taking &[&str]. Neither is generic, neither looks at a method table, and the comparison inside each is a direct call that the optimizer can inline. This process is called monomorphization, and it is why generic Rust code has no runtime penalty at all compared to code written by hand for one type.

The cost shows up elsewhere. Each instantiation is real code that has to be compiled and occupies space in the binary. A generic function used with fifteen types produces fifteen copies; a generic function that calls other generic functions multiplies. This is the main reason Rust compiles slowly and why binaries are larger than the equivalent C, and on a large project it is worth knowing about before it becomes a problem.

impl Trait in argument position is the same mechanism with less ceremony:

use std::fmt::Display;

fn announce(value: impl Display) {
    println!("-> {value}");
}

fn announce_explicit<T: Display>(value: T) {
    println!("-> {value}");
}

fn main() {
    announce(42);
    announce_explicit("forty-two");
}

Those two functions compile to the same thing. The impl Trait form is shorter and the explicit form lets callers specify the type with turbofish syntax and lets the same parameter appear twice, so use the short one until you need the other.

In return position, impl Trait means something different and useful: the function returns one specific type that the caller is not told the name of.

fn evens(limit: u32) -> impl Iterator<Item = u32> {
    (0..limit).filter(|n| n % 2 == 0)
}

fn main() {
    println!("{:?}", evens(10).collect::<Vec<_>>());
}

The actual return type is an unnameable compound of Filter and Range and a closure. impl Iterator<Item = u32> lets the function keep that private while the caller still gets static dispatch and full inlining. Every iterator chain you return from a function will use this.

Trait objects are dispatched at runtime

The other mechanism is dyn Trait, which erases the concrete type:

trait Shape {
    fn area(&self) -> f64;
    fn name(&self) -> &'static str;
}

struct Circle { radius: f64 }
struct Square { side: f64 }

impl Shape for Circle {
    fn area(&self) -> f64 { std::f64::consts::PI * self.radius * self.radius }
    fn name(&self) -> &'static str { "circle" }
}

impl Shape for Square {
    fn area(&self) -> f64 { self.side * self.side }
    fn name(&self) -> &'static str { "square" }
}

fn main() {
    let shapes: Vec<Box<dyn Shape>> = vec![
        Box::new(Circle { radius: 1.0 }),
        Box::new(Square { side: 2.0 }),
        Box::new(Circle { radius: 0.5 }),
    ];

    let total: f64 = shapes.iter().map(|shape| shape.area()).sum();
    for shape in &shapes {
        println!("{} {:.3}", shape.name(), shape.area());
    }
    println!("total {total:.3}");
}

This is the thing generics cannot do. A Vec<T> holds one type; a Vec<Box<dyn Shape>> holds a mixture, because each element is a pointer to a value plus a pointer to that value’s method table. A reference to a trait object is therefore two machine words rather than one, which is why you meet dyn Trait almost always behind a Box, an Rc, or a reference — the value itself has no size known at compile time.

The method table, or vtable, holds the function pointers for the trait’s methods plus the value’s size, alignment and destructor. A call through it is an indirect jump: cheap in absolute terms, and not inlinable, which is the real cost. A tight loop calling a trait object’s method a million times loses the optimizations that matter, and the same loop over a generic type keeps them.

Note

Box<dyn Error> from chapter 8 is a trait object, and so is every closure stored in a struct as Box<dyn Fn(i32) -> i32>. You have probably already used them without naming them.

Not every trait can be a trait object

Erasing the type means the compiler must be able to build a vtable, and some trait definitions make that impossible. The rules are called object safety, and in practice two of them account for almost everything you will hit.

A method that is generic over a type parameter cannot go in a vtable, because there would have to be an entry for every type it might be called with, and that set is unbounded. A method returning Self by value cannot either, because the caller would not know how large the returned value is.

#![allow(unused)]
fn main() {
trait Spawn {
    fn duplicate(&self) -> Self;
}

fn make_two(source: &dyn Spawn) {
    let _copy = source.duplicate();
}
}

That fails with an object-safety error naming duplicate. The usual fix is to move the offending method behind a where Self: Sized clause, which makes it available on concrete types and excludes it from the object, or to return Box<Self> instead of Self. Clone is the standard library’s example: it is not object safe, which is why Box<dyn Trait> is awkward to clone and why crates exist solely to work around it.

This matters at design time rather than at use time. A trait intended as an extension point should be checked for object safety early, because discovering that it cannot be one after twenty types implement it is an unpleasant refactoring.

Choosing between them

The decision is usually clear once you ask the right question, and the right question is not “which is faster”.

Do you need a collection, or a field, holding several different types? Then it is a trait object. Generics cannot express a heterogeneous container, and there is no amount of cleverness that changes that. A list of plugins, a stack of middleware, a vector of shapes, a set of event handlers: all trait objects.

Is the type known at the call site, in code that runs a great many times? Then it is generics. Sorting, numeric work, iterator pipelines, anything inside a hot loop. Inlining is where most of the performance comes from, and dynamic dispatch gives it up.

Is the trait crossing a boundary where the concrete types are not knowable? A plugin loaded at runtime, a callback registered by the user of your library, a dependency injected for testing: trait object, because there is no compile-time set to enumerate.

Is compile time or binary size hurting? Then dynamic dispatch is a lever. Generic code instantiated in a hundred places can often keep a generic outer layer for ergonomics while immediately converting to a trait object inside:

use std::fmt::Debug;

fn log_all(items: &[&dyn Debug]) {
    for item in items {
        println!("{item:?}");
    }
}

fn log_one(item: &impl Debug) {
    log_all(&[item]);
}

fn main() {
    log_one(&42);
    log_one(&"text");
}

log_one is generic and gets one small instantiation per type; log_all holds the real body and is compiled once. For a function with a large body called with many types, this can cut compile time noticeably and costs a few nanoseconds per call. The standard library does this internally in several places.

When none of the above applies, and the code is not hot, either works. Start with generics — the default in Rust — and switch when you find a reason.

Associated types

A trait can declare a type as part of its contract rather than taking it as a parameter:

trait Repository {
    type Item;
    type Key;

    fn get(&self, key: &Self::Key) -> Option<&Self::Item>;
    fn put(&mut self, key: Self::Key, item: Self::Item);
}

use std::collections::HashMap;

struct UserRepo {
    users: HashMap<u32, String>,
}

impl Repository for UserRepo {
    type Item = String;
    type Key = u32;

    fn get(&self, key: &u32) -> Option<&String> {
        self.users.get(key)
    }

    fn put(&mut self, key: u32, item: String) {
        self.users.insert(key, item);
    }
}

fn main() {
    let mut repo = UserRepo { users: HashMap::new() };
    repo.put(1, String::from("ada"));
    println!("{:?}", repo.get(&1));
}

The distinction between an associated type and a type parameter is about how many times a type may implement the trait.

Use an associated type when each implementor has one natural answer. Iterator has type Item because a given iterator yields one kind of thing; if it were Iterator<T>, a type could implement it several times and every call to next would be ambiguous.

Use a type parameter when a type should implement the trait repeatedly with different types. From<T> is the example: a single error enum implements From<io::Error> and From<ParseIntError> and as many more as it needs, and being able to do so repeatedly is the reason it takes a parameter.

Getting this backwards produces traits that are painful in a way that is hard to diagnose, so the question — one answer per implementor, or many? — is worth asking explicitly when you write a trait.

Generic types and conditional behavior

Structs take type parameters too, and their impl blocks can add capability conditionally:

use std::fmt::Display;

struct Pair<T> {
    left: T,
    right: T,
}

impl<T> Pair<T> {
    fn new(left: T, right: T) -> Pair<T> {
        Pair { left, right }
    }
}

impl<T: Display + PartialOrd> Pair<T> {
    fn announce_larger(&self) {
        if self.left >= self.right {
            println!("larger is {}", self.left);
        } else {
            println!("larger is {}", self.right);
        }
    }
}

fn main() {
    Pair::new(3, 8).announce_larger();
    Pair::new("b", "a").announce_larger();
}

Every Pair<T> has new. Only a Pair<T> whose T can be displayed and compared has announce_larger. A Pair<Socket> would compile fine and simply not have that method, and the error for calling it names the missing bound.

This is a genuinely different capability from anything in a class-based language, where a class either has a method or does not. It is how the standard library gives Vec<T> a sort only when T: Ord, and Option<T> a copied only when T: Copy, and it is worth reaching for when a type’s behavior really does depend on what it contains.

Conclusion

Generics are expanded at compile time into one specialized copy per type, so they cost nothing at runtime and cost compile time and binary size instead. Trait objects erase the type behind a pointer pair, so they cost an indirect call and the inlining it prevents, and they buy the one thing generics cannot do: holding several different types behind one interface.

The choice follows the shape of the problem rather than a general preference. Heterogeneous collections and runtime extension points need trait objects. Hot paths with known types want generics. A large generic body called from many places can be both: a thin generic shell over a single dynamically dispatched implementation.

Associated types and type parameters look similar and answer different questions: one answer per implementor, or many. The next chapter puts traits and composition together and works through what happens to an inheritance hierarchy when it is rewritten in a language that has neither base classes nor a way to miss them.

Questions to think through

A generic function used with fifteen types produces fifteen copies. Find a generic or template function in a codebase you know that is called with many types. Would you rather have the speed or the compile time, and how would you find out which you are getting?

Clone is not object safe, so Box<dyn Trait> cannot be cloned in general. Reason out why: what would the vtable entry for clone have to return, and why can the caller not handle it?

Pick an interface you have defined with a generic method. Could it be a trait object in Rust? If not, what would you change about it, and would the change make it better or only make it legal?