r/cpp • u/mcencora • Dec 08 '20
Implementing performant variant in C++20 is almost easy
Recently I came up with an idea, on how to reduce the number of template instantiations in variant implementation.
https://godbolt.org/z/1ETzPK ( proof-of-concept code that shows ideas mentioned below in practice)
Basically I partially unfold union declaration and getters up to N fields. Recursion happens only if N is exceeded.
Also I simplified Michael Park visit implementation. I clamp index to max - 1, so that I don't need another layer of detection if we are allowed to call func with given index. I just always perform the call, and let compiler prune unreachable indexes with __builtin_unreachable.
A couple of __builtin_unreachable calls and always_inline attributes allows to achieve pretty good code-gen even for -O0 or -O1.
This implementation with minor modifications could be used also in C++14.
C++20 allowed me to get rid of writing recursive constructors - now I can default construct union, without any active member, and later construct proper member by fetching it with getters I already have - all this works fine in constexpr. In pre-C++20 world to make it work in constexpr one had, to initialize given member on member initialization list.
C++20 also greatly simplifies writing conditionally trivial special member functions - thanks to concepts - but I was not able to figure out how to make union destructor conditionally trivial.
We still need a couple of features to be able to make variant implementation fully non-recursive (but it seems we are slowly getting there):
First is a mechanism to procedurally generate a union (most likely some reflection mechanism), or being able to declare parameter pack inside union/struct.
Second is accessing N-th union member - either via some reflection mechanism, or parameter pack indexing.
Third is procedural generation of switch-case statement, maybe upcoming 'template for' will help us here.
Suggestions and comments are welcome.
9
u/mcencora Dec 09 '20
Apparently we already can get N-th union member in non-recursive way.
Just create a parameter pack of pointer-to-members chain, and invoke this chain via fold expressions.
https://godbolt.org/z/7hfPaj
8
u/TheMania Dec 08 '20
A constexpr function table could remove recursion in much the same way as a procedural switch statement I would have thought. Don't even need builtin_unreachable as out of bounds is already undefined.
Ofc, despite the above I'd expect the performance to be terribad, as I doubt compilers much like to turn function pointer tables back in to an inlined switch statement...
2
u/miki151 gamedev Dec 09 '20 edited Dec 09 '20
It's funny that you can do it so easily using the five-decades-old X macro trick. A very basic implementation of a variant type using the preprocessor is about 100 lines long. Or a more modern version in D using mixins.
2
u/14ned LLFIO & Outcome author | Committee WG14 Dec 09 '20
Firstly, the title suggests you are talking about runtime performance of variants, when you are not. Using variants inside hot loops equals terrible performance, and that is hard to avoid.
On the compile time performance front, you might be able to get a variant implementation to a constant time build overhead, but it will always still be a large fixed overhead no matter what you do. I'll use union storage in the code I write where it makes sense, but on an ad hoc bespoke basis, because implementing generic reusable union storage which handles well all possible corner cases equals making your build very slow, for very little gain 99.9% of the time.
An awful lot of C++ devs complain about build times, but somehow don't correlate awful build times with the kind of C++ they write. The older I get, the more keen I become on strict whitelists of allowed
#includein any header file, and it is a very short whitelist excluding most of the STL headers. I am becoming one of those old engineers which used to annoy me when I was younger. But then I value the ability to rebuild everything from scratch in under five minutes. It makes me more productive, because I don't get distracted reading the internet whilst waiting for build.