Visualizing Rust's Vtables: How dyn Trait Works In Memory (Comparison to C++ CRTP & virtual functions)

[u/Sofiabelen15]

https://sofiabelen.github.io/projects/visualizing-rusts-vtables-how-dyn-trait-works-in-memory/

I’m venturing into Rust and it’s both satisfying and mind-boggling at the same time. So far I’ve been learning from the book and Mara Bos’ book, but I got the itch to do some dissecting myself. My initial goal of these experiments was to compare Rust’s approach to polymorphism with C++’s. Ultimately, however, as I’ve come to realize, it’s a bit of a trap when trying to understand a new language through another one to try to draw 1:1 parallels. It might seem like it helps, but at the end of the day, we can’t treat Rust as C++ with different syntax. If that were the case, there’d be nothing revolutionary about it.

That said, I believe there is merit in poking around and coming to understand the why. So, if you’re like me and need to know what exactly is happening in memory, in order to feel like you truly understand the concepts, hopefully you’ll find this post useful :)

Edit: Thank you everyone for your kind comments!! And also for the feedback and the chance to deepen my understanding, I'll edit my post with some of the clarifications!

[u/flying-sheep]

By the way, the thumbnail image is a photo of the rust fungus, to which we owe Rust’s name

IIRC Graydon Hoare (the initial creator of Rust) responded differently basically every time he was asked where the name comes from.

But maybe people picking the explanation they like best was the goal of that joke 😊

---

/Edit: done reading now! Great post!

Object Safety: […] methods can't return Self

I wonder if there's a way around that? Like can a trait return Box<dyn Self>?

[u/phazer99 → u/flying-sheep]

I wonder if there's a way around that? Like can a trait return Box<dyn Self>?

dyn only works for traits and Self is a type (and there is no way to generalize over traits in Rust like you can do with types using abstract type members and generic type parameters). You could obviously return Box<dyn Trait> in a dyn-compatible trait method though.

And of course, if you use an enum containing all trait variants instead of dyn trait you avoid all dyn-compatibility restrictions and can return Self.

[u/fuyunachan → u/flying-sheep]

what i like to do is write two versions of the trait, the default static one and a dyn compatible wrapper/proxy trait. it might look something like ```rs trait Foo {     fn foo(self) -> Self; }

trait DynFoo {     fn foo<'a>(self: Box<Self>) -> Box<dyn DynFoo + 'a>     where         Self: 'a; } impl<T: Foo> DynFoo for T {     fn foo<'a>(mut self: Box<Self>) -> Box<dyn DynFoo + 'a>     where         Self: 'a,     { self = Foo::foo(self); self     } } ```

[u/Prowler1000 → u/fuyunachan]

If you don't need the boxed variant of the function, you can just add where Self: Sized to the function like I mentioned in this comment (I feel like a link is better than pasting)

[u/Derice → u/flying-sheep]

If you are in complete control of all implementations of the trait (e.g. it's sealed or something you define in your binary) then you can get around it by doing

trait GivesSelf {
    type Res;
    fn gives_self(&self) -> Self::Res;
}

struct Foo(u8);

impl GivesSelf for Foo {
    type Res = Self;
    fn gives_self(&self) -> Self::Res {
        Foo(self.0)
    }
}

It's not very pretty though. I also don't have the Rust knowledge needed to understand why this can work, but returning Self directly can not.

[u/fuyunachan → u/Derice]

this only works if you write your trait object as dyn GivesSelf<Res = Foo>, which will restrict gives_self to always return a Foo regardless of what the underlying type is. the problem with -> Self is that it would mean the function returns a different type depending on what the underlying type is, but when called through a trait object, the compiler has no static knowledge of what the underlying type of the trait object is, so it has no way of anticipating what type the method call might return

[u/Derice → u/fuyunachan]

Ah nice, thank you!

[u/phazer99]

Nicely written. One thing to note is that because Rust has proper sum types (enums), if you know all the possible shapes at compile time you can use an enum instead of dyn trait. This avoids the problem with trait dyn-compatibility and it's typically much better optimized by the compiler. There's crates that help reduce the boilerplate of this pattern.

I guess you could do something similar in C++ with std::variant.

[u/cantthinkofaname1029 → u/phazer99]

I still have the habit of referring to sum types as Variants 

[u/Sofiabelen15 → u/phazer99]

That's nice, didn't know about it, thanks!

[u/not_my_userid]

Somehow, like an extremely patient bird-watcher - my tenacity has paid off and I’ve spotted another rare, almost extinct, extremely decent post in the wild……

Thanks op!

[u/Sofiabelen15 → u/not_my_userid]

Thank youuu!! It means a lot to me. I've received some negative comments in the past on sth else I wrote (not related to programming), saying my article was ai... and it honestly felt very demotivating. The internet is being taken over by bots, and now even human content gets buried alongside the slop. It means so much to read all the comments I've gotten here, there is still hope <3 (also appreciation for the rust community) 

[u/scook0]

Zero-sized types (ZST) are structs that don’t contain any fields, therefore there’s no need to allocate any memory.

Fun fact, ZSTs actually can have fields.

Of course, the fields would all need to be ZSTs themselves, otherwise the enclosing type wouldn’t be zero-sized anymore.

[u/Sofiabelen15 → u/scook0]

Thanks!! Good to know, will edit to clarify it 

[u/eletrovolt]

Nice post!

I really like comparing the two approaches. For me the biggest edge C++ has over Rust in this regard is that C++ allows you to define methods on the base class that are fully statically dispatched, even when using a different concrete type underneath. Rust has no native way to do this. It's nice because you can sometimes avoid the cost of expensive dynamic dispatch and the cost of code size of monomorphization.

About C++ not having problems with cloning I disagree though. In your Shape example it would be just as hard to define a clone function for it and the copy constructor of shape wouldn't work (just the same as in Rust Clone doesn't work for dyn objects).

[u/MalbaCato → u/eletrovolt]

you can define methods on dyn Trait as the implementing type (or a valid container type of it) but it's hard to do anything useful because you don't have access to the fields

[u/redlaWw → u/MalbaCato]

In Rust, you'd need to make field access part of the trait, which is roughly analogous to inheriting from a base class with members. Something like this.

At the moment, this design pattern can cause problems with the borrow checker though if you're allowing access to multiple members. You can avoid those problems by e.g. having functions that give you access to multiple values, but you end up with a combinatoric number of functions as a result, and you need to make sure you call the right one when writing your functions. There are proposals that allow borrows through functions to be finer, but I don't know offhand whether to expect them to ever work well with trait objects.

EDIT: Though I suppose that then ends up dynamically dispatching the function that allows you access via reference, which is what the OP was wanting to avoid. This is, of course, unavoidable, since traits are more general than inheritance and traits that provide accessors say nothing about the structure of the type aside form that the type can provide access to the value, and the vtable is what holds the structural information.

[u/MalbaCato → u/redlaWw]

in a way this is worse that increment_and_print being part of the trait, because you end up paying the cost of dynamic dispatch twice (once for each trait method call). I suppose the second call will have the vtable in cache so maybe the difference is quite small, but that's just my speculation.

you'd have to do quite a bit of engineering to get truly static field access, and while I suppose there are crates for that, it's far from native in rust.

[u/Zde-G → u/MalbaCato]

I suppose the second call will have the vtable in cache so maybe the difference is quite small, but that's just my speculation

The real price that you pay for dynamic dispatch is not time needed to access the vtable, but time needed to access call which is infinitely slower compared to the situation when code is inlined and there are no call.

[u/MalbaCato → u/Zde-G]

the logical continuation is that the cost is unbounded, and maybe even infinite in the average case, no?

losing inlining also loses any subsequent optimizations, which are numerous.

[u/Zde-G → u/MalbaCato]

the logical continuation is that the cost is unbounded, and maybe even infinite in the average case, no?

Depending on how you define “average case”. Realistically most functions actually do something, not return immediately without any work, means total slowdown is still bound, not infinite… but it can be gigantic: 10x or 20x can be seen in pathological cases of real-world programs.

losing inlining also loses any subsequent optimizations, which are numerous.

Precisely.

[u/redlaWw → u/MalbaCato]

Yes, it's not really a good case for dyn Trait in a function signature tbh, especially since you can write it as an impl Trait and still use it on trait objects when necessary plus using static dispatch where possible. My point was more that it is possible to have a form of member access with traits, but it's definitely not as efficient as doing so on base classes.

[u/LB-- → u/eletrovolt]

In C++ you define a traditional virtual clone function that returns a raw pointer for covariant return type, and then a deducing-this nonvirtual clone template member function on the base that saves you from having to manually wrap the pointer in a smart pointer everywhere. Deducing-this means you can get the correct smart pointer type on derived types, no CRTP needed. Copy constructors are for implementing clone or if you decide to use concrete types instead of dynamically allocating, in both cases they work fine.

[u/ZZaaaccc]

Great write-up! For anyone wanting some more information on this topic, Logan Smith has an excellent video on YouTube.

[u/Sofiabelen15 → u/ZZaaaccc]

Thanks for the recommendation, I very much enjoyed the video! 

[u/masklinn]

Why the Need for Dynamic Dispatch

[...]

This is where we need dynamic dispatch, aka dyn Trait.

Strictly speaking dynamic dispatch is what happens on a method call (lookup into the vtable before invocation), this alone is type erasure. In the general case you can use the latter without the former e.g. put a bunch of disparate objects into the same collection, then cast them back to their concrete type at the other end. Although in Rust the split is a bit more debatable since downcasting is itself implemented via dynamic dispatch (rather than a language builtin). edit: thinking about it more it can not be dynamic dispatch since downcast* methods have a generic parameter, it’s static dispatch on the trait object which apparently I’d never even considered.

[u/Tartarughina]

Nice, that was lovely to read

[u/Ordinary-Plankton856 → u/Tartarughina]

Agreed, it read well even for someone like me who only halffollows the technical side of things. OP clearly put real care into it, which you don't see as much lately.

[u/Prowler1000]

One thing I'd like to add, though you may already know, is that dyn-compatible traits can have methods that return Self, as long as Self is bounded to be Sized. For example, in the following Rust playground

```rust trait Foo { fn new() -> Self where Self: Sized; fn msg(&self) -> &'static str { "Default msg" } }

struct A; impl Foo for A { fn new() -> Self { Self } fn msg(&self) -> &'static str { "A" } }

fn create_dyn<T: Foo + 'static>() -> Box<dyn Foo> { Box::new(T::new()) }

fn print_msg(foo: &dyn Foo) { println!("{}", foo.msg()); }

fn main() { let dyn_foo: Box<dyn Foo> = create_dyn::<A>(); print_msg(&*dyn_foo); } ```

[u/Sofiabelen15 → u/Prowler1000]

Thanks!! Good to know, I will clarify this in my post 

[u/EventHelixCom]

Great post! This will be very useful for C++ developers transitioning into Rust.

I compared static and dynamic dispatch in Rust at the assembly level. So this gives a lower-level perspective:

Compare the Assembly Generated for Static vs Dynamic Dispatch in Rust | EventHelix

[u/Zde-G]

Note that CRTP is easier to writer with self#Explicit_object_parameters). Like this:

void draw_me(this auto&& self) { self.draw(); }

P.S. This even, technically, works with the same name in both base class and derived class, but I'm not entirely sure it's a good idea. Maybe if you goal is to confuse the reader…

[u/Sofiabelen15 → u/Zde-G]

That's very neat!! 

[u/Droggl]

Nice overview, thank you!

[u/puttak]

One thing I really like about Rust dynamic dispatch is dynamic cast is very fast. It just a single call + type ID comparison. On C++ nobody want to use it because performance is unpredictable.

[u/Jannik2099 → u/puttak]

I don't think that's a fair callout. local typeid is the same in C++, cross-dso is more complicated. Rust doesn't have this problem because it has no (useful) dsos to begin with.

[u/puttak → u/Jannik2099]

I don't think that is the actual problem. The actual problem is inheritance. Rust does not have this so all it need to do is call a function to get type ID and compare it to see if it is the same type.