CppCon 2017: Louis Dionne “Runtime Polymorphism: Back to the Basics”

CppCon.org
-
Presentation Slides, PDFs, Source Code and other presenter materials are available at: github.com/CppCon/CppCon2017
-
C++ solves the problem of runtime polymorphism in a very specific way. It does so through inheritance, by having all classes that will be used polymorphically inherit from the same base class, and then using a table of function pointers (the virtual table) to perform dynamic dispatch when a method is called. Polymorphic objects are then accessed through pointers to their base class, which encourages storing objects on the heap and accessing them via pointers. This is both inconvenient and inefficient when compared to traditional value semantics. As Sean Parent said: Inheritance is the base class of evil.
It turns out that this is only one of many possible designs, each of which has different tradeoffs and characteristics. This talk will explore the design space for runtime polymorphism in C++, and in particular will introduce a policy-based approach to solving the problem. We will see how this approach enables runtime polymorphism with stack-allocated storage, heap-allocated storage, shared storage, no storage at all (reference semantics), and more. We will also see how we can get fine-grained control over the dispatch mechanism to beat the performance of classic virtual tables in some cases. The examples will be based on a real implementation in the Dyno library [1], but the principles are independent from the library.
At the end of the talk, the audience will walk out with a clear understanding of the different ways of implementing runtime polymorphism, their tradeoffs, and with guidelines on when to use one implementation or another.
[1]: github.com/ldionne/dyno
-
Louis Dionne: Amazon, Software Engineer
Louis is a math and computer science enthusiast with interest in C++ (meta)programming, functional programming, domain specific languages and related subjects. He is a member of the C++ Standards Committee and of the Boost community, where he authored the Boost.Hana metaprogramming library.
-
Videos Filmed & Edited by Bash Films: www.BashFilms.com
*-----*
Register Now For CppCon 2022: cppcon.org/registration/
*-----*

[@TobiasFuchs]

link to the related talk mentioned at 5:59 "Better Code: Runtime Polymorphism - Sean Parent" ua-cam.com/video/QGcVXgEVMJg/v-deo.html

[@oktal3700]

Links from penultimate slide:
Zach Laine "Pragmatic Type Erasure" ua-cam.com/video/0I0FD3N5cgM/v-deo.html
Boost.TypeErasure boost.org/doc/libs/release/doc/html/boost_typeerasure.html
Adobe Poly stlab.adobe.com/group__poly__related.html
Eraserface github.com/badair/eraserface
Liberasure github.com/atomgalaxy/liberasure
2004 thread on interfaces goo.gl/zaBN6X

[@vittorioromeo1]

Brilliant talk. With proper reflection `dyno` could become the first choice for runtime polymorphism, leaving `virtual` in the dust.

[@YourCRTube]

Often a classical hierarchy is needed - the child need to know about its parent and use its functionality, improve upon it. Here only the case of an 'interface' is tackled, not a complete inheritance (as in not-by-interface-alone).

[@randfur]

@@YourCRTube I don't think using dyno means you can't use inheritance to share code and fields as per normal. It just changes the dispatch methodology to not depend so heavily on the heap in the common case.

[@kensmith5694]

The need to allocate on the heap only happens if you don't know what objects will be needed at compile time. If you know what objects are needed, they can be made before main or actually in the executable. It is still polymorphic if you pass to a routine a pointer to one of the existing object.
If you don't know how many integers or complex objects you are going to need, somebody has to do the heap action.
K&R made an error when they made the null pointer all zeros. Practically all real hardware or virtual memory spaces have a location at address zero. Thus there is a real location that matches up with the null.

[@KhalilEstell]

Thank you. I found it so weird that he kept saying that inheritance results in heap allocation.

[@hansiraber]

great talk, lots of interesting ideas!

[@Kalumbatsch]

for (auto& vehicle: vehicles) is the perfect use for auto. This goes back to the C IFAQ.

[@von_nobody]

20:33 there is tweak to this, you could always send buffer address to vtable and have special version of vtable that thande this buffer as pointer. All checks will be constexpr in that vtable

[@viniciusferrao]

The talk is really good, and I’m considering dyno now. But I’m not sure if it’s only me but that’s definitely not a back to basics talk.

[@crystalgames]

great lecture , thanks

[@botetescribavicentej.2326]

As always, an awesome talk. Glad to see that you are looking for a language solution to this problem.
With proper reflection (meta) we could define the "interface" for some kind of classes and get several kinds of polymorphism: static (a la Concept0x concepts maps), run-time (as suggested by Herb) or type erased (as suggested by Louis), leaving 'ADL` surprises and 'virtual' functions most of the time in the dust.
I believe Swift is covering static and type erased polymorphism with Protocols. Depending on the context a Protocol can be seen as a static constraint or a dynamic one. I would like to see something like that in the C++ world.
In the same way we could see in the future a poly with meta-reflection (55:00) we could as well have static_ or an abstract when the Vehicle interface allows it.
Just wondering on the limits of meta-reflection and what should be done using meta-reflection and what should go directly in the language. Wondering if meta-reflection wouldn't open the Pandora's box. From my side, I would prefer to have some kind of Protocol similar to the ones in Swift in C++.

[@connorhorman]

Nice SBO. The main issue is that the type has to has to be nothrow move constructible or you should not use it.

[@skyeplus]

1:03:59 The objection to inlining virtual calls doesn't make sense to me. It only happens when the type of the object is known, at least on paper.

[@YourCRTube]

Neat talk, probably lacks focus and balance a bit - is it about new ideas or optimizing them and the first idea is much more presented then the others. In any case good talk and great topic - polymorphism + value semantics is very interesting topic to me ever since the old "Inheritance is the base class of evil" talk.

[@huxleyrummy9544]

So, the whole point of the talk was about how to implement the interface thing. Ok, this was in 2017, but it just scream RUST to me so loudly that I can't not notice it. This whole thing is about twisted ways on how to implement Rust's traits in C++

[@Sopel997]

How would one implement 'clone idiom' with that approach? Because it's decentralized you can't just return a Vehicle, because the classes don't know about it (similarily to variant). One way would be to return void*, but that would not only be type unsafe but also you would be returning an owning raw (void) pointer (So it's useful only in the context of Vehicle class. So why not use inheritance if we already imply some connection)... You can't have std::unique_ptr. You don't have return type covariance as with inheritance. What do you do?

[@oktal3700]

The clone function of the "vtable" takes a void* parameter, pointing to uninitialized storage provided by Vehicle, and does a placement-new into this buffer?

[@Sopel997]

Sounds reasonable.

[@louisdionne7268]

Yup, this is how it works.

[@mrlithium69]

Heady stuff.

[@connorhorman]

It should not just outright fail like that, it should just not participate in overload resolution when its too large

[@Bakuta1103]

I assume you're talking about the local_storage case? If so, it should just fail to compile via a static assert. The static assert allows for a clear error message and understanding on why it failed to compile. There is no need for enable_if here since there is no other constructor that would work if sizeof(T) > sizeof(aligned_storage_t)

[@hungbiu8609]

This is not BASIC by any mean at all... But still, good points

[@DimitrisAndreou]

Sean parent link: ua-cam.com/video/QGcVXgEVMJg/v-deo.html

[@thelatestartosrs]

to anyone watching this now, go watch klaus iglberger type erasure talks instead

[@ericcurtin2812]

Or you could just use the tried and tested decorator pattern to do this?

[@velho6298]

Templates, mate.

[@Sopel997]

Templates won't help you with runtime polymorphism.

[@jankodedic3130]

Not with that attitude

[@Evan490BC]

I have the impression that Louis knows his templates... Check out the Boost Hana library.

[@sebastianmestre8971]

Not possible when you want to distribute your library in binary form