Two Ways To Do Dynamic Dispatch
ฝัง
- เผยแพร่เมื่อ 27 ก.ย. 2023
- Rust and C++ both have built-in (but different-flavored) support for dynamic dispatch, and both also let you open the hood and implement it the other way that's not built-in. In this one we look at both languages' approaches, weigh the pros and cons, and ultimately come away seeing that they're both the right choice in different situations (isn't that just so unsatisfying and typical).
Special guest appearances from vtables, vptrs, wide pointers, thunks, unsafe code, drop glue, virtual destructors, the Rule of Three, and me re-recording the live coding section like 5 times because I kept messing it up.
the Sean Parent talk - • Better Code: Runtime P...
godbolt to the demo - rust.godbolt.org/z/6YrK3vhGj
dyno - github.com/ldionne/dyno
NonNull - doc.rust-lang.org/stable/std/...
thunk - en.wikipedia.org/wiki/Thunk
std::function - en.cppreference.com/w/cpp/uti...
std::any - en.cppreference.com/w/cpp/uti...
I use the amazing Manim library for animating these videos, and I edit them with Blender and Audacity.
www.manim.community/
www.blender.org/
www.audacityteam.org/
Inside of you there are two wolves: One that cannot wait for new Logan Smith content, and one that knows it must wait for quality videos. The wolves are lovers. Woof woof.
feeling a lil goofy today arent you?
@@catus7787 You haven’t even SEEN goofy yet. I can and will bring a goof so goofy, so gooftacular… I will conjure a goof out of thin air-the likes of which the Logan Smith TH-cam channel has never seen. Empires will crumble under the weight of my goof. Today, tomorrow, and always, I goof. Just for you.
@@natashavartanian woof
I cant remember where did i hear/see this bs before about inside of you 2 wolfs none sense.
What.
You did, in fact, blow my mind with static promotion 🤯
Rust is the only piece of tech I've used extensively that I continue to be MORE impressed with over time. Usually the cupcake-phase wears off and you start disliking the warts found in all technology, but somehow after years of using Rust, I love it even more than the day I first picked it up. Fantastic video, thank you for starting a channel geared towards experienced engineers, there are very few of them.
How much value did you produce with RUST programming? I mean - software shipped, company earning money, etc?
@@dexio85 Rust has fixed my financial situation, rehabilitated me from multiple addictions, revived my dog and found me a partner.😊
Given that you probably spent most of "the day you picked it up" cursing the borrow checker, this isn't hugely surprising.... :)
Great, now I have an image of a cupcake with warts in my brain. Thanks a lot
Not gonna lie, I said out loud "wait, what?!!" when I saw you invoke &SpeakFunctions as 'static. That's certainly something new to me, and I love it (obviously, only for extremely specific circumstances).
C++: hold my variable templates
@@mariansalam In terms of C++ this actually feels kind of similar to Temporary Lifetime Extension. Where you bind a const reference to an rvalue, and instead of the usual undefined behavior for binding a reference to an object that is about to be destroyed, the compiler automatically extends the lifetime to the end of the scope.
auto main() -> int {
auto const& x = 2 + 3; // Compiler error if you remove const
std::printf("%d
", x); // Works just fine, no UB
}
It was just a &'static closure creation.
I code in C++ most of the time. I could do the first approach similarly in C++ (with similarly large amounts of boilerplate), but the &dyn trait type is the kind of compiler magic that I'm envious of from Rust: I wish we had dynamic dispatch in C++ that doesn't entangle the implementation and the trait/interface/concept.
@@anon_y_mousse That's compile-time/static, not runtime/dynamic dispatch. The video and my comment are about type erasure.
Watching the metrics of this channel since it started putting out Rust content has been fun.
You should upload a video on April 1st that explains how to do something in Rust the game, but explain it as if you are explaining some technical topic about Rust the programming language.
19:40 I like that last quote
class Inheritance { }
class Evil : Inheritance { }
Incredible stuff you are putting out.
For me, there isn't much new information, but you always manage to present a slightly different way of looking at things, which has so far always been valuable.
Your animations are spot on as well and make your videos an excellent resource that I'm eager to pass on.
Keep it up!
I wish Rust had better support for manually constructing vtables (ie. at runtime) that interfaces smoothly with dyn pointers. There are even places in standard library where they kinda had to awkwardly fudge it (looking at you std::task::RawWaker).
RawWaker exists because Rust has no concept of 'Owned Pointers' in core. There's no way to implement a Waker trait with a owned `wake(self)` function without assuming it's a Box or an Arc. (the Wake trait assumes it's an Arc)
IIRC, the `*dyn Trait` concept that was floated around before is intended to fix this concept. But there's alternative ideas like `&own T`
It was so cool seeing you implement vtables manually! It's something I have been curious about and always wanted to see someone do. Learned a lot too! Good stuff 😄
Very nice explanation, didn't realise this difference until now
This was great. I hope you make a follow-up video about downcasting(or maybe all types of casting) in Rust vs C++.
Explanation and visuals are absolute class.!!!
Man, I love your videos. I rarely ever _learn_ something new, but my understanding of the topic gets so much better.
I was also wondering the entire time if you'd mention anyhow, and I'm glad you did
Thank you for the video, please keep them coming.
amazing explanation, clear and to the juice of the discussion
This is a really fantastic video. Well made, well rehearsed, and well taught. Kudos from a seasoned Rustacean!
It's an excellent lecture overall. I liked it very much.
amazing details. thank you.
I am so glad youtube recommended me this!
Gotta say it's been a long time since I have been this excited about watching a new youtube video.
amazing content as always
Very well done! I’ve been hoping you would make a clear and insightful video into this topic. I find your videos to actually provide real explanations for how things work. So many videos out there fail to get to the meat of the matter. Thank you for doing what you do!
your explanations are SO clear and understandable!! I don't have any formal comp-sci education, the only strong-typed lang I've only worked in was Go for a year, and _all_ of this is making sense to me - your presentation skills are immense 🤩
There is one important difference you didn't talk about. In C++, if you are in an instance of a class running a function on itself, it can call a virtual function on itself, and derived classes will then be able to override that. You don't have to keep a special pointer that knows what type it is you are calling, and the "this" pointer can not be an all encompassing wide pointer just for this potential case right?
There are more cases of the same kind. Of course you can work around this in some ways, but somewhere you will get a hard time. If those are cases of actual value is another question entirely.
I think having the option for both solutions would be ideal.
Feels like making that kind of wide pointer and static v-table per type, would be not that hard with a template in C++. But it would not be quite as clean, and would be nice to have it built in.
This is an interesting point! I agree it'd be hard to have a class call a virtual method on itself using wide pointers, unless you somehow made the `this` pointer itself wide. I'll point out that calling a method on yourself dynamically is mostly an inheritance/OOP pattern, and based on my own observations at least, wide pointers tend to "slice the other way" and be used more compositionally rather than in situations with hierarchy/inheritance (a good example being Rust which doesn't have inheritance at all), so this problem doesn't really come up as one that needs to be solved.
I sketched out a C++ version of the Speak wide pointer, check it out: godbolt.org/z/zGxdsEsxd
It's not a nightmare to write, but it's definitely got sharp edges. Having a way to get the compiler to write it for you instead would be great.
@@_noisecode This is beautiful in a weird way! Also reminded me I need to refresh on the latest news on C++, concepts are an actual thing now? I just remember the endless discussions about whether it should be in the standard ;-)
@@_noisecodejust wanted to say tgat in c++ it's not realy 3 indirections because the offset is known at compile time so you can insert the addition of the offset to the call instruction and the compiler does that.
@@classone7101I know, but I’m counting the indirect jump into the code at the end as one of the indirections (for both C++ and Rust). In C++, it’s dereference object -> dereference vptr (at known offset) to get the function pointer -> jump into that code. So 3. Rust is 2 since it doesn’t need to first dereference the object to get the vptr.
That’s very interesting and well presented. Thanks for sharing.
This is some high-quality content. Chapeau to you, sir!
Thanks for letting me know about rvalue static promotion. It's a really cool think to know about!
amazing video!! thanks for sharing
Great video!
Thank you so much for this! I needed a workaround to a dyn trait object, because I wanted to implement some runtime dynamic casting back and forth between trait objects (between sub and super traits), but the compiler wasn't able to turn one trait object into another, in case they weren't sized. (They are in my case, but I was struggling to tell the compiler so)
That "&SpeakFunctions" static reference promotion tho, so good
i didn't understand most of the video, but it sounds very interesting! hope someday I will be able to rewatch it and comprehend it fully :)
This is such an awesome (and important) place to start; I have the same exact experience OFTEN when I'm exposed to brand new material I'm not comfortable with, and I truly believe it's a great way to "jumpstart" learning about a particular topic, even if you don't take much away on your first watch. It will plant seeds that will blossom later. Plus, after time passes and you later come back and find you understand things, it's an awesome, tangible marker of how much you've learned and grown in the meantime. Thanks so much for watching and I hope you really do come back sometime and share what now clicks that didn't the first time!
@@_noisecodeI am 48 and out of industry for few years. Have done a bit of programming in other languages but mostly in javascript. Learning rust now. I know I can do it. I find almost every rust video such as this one has very useful and overwhelming at the same time. I wonder if there is a single source of information that can provide some sort of insight into possible complexity of grammer that the rust language allows. I have read The Book and understood all of it. But the moment I come across videos such as this one I find them to be at an entirely different depths. Hmm. I guess the only way to keep going is just to keep going.
The main takeaway is that there are two places you can store a vtable pointer: 1. In every reference to an object, or 2. in the object itself.
This was a great video 🤯
The summary is: (1) to build a pointer to a vtable into the type itself, so that the type can't be used without vtable dispach on the flagged functions, as per C++, and (2) to build a wrapper around the type that uses a fat pointer to a vtable, as per Rust, so that the type can be used either way.
In C++ you have "final" keyword, which disables dynamic dispatch. I.e. if you mark Derived as final, all calls via ptr/ref to Derived will be static, but calls to Base will still be dynamic.
Then the optimizer comes in, but that's another story.
And you can handcraft fat pointers, there are few neat libraries for that, such as AnyAny.
now I know why I should use anyhow in rust
I thought I understood dyn but apparently I didn't. Awesome video, was interesting beginning to end.
Amazing!
Awesome video!
this notification made me pop my headphones in at work 🙏
9:15 learning rust and was hella struggling with why Box was required, this helped tonnes.
Very nice video. You helped me solve a tough problem I've been working on where I want to do type-erased dynamic dispatch to methods _of generic structs_. So rather than calling the implementation of a trait, I want to call the monomorphised implementation of a generic struct method dynamically. The core idea in the first part of this video to bind the type information into a thunk closure is what finally cracked that problem for me. `dyn Trait` is not enough for my use-case (it is fundamentally unsafe and even abstracting the methods I want to dispatch into a special-purpose trait does not work), but the hand-written unsafe approach you demonstrate in the beginning of the video works perfectly for what I want to do.
Sounds like a really interesting problem! I'm glad the video was helpful. Be careful with all that unsafe. ;)
"for... Reasons" 10:37
oh I love how inconspicuous that sounds and how deep it runs actually
No one should be able to use inheritance until they watch this video
Certainly, it is a nice video on the topic of indirection, but if you mean because one should be aware of the indirection cost of using inheritance, that isn't the case. Inheritance with overriding needs vtables, but Inheritance alone does not.
Alot of the time when I make a c++ virtual I am going to use it only as a virtual.
And probably going to be using it alot. So having that be less stack memory for abit extra heap memory is not the worse idea
Logan ur so goated
Excellent conclusions! I so much whish we had something like `dyn` in the language and there have been proposals to achieve that (including static reflection-based techniques) but there is a missing piece in C++ : a way to specify a specific interface. We dont have an equivalent of traits, except if you consider a virtual class as being something like that, but then we need reflection to treat that as an interface specification. Anyway I liked that you properly address all the type-erasure details in both languages, I didnt know you could write it in Rust as I always assumed people wiell just use dyn. I'm more experimented in c++ so I can confirm you treated the comparison very fairly.
Concepts, CRTP, SFINAE (please use enable_if though if the former two don’t suffice), …
C++ DOES have the means to accomplish what you say, even at compile time.
The problem is that 99% of those pesky Rust vs C++ comparisons (this video is not included, it’s very good if you ask me) are not fair even by a long shot (even batshit I would claim): they usually compare the latest nightly build of Rust with some experimental crate to… well, not even C++, more like C with classes, not even using the language’s standard library.
Which creates a positive feedback loop determining more gullible ex-JSer, Self-Taught(TM), Rust-enthusiast(TM), ChatGPT-enthusiast(TM), I-use-arch-btw(TM) “developers” to further push the agenda that Rust is somehow unlike the rest of the languages that have been compared to no avail against C++.
@mariansalam While I agree with your other statements (I tried Rust for dayjob, but I prefer some aspects of C++ personally, in particular in generic programming), I disagree that "Concepts, CRTP, SFINAE" are enough to allow generating type-erasing types given a simple interface description. First, we dont have that simple interface description. The closest we have is a virtual class or a data-less type (only functions). Concepts acts like expression filters, they dont specify an interface from which we can infer code, same with all you cited except CRTP (but I'm not sure how you would use that to help).
Then comes the issue of actually going through that interface to generate the type. Currently the closest thing that allows us to do that is macros. We need some kind of static reflexion mechanism to allow going through the functions and generating code from that.
All the attempts I've seen successful relied on experimental static reflection implementations, which have to come from the compiler.
So basically my point is: we need either static reflection provided by the language -in whch case we can do it using library code, indeed- OR a whole language feature to enable automatic generation of type-erased types given
Note that I followed a lot of expert people taknig a stab at it (I tried to but quickly abandonned lol) and they all agree with my point. But if you see a way to do this (maybe using C++23 features, that are novel enough that we might not see some uninteneded "features") feel free to show me and the rest of the C++ community, they would be incredibly interested. Basically...
"C++ DOES have the means to accomplish what you say, even at compile time."
I challenge that }:D please show me how }:D
It may be a bit unrelated, but I would like to see more videos about C++ from you if that is possible. Your explanation is centered around very small and concise samples of code, which helps a lot with understanding
I have hopes and goals to do more C++ stuff, so this is great to hear! Thanks for the feedback. :)
@@_noisecode thank you!
new logan smith video dropped :O
Another to note when speaking about wide pointers is the "ThinBox" experimental rust type which stores the vtable pointer in the heap allocation.
Usually there are many more pointers to things than things themselves in my data. But 2 fetches instead of 3 may be an important benefit depending on the usage
I wonder how the branch predictor reacts when calling the same function with dynamic dispatch repeatedly on the same object or a bunch of objects of the same dynamic type.
Maybe the additional indirection of C++'s approach causes a good hit chance for speculative execution there.
Would that case lessen the runtime efficiency advantage of wide pointers? 🤔
With concepts (which as I understand it are essentially C++'s way of doing interfaces) and if constexper (compile time executed if statements) in C++ there's very little reason to have polymorphism anymore, because you can have something like a can_speak concept and use that to constrain a non-member template function...
I would say all those features essentially bring C++ pretty close to where Rust is now, where static polymorphism via generics is much more common, but dynamic dispatch still does come up here and there. It’s rarer but not totally obsolete, and it’s there when you need it.
@@_noisecodecan rust do that? That kinda spits in the face of the whole type safety thing
Not sure I understand. I'm saying that (IME) the majority of Rust code does `fn foo() {}`, i.e. static polymorphism, but `&dyn Speak` is there when you need it.
@@_noisecode No I think I'm the one that's misunderstanding...
Concepts have little to nothing to do with interfaces. That is the common misconception. Concepts are just fancy and more elegant way of doing SFINAE and checking compile time preconditions, but there is nothing more you can extract from concept checking than true/false boolean.
Loved it & loved your video with explanations❤, could you perhaps recommend a book / course that gives me more of these? Many courses / lessons I see only deal with the top of the iceberg that is Rust features 🙏🏻
I’ll be working on cranking out more of these. :) In the meantime, I’d make sure to check out the Crust of Rust series from @jongjengset which is an amazing series of intermediate level deep dives into cool topics. The episode on dispatch and fat pointers was actually a great resource while I was working on this video!
@@_noisecode thanks for that 👍🏻
It would have been interesting his Rust's Any type stacks up in all this, as it is another way to deal with unknown types (although with slightly more flexibility and different use cases)
This is actually extremely fast to answer: Rust’s Any trait is (roughly) that RTTI pointer from the C++ vtable, but opt-in as a vtable unto itself. It behaves exactly like any other trait as described in the video, and it just so happens that the methods provided by Any let you get type information at runtime.
Great video! Total Rust victory!
ty - i like rust more and more once things are explain ed like this
wake up babe new logan smith video dropped
This is cool, can you share the source code for the animations in the video?
What do you use to create your slides? Manim? Google Slides? The transitions are so smooth
The description says Manim for animating and Blender and Audacity for editing.
It's so delightfully ironic that the guy at the end is called Sean Parent.
Could you cover FFI? How to call foreign functions
Help me understand please, when you say around 7:43 - 7:45 that the speak_thunk closure doesn't capture variables, but it does capture data from the Anything struct. How then can you claim that it's not capturing anything? Afaiu, capturing means whenever there's a reference or a move of a variable from the surrounding scope of a closure, and in this case there seems to be data being passed by ref to the closure.
We actually take the data as an explicit parameter to the closure, and then pass in `self.data` at the call site. So the closure doesn't capture the 'outer data', it just uses the one we pass in to it (which happens to be that same 'outer data' when we eventually call the closure).
I thought about naming the closure parameter something other than `data` in order to avoid exactly this confusion--but one good thing about giving it the same name is that we can't _accidentally_ capture the outer data, since the parameter name shadows it.
A tangential question: IIUC static dispatch generates and selects the specific implementations for the concrete type at compile time just like if I had duplicated the code for each concrete type myself, while dynamic dispatch selects it at runtime.
But when does dynamic dispatch generate the specific implementations? At runtime or at compile time? If at compile time, then why doesn't it increase binary size just like static dispatch? If at runtime, then why is this never mentioned as performance penalty besides the vtable lookup for the selection?
I'm sure I'll get hate for this comment but Java's reflection can do a dynamic dispatch where we don't know if the animal has a speak function but we would like to call cat.speak and dog.speak. The cost for doing this is much higher than anything else shared in the video.
The number of pointers / references needed to reach the "speak" method is at least 3 - I think it's actually 5 (it's been awhile since I needed to do this).
For it to be fully flushed out, it requires polymorphism from the tokenizer. If you just want the base line features, it's non-intrusive. However, in either case the code to get there will rot your brain.
And the CPU cost is much higher, but at least you can tokenize your generic (type) and remember it.
The java reflection "vtable" is associated with the object and therefore not static, and is costly for each call.
It's been very hard for me to decouple a lot of these very atomistic subjects from my original understanding of them coming from Java. All of these disparate concepts being baked in and "solved" with Java's particular inheritance model. The entire time I'm thinking to myself "Rust doesn't have simple interfaces?" xD
I'm learning though, every day.
A few times you mention about the cost of having a vtable even if you don't use it in c++. In most cases I've come across the optimiser has been pretty good at devirtualising these cases so there is no cost.
Parent speaking about inheritance.
If you have (e.g.) a Vec of references, is there a way to have the vtable pointer be part of the pointer inside the Vec, rather than being duplicated on each reference in the Vec?
for Vec specifically this would have no benefit over `Vec where T: Trait`, because of `dyn Trait : Trait`
last time I looked, the rust did not provide enough defined behaviour to implement your idea soundly. vtable pointer comparisons and unsafe casts happen to work, but may break with future optimizations in the compiler
see also "DSTs Are Just Polymorphically Compiled Generics" by Gankra. I'd link, but youtube has a habit of silently erasing comments with links.
Well (if I’m understanding correctly) each of the references in the Vec could be of different dynamic type, so they each need their own vptr.
If you have a situation where you know for certain that all the types in the Vec have the same dynamic type, but don’t know that type at compile time, you could maybe optimize that by figuring how to store the vptr just once alongside a Vec, but you’d have to do some hand-rolled trickery for it.
I'm confused.
I thought that 'dyn Trait' itself is a DST (i.e a value) and only when taking the ref (&dyn Trait) it becomes a wide pointer. I thought that the experimental 'dyn* Trait' is meant to instead store the value behind a pointer as is shown in the video.
Could someone explain this please?
I believe dyn* is similar to ordinary wide pointers except it can store small values (usize or smaller) directly inline instead of through a pointer. It’s like a flexible (usize, vptr) where you can either use the usize part to store a pointer, or else embed tiny values directly into it.
You’re right about `dyn Trait` being a DST that implements Trait, only becoming a wide pointer when you take a reference or pointer to it. AnythingSpeak from the video is thus equivalent to `&dyn Speak` (note the ref), not `dyn Speak`. (By the way, this is why I was careful not to implement the Speak trait for AnythingSpeak, instead implementing .speak() as an inherent method-since &dyn Trait doesn’t (in general) implement Trait.)
Awesome video again!
Okey type erasure is quite an elaborate topic and is maybe first better understood in C++ if you are new to Rust. What made me puzzle in this video (as a rather Rust newborn), whats going on with `AnythingSpeak::new(&Cat)`. Is `&Cat` really refering to the class instead of an actual instance? or is `&Cat`the shorthand for `&Cat()`which creates an instance?
Wide pointers IMO are always so much better (of course only when you really need otherwise such as the anhow:: thing)
because decoupling data from logic is always better, and dynamic dispatch is logic for me, and does not belong to the type, thats why I just hate how C++ forces you to mark stuff you just dont want to mark at the type level, Ok in Rust you mark it with Trait which is an interface in the most general term. I was astonished when you threw in the dyno library at the end, you literally covered the wholy grail of dyn. dispatch here in all senses, amazing video. Its truely marvelous how Louis crafted such a system just with meta programming in C++ to produce the same compiler magic as in Rust. If it would be production ready, I would just replace all the C++ shittyness with this library, full stop.
Haha after I watched the video to the end I came to the conclusion you should learn type erasure first in Rust, its better for you!
100%, great job.
&Cat is a shorthand for &Cat {}. A short syntax to init a struct without fields.
The struct is declared as a "unit struct"
pub struct Cat;
and this allows it to be constructed using "Cat" alone. If it was a normal style struct
pub struct Cat {}
then you would need to write "Cat {}"
and for a tuple struct
pub struct Cat();
you would need "Cat()". For a bit more regularity, Rust also makes "Cat {}" construction work for all of those though.
The instance created by "&Cat" would, by the way, also usually only live in a temporary variable dropped at the end of the statement. This code relies on constant promotion to work, for structs with actual run-time created data, you'd need to place the "Cat { fields: ... }" into a local variable first, and only then you could create the AnythingSpeak from a reference to this local variable.
I remember actually coming up with the wide-pointer approach myself when leraning C after learning Java. I started thinking about how things are actually laid out in memory, and I wanted to design a way to do method calls on null objects because in java it would be really convenient if I could say 'foo.bar()' and have bar() check for null, rather than have to do 'if (foo != null) foo.bar()'. the polymorphism/dynamic dispatch was sorta an afterthought, and I really preferred it because, to me, it seemed like an implementation that very logically followed from interfaces, and not from inheritance (and I much prefer interfaces over inheritance).
I suppose there isn't null in rust, so that benefit I thought of wouldn't be present here (though rust's null handling is obviously better). My only questioning now is how it is handled if a type implements multiple traits. is there an additional vtable pointer included in the wide pointer for each trait, or are they packaged together somehow?
Because the trait/vtable is associated with the wide pointer, not the source object, there's no problem with multiple traits--if a type T implements both Foo and Bar, coercing it to a `dyn Foo` will create a wide pointer holding a vptr with Foo's methods, and coercing it to a `dyn Bar` will point to Bar's methods instead. A `dyn Foo` doesn't need to contain any information about Bar at all. So in other words, T basically has a separate vtable for each trait it implements, and the one that gets used is the one relevant to the wide pointer it is being coerced to.
Rust supports combining multiple traits through trait "inheritance", e.g. `trait Baz: Foo + Bar`. If you then implement Baz for T and then coerce a T to a `dyn Baz`, you will get a pointer to a Baz vtable, which yes, will itself have Foo and Baz "sub-vtables" combined together in some way that the compiler deems best.
3-4 days before, I asked question about dynamic dispacth in rust to chatgpt. And it gives cat, Dog and speak example :).
7:21 I‘m not lying when I say, that my mind was completely blown away 😮
This video should be course required
In Haskell it is probably:
data AnySpeak = forall a. Speak a => AnySpeak a
instance Speak AnySpeak where speak (AnySpeak x) = speak x
And, if you’re wondering, this is both the intrusive approach and the wide pointer approach at the same time. Haskell calls the vtable for a typeclass a “dictionary”, and it gets stored right alongside the normal data of that constructor in the existential you just wrote. However, Haskell values are all “lifted” by default, meaning they’re pointers anyway. In a sense this is the worst of both worlds (you have a pointer to a wide pointer), but it also lets you much more casually select which side you’re going for if you want to.
Just make AnySpeak a newtype for a Rust-like wide pointer, or attach an UNBOX pragma to the data for a C++-like intrusive approach.
@@PthariensFlame I don't think it is possible to have existential constructor with newtype. Mentally I imagine that "forall a. " creates variance of constructors by type. And it is surprise that it works as thin pointer given that more common use is when you have all type information needed to reference concrete instance. But I agree that it is effectively 2 level thunks and either making inner part inlined (e.g. BangPatterns/StrictData) or making outer part thunk-less should somewhat flip between wide/think pointers. Not sure how, though.
I HAVE BEEN DYING FOR AGES LOOKING FOR SOMETHING AKIN TO RVALUE PROMOTION...AHHHH!!!!
Seriously, thank you for outlining the actual mappings of 'gee I wish I had this feature while writing C' to rust.
Hm I wonder if it's possible to do dynamic dispatch without vtables? Obviously you need at least 1 layer of indirection since you're doing dynamic calls but less indirections obviously = more fast so that only 1 layer of indirection is ideal ;) I was planning out how I would make a game I'm working on recently and for the entities I thought up a way I could possibly do that but idk how scalable it is since I haven't actually gotten around to trying it yet lol
You do definitely need a layer of indirection, but as I showed before doing the SpeakFunctions refactor, you _can_ store your function pointers directly inline in the wide pointer (making it a sorta Very Wide Pointer) which removes a jump to the vtable.
Here’s a Rust crate that does basically exactly that for cheaper dynamic dispatch with the Fn trait: docs.rs/simple-ref-fn/0.1.2/simple_ref_fn/
The dyno library I mentioned at the end also (I believe) gives you a mechanism for inlining some or all of the vtable into the wide pointer itself.
Inheritance that obeys the Liskov Substitution Principle (id est, that doesn't have overriding) can be implemented using the old C style way: a switch on a type id enumeration.
Was the point using the compiler explorer to show that the code is valid and compiles?
Fair question-I’m just in the habit of using CE as a quick “IDE” for stuff like this because it’s easily shareable and I like that it automatically compiles and runs when I finish typing.
I'm not sure if I invented this form of dynamic dispatch or if it already exists or if it's just nonsensical. But I have a 3rd approach that doesn't use any pointer. Here is an example implemented in rust:
trait Animal {
fn make_sound(&self);
}
struct Dog;
struct Cat;
impl Animal for Dog {
fn make_sound(&self) {
println! ("woof")
}
}
impl Animal for Cat {
fn make_sound(&self) {
println! ("meow")
}
}
enum AnyAnimal {
A(Dog),
B(Cat)
}
impl Animal for AnyAnimal {
fn make_sound(&self) {
match self {
AnyAnimal::A(dog) => dog.make_sound(),
AnyAnimal::B(cat) => cat.make_sound()
}
}
}
fn main() {
let animal = AnyAnimal::A(Dog) ;
animal.make_sound();
animal = AnyAnimal::B(Cat);
animal.make_sound();
}
It accomplishes the same thing as the other dynamic dispatch approaches but using a typesafe union instead of pointers and function pointers. The only problem is that all implementors need to be compile time known. Which is the case most of the time. With compiler support this could look similar or the same as the native rust version. Sure this approach has its own ups and downs but it's a valid different approach. What do you think about it?
This approach is called 'enum dispatch' and it's often a very, very good alternative to "real" dynamic dispatch! Usually I reach for this myself tbh when I don't need the full power of &dyn. One difference, as you said, is that it operates on a closed set of types; you can't later add new implementers without changing the enum, unlike &dyn Trait where you can add a new implementer (even in e.g. a downstream crate) and pass it into existing code and it "just works." This might be an upside or a downside depending on the situation. But on the upside, this approach avoids the heap/references and can provide better optimization opportunities for the compiler since it can see the full set of operations in your AnyAnimal::make_sound ahead of time.
And it's true that this code doesn't have any pointers per se, but it does still have indirect jumps, powered by the enum discriminant and the match statement. If you squint, it's a little bit like your enum discriminant is a vptr, and your match statement is a vtable, but it is a table of one function for many types, instead of many functions for one type.
@@_noisecode nice I knew this is to obvious to be unknown 😅
You correctly said that in its hand written form it's not usable in library client bounding code. But if the compiler generates the enum after it searched all implementors it would work.
Imagine the example but without the enum and just:
fn main() {
let animal:Animal = Dog;
animal.make_sound();
animal = Cat;
animal.make_sound();
}
And the above code is then compiled to the enum version of my initial comment. This way it is applicable in all cases the real dynamic dispatch can be used (I think 🤔😉)
That's an interesting idea! It might be tricky in Rust's compilation model because it would cause arbitrary amounts of compilation (any code that uses AnyAnimal, even in your program's dependencies) to have to be deferred (basically) until linking, a.k.a. the last possible moment when you can be sure you have the full set of types. (Also right around now someone always comes along and points out how if you do dynamic linking, you might have new types come in at runtime that you can't possibly know at compile time.) But it might be an interesting idea to explore, maybe in an experimental language or maybe I'm just being obtuse about how it could be done reasonably in Rust. :)
Did the promised Rule of 3/5/0 part get cut with the other material, or did I just sleep through it somehow?
I mention it very briefly during the part about virtual destructors. I do wanna dig into it more in a followup though.
@@_noisecode Thanks, I'll rewatch that. I was less interested in the C++ part so I guess I didn't pay close enough attention. :-)
Hah, I don't feel bad that I missed it now. :-) For one thing it's purely a C++ thing, not Rust, and I'll probably never write C++ again. For another, that sure was a quick mention of "rule of three" (no 5 or 0!) so I wasn't as asleep as I feared when i read that in the intro afterwards. :-) Thanks for the reply, and I appreciate your videos a lot!
Hah, yeah, I might have oversold it in the description. Thanks for you detective work, will adjust it.
The manually implemented interface struct reminds me of the way Zig's allocators work. This can even be done in C.
Also a lot of Zig's comptime shenanigans is just constant promotion taken to it's logical extreme
@@fabricatorzayaclike evaluating constexprs?
@@unflexianpretty much anything, barring I/O can be called as comptime by the caller. It's kinda like if in C++ everything was constexpr by default, but I am not sure.
It would be good to cover a comparison with static dispatch (via type erasure) too, which is more interesting, in both languages, IMO.
Curious what you mean by “static dispatch via type erasure.” Are you just talking about comparing compile-time generics/templates between the two languages?
This video does presuppose that you have a reason to reach for dynamic dispatch instead of static, and yeah, I didn’t cover the pros and cons of static vs dynamic.
@@_noisecodeI’m thinking mostly about heterogeneous collections that are dispatched without the use of “dyn”. I saw another comment that mentioned enum dispatch in Rust which is one way to do it (admittedly there’s a runtime dispatch involved of course but from the programmer’s point of view there’s no obvious “dynamic” dispatch). In C++ there are some interesting ideas by Klaus Iglberger on implementing static dispatch via type erasure, which avoids the use of a vtable by using a combination of the strategy / bridge / prototype patterns.
I’d love a link to Klaus Iglberger’s work that you’re referring to. In his CppCon 2022 talk that I just watched, he appears to implement the exact same approach that I did in the first half of this video-a type erased interface that does dynamic dispatch internally inside a static interface (and there are vtables in play for sure).
Anyway yeah! I could have covered enum dispatch / tagged unions in this video too; although since those are constrained to a fixed set of types, whereas “true” dynamic dispatch can handle an open set of types, I guess I sort of consider that to be a bit more of an apples-to-oranges comparison. Maybe I’ll tackle it anyway in the next one though. :)
@@_noisecode there are several, it's something he likes to revisit year on year:
th-cam.com/video/4eeESJQk-mw/w-d-xo.html
th-cam.com/video/qn6OqefuH08/w-d-xo.html
But if you search for "klaus iglberger type erasure" you'll find a lot more.
It's good to hear that it might be the same thing as what you implemented, it has been a while since I watched any of those videos and I didn't make the connection.
One thing I thought was really useful in your video is to learn that "dyn" isn't as expensive as "virtual" in C++. I tend to avoid virtual functions as much as I can, and I was naturally steering away from Rust's dyn for similar reasons, but it sounds like it's not as bad. I might have to become more willing to use it, since sometimes it's exactly what's needed. I wonder how dyn benchmarks alongside enum dispatch? Time to write some code methinks...
You’ll have to let me know what you find! My guess is that enum vs dyn will both outperform the other on different benchmarks. They each have strengths and weaknesses versus the other, and on the whole I’d wager they’re similar enough that there’s no sense avoiding dyn when it’s the right tool for the job.
Don't use virtual functions use concepts for compile time polymorphism and function function pointer wrapper(s) for runtime polymorphism.
Would be real interesting to have the D language mixed in with these 3.
how does c++ store their vtables for objects with multiple interfaces implemented ?
it cannot just store all of the virtual methods in one vtable cuz if we had
Dog: Animal, Pet
Snake: Animal, Attacker
the calling code would not know if Pet or Animal functions were first 🤔
and the same with a function that just accepts Pet, it would not know where does it's part of vtable start
in case of fat pointers it is easy as you just store only the pointer to the vtable that matters
Snake ends up with two separate vptrs, one inside its Animal subobject and the other inside its Attacker subobject, that point to the different respective vtables. That way, if you pass a Snake to a function that takes an Attacker&, that function just sees a fully-formed Attacker object with a vptr at the beginning as expected, even though we know that Attacker is just a subobject inside a larger structure. So this layout actually works out pretty cleanly for the needs of upcasting IMHO, although the downside is of course that your space overhead grows with each new interface. In some other comment somewhere on this video I talked about a time I had to untangle a class hierarchy (of what were supposed to be empty classes, IIRC) that had like a kilobyte of vptrs in the final derived objects.
I still don't understand how OO implements interfaces ... You need a different vtable based on which Interface one is using it through ... but how are they all the same pointer in the instance?
- I find the Rust approach much more sensible and easy to understand... - Probably the only drawback is atomic operations on a singe pointer work, and on a wide pointer? Who knows, probably not...
In OO, you implement an interface by inheriting from it. In C++, if you have a class C that inherits from both A and B, the compiler puts A and B “subobjects” inside of C, and so if both A and B have vptrs, C ends up having two vptrs inside of it, one inherited from A and one inherited from B. The ‘main’ one is the one inherited from A (assuming A is first in the list of base classes), and in C’s constructor, it fills in that ‘main’ vptr with a vtable containing info about both A and B. But, when you upcast a C* to a B*, it’s B’s vtable that ends up getting used for virtual calls on that B*, which only contains info about B’s methods. (Interestingly, those methods will be “thunked” to offset the B* back into a C* before calling, basically by subtracting the offset of the B subobject.)
This gets more complicated by virtual inheritance but we shall not speak of such evils here.
Anyway yeah, this is another con of intrusive vptrs-you end up with even more vptr bloat when you use multiple inheritance, and that bloat is then transitive to anyone who inherits from you too. I remember once untangling a class hierarchy full of _empty_ classes that were using virtual functions and many base classes for some “cute” function composition stuff, and the leaves down at the bottom had like half a KB of vptrs, no joke.
@@_noisecode Thank you. Very interesting. So A* and B* are different pointers (!?) to different offsets of the struct ... This explains multiple inheritance in C++ in general, I guess - I never realized the pointer itself changes on cast...
- Somehow, each time I learn a new thing about C++, it makes me like it less and less 😅 (your Rust usefulness example for this approach is good, but adding 100 pointers of bloat to an empty struct as you said it can ... just shows how bad of an idea it is if used by default...)
- This makes me wonder how it works in Java etc. ... I think they are always the same pointer, regardless of interface...
Yep, a pointer might need to be offset during a derived-to-base conversion (or vice versa) when multiple inheritance is involved. As a corollary, you *must* use static_cast or dynamic_cast (or implicit conversions where possible) for these types of conversions, since they are aware of this fact; reinterpret_cast or rogue C-style casts* will ignore it and just type-pun the address directly without offsetting, and will then lead to UB.
I have no idea how Java implements this stuff; I pray it somehow avoids some of this mess. :)
*C-style casts do the right thing when they select static_cast from the list of things they try; but if something goes awry (esp during refactoring) and they fall back to reinterpret_cast, you get UB. This is a big reason it’s a best practice to avoid them.
Love the video! The effort was worth it. One small thing: Can you please say standard function instead of stud function? thx
Thanks for watching and the kind words, I really appreciate it! As for “stuhd”, that’s an overwhelmingly common way to pronounce ‘std’ when talking about C++, and you’ll hear it all the time in conversations, video content, podcasts, and conference talks. I’ll be sticking with it, since it’s short and ubiquitous.
@@_noisecode It's just like you should say "mute" instead of "mutt"
The cross pollination Rust has caused is really palpable. std::any for C++ is basically std::any from Rust. The funny thing is most Rust things are copied from other languages, but Rust is turning heads because of the excellent conglomeration of good ideas, resulting in a lot of languages looking at copying the same things.
It's definitely super interesting, and the influence of Rust on e.g. all the C++ "successor languages" (Carbon in particular) is especially striking.
To give credit where it's due though, I will point out that std::any is actually the standardized version of boost::any, which predates Rust.
@@anon_y_mousse Two rude comments in 10 minutes.... I'm going to ask you to either be more polite or take your opinions elsewhere.
@@anon_y_mousse Found the fossil.
@@anon_y_mousse The irony of complaining about supposed "censorship" (where???) when you yourself are saying "not-see-ism" lmfao
Louis Dionne has a CppCon talk: th-cam.com/video/gVGtNFg4ay0/w-d-xo.html . In it, he talks about how one could implement dynamic dispatch other than classical inheritance and I think it's quite good. He also mentions dyno in it.
+1, excellent talk. Watched it more than once while researching for this video. :)
This is why I write Go and Python because I can barely comprehend this. Maybe once I become fluent in Go I’ll learn rust one day :/
Hey, I really appreciate you watching and I hope this doesn't scare you off! :) I certainly didn't understand this stuff my first time being exposed to it, and also, this is some slightly-more-advanced black magic that isn't at all crucial knowledge for getting started in Rust and C++ and other systems languages--it's just fun to geek out on once you have your feet wet. You shouldn't feel bad at all if it went over your head. Also--hearing information you don't understand is just the first step toward understanding it. Congrats on the first step!
Is the video rolling at 1x your typing speed?
Most of it yes! But I did speed up a couple parts just to help with awkward pauses and pacing. Also I had to re-record it a bunch of times for various reasons so by the take you see in the video I had some muscle memory built up. ;)
I've been doing rust for 5 months full time and i cant even see the skill ceiling yet.
Seems like implementing intrusive pointers in Rust is an ugly pain in the ass while implementing wide pointers in C++ would be pretty easy and even trivial
The implementation of wide pointers in C++ is quite similar to the handwritten wide pointer in Rust. I wouldn't exactly call it trivial, although you might argue it's a smidge simpler than the Rust version since you don't have to think about unsafe, PhantomData, etc.
Something like this. godbolt.org/z/zGxdsEsxd
Great video, but you should've at least mentioned that in Rust land they're typically called fat pointers to help anyone who wants to google it further
I think those people will be fine-googling “rust wide pointers” brings up a wealth of highly relevant results, including results that use the term ‘fat’ instead.
I do appreciate the thought; I always make a very conscious effort to make sure that all terms are used in these videos are accurate and googleable. Thanks for watching!
Is that why so many software written in Cpp are unreasonably slow?
composition over inheritance...
i heard thunk this must be haskell
noo nevermind this code does something
Hey I know this guy
Its so not simple - because imagine that many people compile linux kernel with 32 bit pointers just to save memory on 64 bit single board computers... Even 32->64 bit can go huge memory (and thus imperatively also CACHE) wasting so imagine what happens if you store fat pointers....
I agree on paper it can be faster, but looming effect of waste is also there - but honestly you should not touch dyn / virtual anyways unless very very clumsy otherwise. Btw I also think about implementing my own very interesting smart pointer in C++ that I planned originally for my own language and it also uses fat pointers under the hood so I should be quiet likely... but this also remids me: when you say you have to roll your own in C++ if you want the rust style - I hope you see that its very likely that you can literally implement it as library using template metaprogramming.
But I would not say which is clear winner here - its just not this simple.