Runtime Static Dispatch via Rust's Sum Types

Static dispatch (also called early binding) and dynamic dispatch (late binding, runtime dispatch, virtual method call) are the ways to resolve member function (methods) bindings. In other words they are ways of choosing which implementation of a method/function to use.

In static dispatch, this is done statically (at compile time). In dynamic dispatch, the resolution happens at runtime. The former is often the default in compiled language. The latter is often used when doing some form of polymorphism, for example when multiple types have their own implementation of the "same" method (interfaces in many languages, traits in rust).

Dynamic Dispatch

without knowing the concrete type of UnknownInstanceOfInterface at compile time, the compiler can replace this with

This works if there's a guarantee that all implementators of the interface store the same indexes for a the same methods.

In C++, dynamic dispatch is in play when a method is declared virtual. When that happens, instance of objects that have virtual methods have an extra hidden field which is a pointer to the vtable. This extra member affects the layout of the type. A typical call site might look something like:

This is quite a bit of pointer chasing. They also use strategies such as name mangling to help support late binding, but that's outside of the scope of this post.

Rust

That way rustc is happy because the size of a Box pointer is known at compile time. The big contrast between rust and cpp is that in rust a trait object (dyn trait) is an entirely new type. Instead of injecting a new member to the instance of a type like in cpp, trait objects are fat pointers.

The fat pointer (dyn trait/trait object) contains two pointers: one to the vtable of the object, and one to the data of the object. The vtable ptr is therefore decoupled from the type itself. This also has a very powerful side effect: since the vtable is physically separated from the object's instance, the interfaces do not have to be known at compile time. The object layout is not modified so there is no absolute need to know what interface is implemented by what type at compile time. This allows implementing interfaces on multiple pre-existing types.

Enum Dispatch: Static and Dynamic?

There is no magic: if we want to delay resolving the mapping between a method and a type to runtime we need a layer of indirection. In the case of dynamic dispatch, this is done via vtable, which means that we are dealing with non-concrete types.

Using sum types, it's possible in Rust to resolve everything from the compilers point of view at compile time (static dispatch) while not knowing the concrete type. This is particularily useful when needing to store a collection of types where we do not know the concrete type at runtime, we would typically need to store a vector of boxed trait objects (Boxed dyn traits).

Instead, what we can do is store implementators of a trait inside an enum, have the collection hold instances of that enum and do the dispatching in that enum:

// Sharing behavior (polymorphism), via traits.
trait Traitor {
    fn blah(&self) -> ();
}

// first implementator
struct A {}
impl Traitor for A {
    fn blah(&self) -> () {
        println!("Hello From A");
    }
}

// second implementator
struct B {}
impl Traitor for B {
    fn blah(&self) -> () {
        println!("Hello From B");
    }
}

// Enum used for the enum dispatch strategy
enum Traitors {
    AWrapper(A),
    BWrapper(B),
}
impl Traitor for Traitors {
    // Dispatches blah() to the "real" underlying type
    fn blah(&self) -> () {
        match self {
            self::Traitors::AWrapper(actual_a) => actual_a.blah(),
            self::Traitors::BWrapper(actual_b) => actual_b.blah(),
        }
    }
}
            

We can then dynamically create instances of the enum and have collections of them. Since rust enums are implemented as tagged unions, it stores the the value and the discriminant (which tells us the current variant). A downside to this approach is that the size of our enum's will have the overhead of the discriminant (a u8 if there are less than 256 variants) + the required padding for aligment. It can also create some bloat when the variants have widely different sizes (in our previous example, if A has lots of members and B is a very small struct, we pay a penality of sizeof(A)-sizeof(B) (rounded to aligment) when B is the variant.

Now the big advantage is that we do not have to deal with dynamic dispatch anymore: the type is selected at runtime but we know at compile time that we are calling enum.blah(); in the example above, and not instanceOfA.blah(); or instanceOfB.blah();. The dispatching happens inside enum.blah(). This is effectively a conversion from using dynamic dispatch to only relying on concrete types. This makes it much easier to debug and understand.

I'm not advocating for this technique at all times: when there are too many implementators of a trait or when the trait has too many methods it becomes hard to manage, and at this point it might be worth it to simply default to trait objects via dyn traits.

Another disadvantage of this strategy is that if you are designing a library you might want to give the users the possiblity to extend your type, possibly via the newtype pattern. In our case this is hard to do because everything goes through an enum, we could wrap that enum into another enum, but then we need to implement the trait methods/dispatching via that new enum again, creating more indirection. A sane way to allow for some flexibilty while keeping things simple is to have an enum variant that is specifically made for this. The following implementation showcases this strategy:

// ...
// Enum used for the enum dispatch strategy
enum Traitors {
    AWrapper(A),
    BWrapper(B),
    // This allows extension: anything that implements Traitor is valid!
    Placeholder(Box<dyn Traitor>),
}
impl Traitor for Traitors {
    // Dispatches blah() to the "real" underlying type
    fn blah(&self) -> () {
        match self {
            self::Traitors::AWrapper(actual_a) => actual_a.blah(),
            self::Traitors::BWrapper(actual_b) => actual_b.blah(),
            // Consumer who extends the Traitors enum does not need to change anything!
            self::Traitors::Placeholder(who_knows) => who_knows.blah(), 
        }
    }
}
            

In this article we took a look at static vs dynamic dispatch, covered some virtual table basics and looked at what c++ does in the simple case. More importantly we investigated a way to leverage rust's tagged unions to avoid dynamic dispatch. This is a design decision with tradeoffs, just like all design decisons, and is not always better than relying on dynamic dispatch via trait objects.

Uploaded 08-10-2024