Item 12: Understand the trade-offs between generics and trait objects

Item 2 described the use of traits to encapsulate behavior in the type system, as a collection of related methods, and observed that there are two ways to make use of traits: as trait bounds for generics or in trait objects. This Item explores the trade-offs between these two possibilities.

As a running example, consider a trait that covers functionality for displaying graphical objects:

#[derive(Debug, Copy, Clone)]
pub struct Point {
    x: i64,
    y: i64,
}

#[derive(Debug, Copy, Clone)]
pub struct Bounds {
    top_left: Point,
    bottom_right: Point,
}

/// Calculate the overlap between two rectangles, or `None` if there is no
/// overlap.
fn overlap(a: Bounds, b: Bounds) -> Option<Bounds> {
    // ...
}

/// Trait for objects that can be drawn graphically.
pub trait Draw {
    /// Return the bounding rectangle that encompasses the object.
    fn bounds(&self) -> Bounds;

    // ...
}

Generics

Rust's generics are roughly equivalent to C++'s templates: they allow the programmer to write code that works for some arbitrary type T, and specific uses of the generic code are generated at compile time—a process known as monomorphization in Rust, and template instantiation in C++. Unlike C++, Rust explicitly encodes the expectations for the type T in the type system, in the form of trait bounds for the generic.

For the example, a generic function that uses the trait's bounds() method has an explicit Draw trait bound:

/// Indicate whether an object is on-screen.
pub fn on_screen<T>(draw: &T) -> bool
where
    T: Draw,
{
    overlap(SCREEN_BOUNDS, draw.bounds()).is_some()
}

This can also be written more compactly by putting the trait bound after the generic parameter:

pub fn on_screen<T: Draw>(draw: &T) -> bool {
    overlap(SCREEN_BOUNDS, draw.bounds()).is_some()
}

or by using impl Trait as the type of the argument:¹

pub fn on_screen(draw: &impl Draw) -> bool {
    overlap(SCREEN_BOUNDS, draw.bounds()).is_some()
}

If a type implements the trait:

#[derive(Clone)] // no `Debug`
struct Square {
    top_left: Point,
    size: i64,
}

impl Draw for Square {
    fn bounds(&self) -> Bounds {
        Bounds {
            top_left: self.top_left,
            bottom_right: Point {
                x: self.top_left.x + self.size,
                y: self.top_left.y + self.size,
            },
        }
    }
}

then instances of that type can be passed to the generic function, monomorphizing it to produce code that's specific to one particular type:

let square = Square {
    top_left: Point { x: 1, y: 2 },
    size: 2,
};
// Calls `on_screen::<Square>(&Square) -> bool`
let visible = on_screen(&square);

If the same generic function is used with a different type that implements the relevant trait bound:

#[derive(Clone, Debug)]
struct Circle {
    center: Point,
    radius: i64,
}

impl Draw for Circle {
    fn bounds(&self) -> Bounds {
        // ...
    }
}

then different monomorphized code is used:

let circle = Circle {
    center: Point { x: 3, y: 4 },
    radius: 1,
};
// Calls `on_screen::<Circle>(&Circle) -> bool`
let visible = on_screen(&circle);

In other words, the programmer writes a single generic function, but the compiler outputs a different monomorphized version of that function for every different type that the function is invoked with.

Trait Objects

In comparison, trait objects are fat pointers (Item 8) that combine a pointer to the underlying concrete item with a pointer to a vtable that in turn holds function pointers for all of the trait implementation's methods, as depicted in Figure 2-1:

let square = Square {
    top_left: Point { x: 1, y: 2 },
    size: 2,
};
let draw: &dyn Draw = □

This means that a function that accepts a trait object doesn't need to be generic and doesn't need monomorphization: the programmer writes a function using trait objects, and the compiler outputs only a single version of that function, which can accept trait objects that come from multiple input types:

/// Indicate whether an object is on-screen.
pub fn on_screen(draw: &dyn Draw) -> bool {
    overlap(SCREEN_BOUNDS, draw.bounds()).is_some()
}

// Calls `on_screen(&dyn Draw) -> bool`.
let visible = on_screen(&square);
// Also calls `on_screen(&dyn Draw) -> bool`.
let visible = on_screen(&circle);

Basic Comparisons

These basic facts already allow some immediate comparisons between the two possibilities:

• Generics are likely to lead to bigger code sizes, because the compiler generates a fresh copy (on_screen::<T>(&T)) of the code for every type T that uses the generic version of the on_screen function. In contrast, the trait object version (on_screen(&dyn T)) of the function needs only a single instance.
• Invoking a trait method from a generic will generally be ever-so-slightly faster than invoking it from code that uses a trait object, because the latter needs to perform two dereferences to find the location of the code (trait object to vtable, vtable to implementation location).
• Compile times for generics are likely to be longer, as the compiler is building more code and the linker has more work to do to fold duplicates.

In most situations, these aren't significant differences—you should use optimization-related concerns as a primary decision driver only if you've measured the impact and found that it has a genuine effect (a speed bottleneck or a problematic occupancy increase).

A more significant difference is that generic trait bounds can be used to conditionally make different functionality available, depending on whether the type parameter implements multiple traits:

// The `area` function is available for all containers holding things
// that implement `Draw`.
fn area<T>(draw: &T) -> i64
where
    T: Draw,
{
    let bounds = draw.bounds();
    (bounds.bottom_right.x - bounds.top_left.x)
        * (bounds.bottom_right.y - bounds.top_left.y)
}

// The `show` method is available only if `Debug` is also implemented.
fn show<T>(draw: &T)
where
    T: Debug + Draw,
{
    println!("{:?} has bounds {:?}", draw, draw.bounds());
}

let square = Square {
    top_left: Point { x: 1, y: 2 },
    size: 2,
};
let circle = Circle {
    center: Point { x: 3, y: 4 },
    radius: 1,
};

// Both `Square` and `Circle` implement `Draw`.
println!("area(square) = {}", area(&square));
println!("area(circle) = {}", area(&circle));

// `Circle` implements `Debug`.
show(&circle);

// `Square` does not implement `Debug`, so this wouldn't compile:
// show(&square);

A trait object encodes the implementation vtable only for a single trait, so doing something equivalent is much more awkward. For example, a combination DebugDraw trait could be defined for the show() case, together with a blanket implementation to make life easier:

trait DebugDraw: Debug + Draw {}

/// Blanket implementation applies whenever the individual traits
/// are implemented.
impl<T: Debug + Draw> DebugDraw for T {}

However, if there are multiple combinations of distinct traits, it's clear that the combinatorics of this approach rapidly become unwieldy.

More Trait Bounds

In addition to using trait bounds to restrict what type parameters are acceptable for a generic function, you can also apply them to trait definitions themselves:

/// Anything that implements `Shape` must also implement `Draw`.
trait Shape: Draw {
    /// Render that portion of the shape that falls within `bounds`.
    fn render_in(&self, bounds: Bounds);

    /// Render the shape.
    fn render(&self) {
        // Default implementation renders that portion of the shape
        // that falls within the screen area.
        if let Some(visible) = overlap(SCREEN_BOUNDS, self.bounds()) {
            self.render_in(visible);
        }
    }
}

In this example, the render() method's default implementation (Item 13) makes use of the trait bound, relying on the availability of the bounds() method from Draw.

Programmers coming from object-oriented languages often confuse trait bounds with inheritance, under the mistaken impression that a trait bound like this means that a Shape is-a Draw. That's not the case: the relationship between the two types is better expressed as Shape also-implements Draw.

Under the covers, trait objects for traits that have trait bounds:

let square = Square {
    top_left: Point { x: 1, y: 2 },
    size: 2,
};
let draw: &dyn Draw = □
let shape: &dyn Shape = □

have a single combined vtable that includes the methods of the top-level trait, plus the methods of all of the trait bounds. This is shown in Figure 2-2: the vtable for Shape includes the bounds method from the Draw trait, as well as the two methods from the Shape trait itself.

At the time of writing (and as of Rust 1.70), this means that there is no way to "upcast" from Shape to Draw, because the (pure) Draw vtable can't be recovered at runtime; there is no way to convert between related trait objects, which in turn means there is no Liskov substitution. However, this is likely to change in later versions of Rust—see Item 19 for more on this.

Repeating the same point in different words, a method that accepts a Shape trait object has the following characteristics:

• It can make use of methods from Draw (because Shape also-implements Draw, and because the relevant function pointers are present in the Shape vtable).
• It cannot (yet) pass the trait object onto another method that expects a Draw trait object (because Shape is-not Draw, and because the Draw vtable isn't available).

In contrast, a generic method that accepts items that implement Shape has these characteristics:

• It can use methods from Draw.
• It can pass the item on to another generic method that has a Draw trait bound, because the trait bound is monomorphized at compile time to use the Draw methods of the concrete type.

Trait Object Safety

Another restriction on trait objects is the requirement for object safety: only traits that comply with the following two rules can be used as trait objects:

• The trait's methods must not be generic.
• The trait's methods must not involve a type that includes Self, except for the receiver (the object on which the method is invoked).

The first restriction is easy to understand: a generic method f is really an infinite set of methods, potentially encompassing f::<i16>, f::<i32>, f::<i64>, f::<u8>, etc. The trait object's vtable, on the other hand, is very much a finite collection of function pointers, and so it's not possible to fit the infinite set of monomorphized implementations into it.

The second restriction is a little bit more subtle but tends to be the restriction that's hit more often in practice—traits that impose Copy or Clone trait bounds (Item 10) immediately fall under this rule, because they return Self. To see why it's disallowed, consider code that has a trait object in its hands; what happens if that code calls (say) let y = x.clone()? The calling code needs to reserve enough space for y on the stack, but it has no idea of the size of y because Self is an arbitrary type. As a result, return types that mention Self lead to a trait that is not object safe.²

There is an exception to this second restriction. A method returning some Self-related type does not affect object safety if Self comes with an explicit restriction to types whose size is known at compile time, indicated by the Sized marker trait as a trait bound:

/// A `Stamp` can be copied and drawn multiple times.
trait Stamp: Draw {
    fn make_copy(&self) -> Self
    where
        Self: Sized;
}

let square = Square {
    top_left: Point { x: 1, y: 2 },
    size: 2,
};

// `Square` implements `Stamp`, so it can call `make_copy()`.
let copy = square.make_copy();

// Because the `Self`-returning method has a `Sized` trait bound,
// creating a `Stamp` trait object is possible.
let stamp: &dyn Stamp = □

This trait bound means that the method can't be used with trait objects anyway, because trait objects refer to something that's of unknown size (dyn Trait), and so the method is irrelevant for object safety:

// However, the method can't be invoked via a trait object.
let copy = stamp.make_copy();

error: the `make_copy` method cannot be invoked on a trait object
   --> src/main.rs:397:22
    |
353 |         Self: Sized;
    |               ----- this has a `Sized` requirement
...
397 |     let copy = stamp.make_copy();
    |                      ^^^^^^^^^

Trade-Offs

The balance of factors so far suggests that you should prefer generics to trait objects, but there are situations where trait objects are the right tool for the job.

The first is a practical consideration: if generated code size or compilation time is a concern, then trait objects will perform better (as described earlier in this Item).

A more theoretical aspect that leads toward trait objects is that they fundamentally involve type erasure: information about the concrete type is lost in the conversion to a trait object. This can be a downside (see Item 19), but it can also be useful because it allows for collections of heterogeneous objects—because the code just relies on the methods of the trait, it can invoke and combine the methods of items that have different concrete types.

The traditional OO example of rendering a list of shapes is one example of this: the same render() method could be used for squares, circles, ellipses, and stars in the same loop:

let shapes: Vec<&dyn Shape> = vec![&square, &circle];
for shape in shapes {
    shape.render()
}

A much more obscure potential advantage for trait objects is when the available types are not known at compile time. If new code is dynamically loaded at runtime (e.g., via dlopen(3)), then items that implement traits in the new code can be invoked only via a trait object, because there's no source code to monomorphize over.