Rust: Trait objects vs generics

Introduction

Abstracting concepts to avoid code duplication is something common.
Rust provides both generics and trait objects to achieve this, but if you look carefully they don't address the exact same problem, and they have different consequences on performance.

In order to compare them, we will consider a simple example : a list.
Let's start with generics.

Generics

struct MyList<T> {
    contents: Vec<T>,
}

fn main() {
    let a = MyList {
        contents: vec![1., 2., 3.],
    };

    let b = MyList {
        contents: vec!["abc".to_owned(), "def".to_owned()],
    };

    println!("{:?}", a.contents);
    println!("{:?}", b.contents);
}

Output:

[1.0, 2.0, 3.0]
["abc", "def"]

MyList is a simple struct containing a Vec whose elements are of type T.
This allows a to contain a Vec<f64> and b a Vec<String>.

Right, what if we try to mix f64 and String in the same list ?

struct MyList<T> {
    contents: Vec<T>,
}

fn main() {
    let not_working = MyList {
        contents: vec![1., "test".to_owned()],
    };

    println!("{:?}", not_working.contents);
}

Output:

error[E0308]: mismatched types
 --> src/main.rs:7:28
  |
7 |         contents: vec![1., "test".to_owned()],
  |                            ^^^^^^^^^^^^^^^^^ expected floating-point number, found `String`

Mismatched types ! To understand why, let's describe how generics are handled by the compiler.
When you use generics, the Rust compiler do something called "monomorphization". It simply means that the compiler looks at all the places generic code is called, and replace the generic type by the concrete ones.
In this example, after monomorphization, the first code example would look like this :

struct MyList_f32 {
    contents: Vec<f32>,
}

struct MyList_string {
    contents: Vec<String>,
}

fn main() {
    let a = MyList_f32 {
        contents: vec![1., 2., 3.],
    };

    let b = MyList_string {
        contents: vec!["abc".to_owned(), "def".to_owned()],
    };

    println!("{:?}", a.contents);
    println!("{:?}", b.contents);
}

Now, how could the compiler generate a struct MyList_f32_string with contents type both Vec<f32> and Vec<String> in the same time ? As you can see, a Vec<T> can only contain elements of the same generic type.
On the other hand, generics have no impact on performance at runtime thanks to monomorphization.

Trait objects

Same idea as before, we want to store items in a list, but this time it contains non primitive types.

trait Entity {
    fn hello(&self) -> String;
}

struct Player {
    name: String,
    xp: usize,
}

impl Entity for Player {
    fn hello(&self) -> String {
        format!("I'm player {} with {} xp", self.name, self.xp)
    }
}

struct Bird {
    xp: usize,
}

impl Entity for Bird {
    fn hello(&self) -> String {
        format!("I'm a bird with {} xp", self.xp)
    }
}

struct MyList {
    contents: Vec<Box<dyn Entity>>,
}

fn main() {
    let world = MyList {
        contents: vec![
            Box::new(Player {
                name: "a".to_owned(),
                xp: 1000,
            }),
            Box::new(Bird { xp: 1 }),
            Box::new(Player {
                name: "b".to_owned(),
                xp: 0,
            }),
            Box::new(Bird { xp: 5 }),
        ],
    };

    for entity in &world.contents {
        println!("{}", entity.hello())
    }
}

Output:

I'm player a with 1000 xp
I'm a bird with 1 xp
I'm player b with 0 xp
I'm a bird with 5 xp

Here we use trait objects instead of generics: contents contains types that must implement the Entity trait (Vec<Box<dyn Entity>>). The compiler doesn't know which type will be used, but it knows it will implement that type.

But shouldn't the compiler complain because types in the list won't have the exact same size ? The list contains Box items, which is the size of a pointer: all items have the same size, everything's fine.

But trait objects have a cost : Rust can't apply monomorphization because it can't guess all types that might be used at runtime, so it keeps a table in which traits methods and concrete types implementations are linked.
In this example, during runtime, when entity.hello() is called for a Player, Rust looks up this table to call the corresponding Player::hello method, and not Bird::hello.

So dynamic dispatch have impacts on performance since it prevents monomorphization and adds a runtime cost due to dynamic dispatch, but sometimes we need it as in the example before.

Conclusion

Generics	Trait objects
refer to one generic type only	refer to any types implementing a specific trait
have no impact on runtime performance	prevent monomorphization and need dynamic dispatch