Rust's Enum Dispatch control flow for Static Polymorphism

Achieving static polymorphism in Rust without the cost of vtable indirection using the Enum Dispatch control flow

Introduction

I was going to title this one something like "Ad-hoc Static Polymorphism via Exhaustive Matching" but I thought that would be too pedantic.

Either way, I don't have much of an intro this time so let's just dig in.

The ‘vtable’, Dynamic Dispatch, and Monomorphism

The Rust ‘vtable’ (short for “virtual table”) is a sort of cheat sheet that directs the CPU on how to handle a compile-time unknown type at runtime. The vtable contains function pointers to the actual implementations for that specific concrete type. So instead of knowing the exact type at compile time, Rust looks up the function pointer in the vtable at runtime. Basically, it allows Rust to handle unknowns, and is the core of Dynamic Dispatch, ie when using dyn Trait or Box<dyn Trait>.

The issue is that Dynamic Dispatch has an obvious cost in the process of looking up function pointers at runtime, a process called “vtable indirection”. Essentially, you pay the price of not knowning for the convenience of not caring.

Monomorphism means “one form” and it is a type-theory term that represents concrete types where all type parameters are resolved (ie, no unknowns). Static Polymorphism on the other hand is a language design term. The “static” portion refers to resolution at compile time, and the “polymorphism” portion just means that it can handle multiple types. The important thing to understand is that Rust uses monomorphism to achieve static polymorphism. In other words, static polymorphism is the identification of the multiple types, while monomorphization is the proces by which those types were identified.

Summary:

▪️ fn do_work(val: &dyn SomeTrait) : Dynamic Dispatch - uses the vtable, resolves at runtime

▪️ fn do_work<T: SomeTrait>(val: T) : Monomorphism - no vtable, resolves at compile time

Enum Dispatch

When you are working with a set of types that are varied but known, ie a “closed set” of concrete types that are known at compile time, it is possible to avoid the vtable indirection cost by replacing the Dynamic Dispatch pattern with the Enum Dispatch pattern. In other words, the dyn SomeTrait call is replaced by an enum with variants of concrete types.

There are two main benefits to using Enum Dispatch over Dynamic Dispatch:

▪️ Faster : The dispatch cost of enum branch prediction is ~0.3ns, compared to vtable indirection of ~2.0ns

▪️ Memory : No heap allocation (inline), compared to using the heap-allocated Box<dyn SomeTrait>

Talk is cheap, show me the code

For this exercise we will be running a Pet Rescue Shelter (no-kill, obviously). The shelter will house different types of pets, all of which we will know ahead of time. So because this is a situation where we are working with a closed set of concrete types that are known at compile time, we can use the Enum Dispatch method to save on dispatch cost and memory allocation.

The first thing we want to do is define our Pet Types. To keep this example brief (and to save on boilerplate), our shelter will only contain cats and dogs.

Yours might have a hampster? Maybe birds? Doesn’t matter.

struct Cat {
    name: &'static str,
    age: u8,
}

struct Dog {
    breed: &'static str,
    name: &'static str,
    age: u8,
}
        

We want to establish polymorphism across our types, so we need to create at least one method that will be shared across them. For this example, let's create a .display() method that will capture the different attributes (fields) of each type. We do this by creating the PetHandler trait with a .display() method, and then implement it on our Cat and Dog types.

trait PetHandler {
    fn display(&self) -> String;
}

impl PetHandler for Cat {
    fn display(&self) -> String {
        format!("{} is a kitty who is {} years old", self.name, self.age)
    }
}

impl PetHandler for Dog {
    fn display(&self) -> String {
        format!("{} is a {} puppy who is {} years old", self.name, self.breed, self.age)
    }
}
        

Now let's create the Enum Dispatch functionality. This is where we achieve semantic interoperability between the new Pet enum and the previously-defined PetHandler trait, by defining the .display() method in the implementation as a match arm process.

enum Pet {
    Cat(Cat),
    Dog(Dog),
}
use crate::Pet::*;

impl Pet {
    fn display(&self) -> String {
        match self {
            Self::Cat(cat) => cat.display(),
            Self::Dog(dog) => dog.display(),
        }
    }
}
        

Finally, let's define the Shelter which contains our pets. It houses our Pets in a vector, and will have one associated function, .new(), and two methods: .add_pet() which allows us to add a Pet to the shelter, and .show_pets() which uses the .display() method from above to list all the pets in the Shelter.

struct Shelter {
    pets: Vec
}

impl Shelter {
    fn new() -> Self {
        Self { pets: Vec::new() }
    }

    fn add_pet(&mut self, pet: Pet) {
        self.pets.push(pet);
    }

    fn show_pets(&self) {
        println!("------------- Our Current Pets -------------");
        for pet in &self.pets {
            print!("- ");
            println!("{}", pet.display());
        }
    }
}
        

With all that in place, we are all set!

We can now define a Shelter, define some Pets, add them to the Shelter, and use .show_pets() to see them.

fn main() {
    // Init a `Shelter`:
    let mut shelter: Shelter = Shelter::new();

    // Define some pets:
    let milo: Pet = Cat( Cat { name: "Milo", age: 10 } );
    let fido: Pet = Dog( Dog { breed: "corgy", name: "Fido", age: 15 } );

    // Add them to shelter:
    shelter.add_pet(milo);
    shelter.add_pet(fido);

    // List:
    shelter.show_pets();
    // ------------- Our Current Pets -------------
    // - Milo is a kitty who is 10 years old
    // - Fido is a corgy puppy who is 15 years old
}
        

Denounement

That's basically it for this short article. As long as you are working with a closed set of types, the Enum Dispatch pattern is a great way to save on exec time and heap allocation overhead.

But keep in mind, the Dynamic Dispatch pattern is unescapable if your project will ever encounter any new types in the future.

As always, thank you very much for reading!