5 ms·
Devirtualization and Static Polymorphism
- dalvrosa 8mo ago[dead]
- pjmlp 8mo agoNice overview, it misses other kinds of dispatch though. With concepts, templates and compile time execution, there is no need for CRTP, and in addition it can cover for better error messages regarding what methods to dispatch to.
- dalvrosa 8mo agoFair. New C++ standards are providing great tools for compile-time everything But still CRTP is widely used in low-latency environments :)
- hinkley 8mo agoI wonder if I still have the link. One of the papers I had bookmarked when toying with my own language design was someone that had worked out how to make interfaces as fast or faster than vtables by using perfect hashing and using the vtable as a hash table instead of a list. You can also, when inlining a polymorphic call, put a conditional block in that bounces back to full dispatch if the call occasionally doesn’t match the common case. The problem with polymorphic inlining though is that it quickly resembles the exact sort of code we delete and replace with polymorphic dispatch: if (typeof arg1 == “string”) { } else if typeof arg1 === …) { } else if { } else if { } else { }
- dalvrosa 8mo agoNice one, TIL One caveat with "hash vtables" is that you only really see a performance win when the interface has a lot of specializations.
- hinkley 8mo agoAs I just mentioned in another reply, the problem they were trying to solve was hierarchies where it makes sense for a group of types to be constructed by the combination of two or three narrowly scoped interfaces. For instance, if you treat some collections as read only, you can define comprehensions across them with a single implementation. But that means the mutators have to be contained in another type, which a subset will implement, and may have covariant inputs.
- anitil 8mo agoI've been thinking through what features I'd want in a language if I were designing one myself, and one of my desires is to have exhaustive matches on enums (which could be made of any primitive type) and sum types. The ability to generate perfect hashes at compile time was one of the things that falls out nicely from that
- akoboldfrying 8mo ago> using the vtable as a hash table instead of a list. Could you explain this a bit more? The word "list" makes me think you might be thinking that virtual method lookup iterates over each element of the vtable, doing comparisons until it finds a match -- but I'm certain that this is not how virtual method invocation works in C++. The vtable is constructed at compile time and is already the simplest possible "perfect hashtable": a short, dense array with each virtual method mapping to a function pointer at a statically known index.
- hinkley 8mo agoThe problem they were trying to solve was multiple inheritance, and by nominal type not by code reuse. So interfaces, basically. So these guys essentially assigned a hashcode to every function of every interface and then you would do dispatch instead of obj.vtable[12] you would do modular math x = singature.hash % len(obj.vtable) and call that. I believe this was sometime around 2005-2008 and they found that it was fast enough on hardware of that era to be usable.
- akoboldfrying 8mo agoThanks, I think I get it now. The hash value would be a pure function of the method's signature (argument types and return type) and its name, so that two interfaces with a same-name, same-signature method would hash to the same value and thus invoke the same underlying method; the constraints would be that, after modulo, different methods must map to different indices; and the objective function to minimise would be the vtable size (which I think would be common across all classes). But maybe I don't get it, since this would require knowledge of all interfaces, and as soon as you require that, it's straightforward to build a minimal-size mapping from method name+signature to integer index: e.g., just form the union of all method declarations appearing in any interface, sort them lexicographically, and use a method's position in this sorted list as its index. Lookups in this map are only ever done at compile time so there's no runtime inefficiency to worry about.
- hinkley 8mo ago
- anon291 8mo agoThat's because that type of code is actually better performing than the dynamic dispatch. There's absolutely nothing wrong with this code. It's just that it's not as extensible It's a 'closed world' representation where the code assumes it knows about every possibility. This make extension more difficult The code itself is extraordinarily good and performant.
- 1718627440 8mo agoAs someone who's favorite language is C, I don't see what is wrong with that code? Sure, you need to extend it with a new subtype, but you also need to implement every virtual function anyway. And if you use switch instead of an if-else-chain the compiler will complain when you are missing a subtype.
- AnimalMuppet 8mo agoWhat's wrong with it is, when I extend with a new subtype, I have to fix up the locations that use the type. Potentially all of the locations that use it - I at least have to look at all of them. With the polymorphic approach, I just have to create the new subtype, and all the users can do the right thing (if they were written with polymorphism in mind, anyway - if they use virtual functions on the base class).
- 1718627440 8mo agoWhy would I change the users at all instead of just modifying the dispatch method in the super type?
- AnimalMuppet 8mo agoI see. Yes, you can do it that way. Still... doing it the C++ way, I can just declare the sub type as deriving from the super type, and I don't have to fix up the super type.
- hinkley 8mo agoThat’s the OO way. Of which C++ is an instance.
- TimorousBestie 8mo agoGood article, rare to see simple explanations of intricate C++ ideas.
- dalvrosa 8mo agoThank you :)
- gignico 8mo ago> Under the hood, a virtual table (vtable) is created for each class, and a pointer (vptr) to the vtable is added to each instance. Coming from C++ I assumed this was the only way but Rust has an interesting approach where the single objects do not pay any cost because virtual dispatch is handled by fat pointers. So you carry around the `vptr` in fat pointers (`&dyn MyTrait`) only when needed, not in every instance.
- dalvrosa 8mo agoGood point, thanks for sharing!
- cataphract 8mo agoThere have been type-erasure libraries in c++ for a longish time that allow choosing inline vtables and inline storage. It's definitely been a widely talked about technique for at least 10 years (I see talks about Dyno from 2017).
- gignico 7mo agoWell, Rust as well has been around for more than 10 years now. I don't imply Rust invented the approach. Surely academia knew about it decades before. I was rather commenting on how one's mental model of things can change by learning new languages.
- anon291 8mo agoThis is the standard type class approach. Haskell does the same thing.
- menaerus 8mo ago> only when needed Do you know how is this exactly deduced?
- dminik 8mo agoIt's not. The user has to decide. A specific type/reference to a type will always use static dispatch. fn foo(bar: &Baz) { bar.thing(); } A dyn trait reference will always use dynamic dispatch and carry around the vtable pointer. fn foo(bar: &dyn BazTrait) { bar.thing(); }
- drmikeando 8mo agoWhile this is a great article, I feels it buries the lede. For me, the key insight was from the last paragraph of the article: C++23 introduces "deducing this", which is a way to avoid the performance cost of dynamic dispatch without needing to use tricks like CRRT, by writing: class Base { public: auto foo(this auto&& self) -> int { return 77 + self.bar(); } }; class Derived : public Base { public: auto bar() -> int { return 88; } }; I wish the article had gone into more details on how this works and when you can use it, and what its limitations are.
- dalvrosa 8mo agoThanks for the feedback, I'll consider expanding in a separate post
- yunnpp 8mo agoCrazy web design, by the way. Diggin' it very much.
- dalvrosa 8mo ago:)
- Panzerschrek 8mo agoSince std::variant was introduced I use inheritance and virtual calls much less than before. It's faster, since variant dispatch (via std::visit) is basically a switch statement with all execution paths visible to the compiler and thus inlining is possible. Inheritance and virtual calls are nowadays only necessary in places where it's not possible to statically list all alternatives (where the set of derived classes is open).
- dalvrosa 8mo agoYeah for C++17 or above, it's a nicer and more performant alternative in most cases
- Archit3ch 8mo agoAn expressive combination is Static Polymorphism + Multiple Dispatch, which Julia resorts to when it can.