Why Is It Not Good to Use Recursive Inheritance for Std::Tuple Implementations

Why is it not good to use recursive inheritance for std::tuple implementations?

A non-recursive implementation has better compile-time performance. Believe it or not, in a heavily used library facility like std::tuple, how it is implemented can impact (for better or worse), the compile times the client sees. Recursive implementations tend to produce compile times that are linear in the depth of recursion (or can be even worse).

This impacts more than just the instantiation of the tuple itself. std::get<I>(tuple) for example will take a linear amount of compile time for one implementation and a constant amount of compile time for another implementation. This impact can rapidly deteriorate (or not) when dealing with tuples of tuples. I.e. the recursive implementation could result in O(N^2) compile time while the non-recursive implementation is still O(1).

Fwiw, the libc++ implementation lays the objects out in the order specified by the client, but optimizes away space for empty components using the compiler's empty base class optimization facility.

STD::Tuple implementations C++

why one should be preferred over the other?

The recursive implementation conforms to C++11, so it should be preferred when later standard is not available because it is the only option. The shown flat implementation relies on C++17 by using if constexpr and C++14 by using std::index_sequence.

The flat implementation is simper in my opinion. Also, I suspect that it will be faster to compile, although I recommend measuring to verify that is correct. As such, I would prefer the flat implementation when sufficient standard level is available.

How is std::tuple implemented?

One approach to implementing tuples is using multiple-inheritance. The tuple-elements are held by leaf-classes, and the tuple class itself inherits from multiple leafs. In pseudo-code:

template<typename T0, typename T1, ..., typename Tn>
class PseudoTuple : TupleLeaf<0, T0>, TupleLeaf<1, T1>, ..., TupleLeaf<n, Tn> {
   ...
};

Each leaf has an index, so that each base-class becomes unique even if the types they contain are identical, so we can access the nth element with a simple static_cast:

static_cast<TupleLeaf<0, T0>*>(this);
// ...
static_cast<TupleLeaf<n, Tn>*>(this);

I've written up a detailed explanation about this "flat" tuple implementation here: C++11 tuple implementation details (Part 1)

How to implement std::tuple efficiently such that a tuple of empty types is itself an empty type?

When all you have is a hammer, everything looks like "why not try CRTP". Because CRTP solves all problems with templates.

Extend tuple_leaf with a class D derived, and pass the type of tuple_base in. (Alternatively, write a template<class...>struct types{}; and pass that in -- all you need is an type that uniquely distinguishes two different tuples).

Modify the get_leaf to get the appropriate class, and now there is no ambiguity.

Problems:

First, without ICF, this makes a bunch of methods that would be identical now distinct.

Second, if you implement recursive tuples, this breaks horribly. The above relies on the fact that a tuple containing a subtuple X has a different set of types in it than the subtuple.

Third, when I tried it myself with the above code, I get empty structures with non-1 size. Strange. And if I bypass the static asserts and the like, get<0> segfaults. This could be an artifact of your simplified problem, I am uncertain.

std::tuple_element need deep template instantination

Why C++11 was not added special operator for getting elements by index? like tuple2 or tuple[0] ?

First, because even if they did, it'd still work the same way: with recursion. Tuples are primarily a library feature. Though they piggy-back off of language features like variadic templates, they were more or less functional in C++98/03.

Second, that would not be possible. Not without a very difficult language change.

It's not clear what you mean by tuple[2].

If you mean that std::tuple<int, float, std::string>[2] should somehow resolve to the typename std::string, then that means you now need to explain why this works. Again, tuples are a library feature, not a language construct. So there would have to be some language construct whereby typename[integer] is a valid construct. What would that be and what would it mean?

If you mean that given:

std::tuple<int, float, std::string> tpl{...};

We should be able to get the string with tpl[2], that's several shades of "not going to happen". C++ is a statically typed language. The only reason std::get is able to get away with what it does is that the integer index is not a function parameter; it is a template parameter. That is what allows std::get<0> to return a completely different type from std::get<2>. That can't happen with operator[](int); that function must always return the same type.

So now you'd need to have something like template<class T, int i> ... operator[](). And that would be very confusing, because you can no longer do tpl[runtimeValue] on that type (since template parameters must be compile-time values). There is no such type where operator[] is restricted from being able to work on runtime values. So you'd be creating a very oddball type.

And even then... it would still have to do recursion to get the value.

Is possible reduce the deep instantiation?

Outside of compile times (which is not an unreasonable issue), what does it matter? A decent inliner will throw most of them away.

As for compile times, there are non-recursive implementations of various features of std::tuple. Whether they can do tuple_element non-recursively, I don't think so. This libc++ implementation seems to suggest that it can't, despite implementing the tuple itself non-recursively.

Why does libstdc++ store std::tuple elements in reverse order?

See this answer for why libc++ chose forward order. As for why libstdc++ chose reverse order, that is probably because that's how it was demonstrated in the variadics template proposal, and is the more obvious implementation.

Bonus: No. These orderings have been stable in both libraries.

Update

libc++ chose forward storage order because:

1. It is implementable.
2. The implementation has good compile-time performance.
3. It gives clients of libc++ something that is intuitive and controllable, should they care about the order of the storage, and are willing to depend on it while using libc++, despite its being unspecified.

In short, the implementor of the libc++ tuple merely felt that storing the objects in the order the client (implicitly) specified was the quality thing to do.

Is a tuple guaranteed to compress empty elements?

No, that is not guaranteed. C++ 11 § 20.4 (the chapter about std::tuple) does not mention the size of the type at all. So there are no guarantees about how the members in a tuple are organised. Any empty-base optimisation and similar effects are purely a quality-of-implementation issue.

Note that this means there is even no guarantee that std::tuple<int, char> will be stored in memory as int followed by char and not vice versa. The layout of a std::tuple object is completely unspecified.

std::tuple and standard layout

No, standard layout requires that all nonstatic data members belong to either one base subobject or directly to the most derived type, and typical implementations of std::tuple implement one member per base class.

Because a member-declaration cannot be a pack expansion, in light of the above requirement, a standard layout tuple cannot have more than one member. An implementation could still sidestep the issue by storing all the tuple "members" inside one char[], and obtaining the object references by reinterpret_cast. A metaprogram would have to generate the class layout. Special member functions would have to be reimplemented. It would be quite a pain.

Where does a tuple store its data?

If you take the time to digest it then the GNU implementation is actually a decent example of recursive inheritance using C++0x variadic templates. This is not a subject that lends itself easily to a layman's explanation and is best understood by reading the code over and over until it makes sense.

From what I can see they're inheriting upwards for each successive type in the tuple's type-list with each inherited class taking charge of the storage for that type until the recursion hits the end of the type-list.

---

Related Topics