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

Question

In this question, Howard Hinnant said

Some implementations of std::tuple use recursive inheritance. But the good ones don't. ;-)

Can someone please shed some light on that?

Answer 1

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.

Answer 2

I don't recall Andrei Alexandrescu's GoingNative 2012 talk exactly, but he talked about this point, and one of the points he mentioned was memory layout. If I have a std::tuple<int, short, char, char>, it will be in memory as char, short, int and this layout will take (on my system) 4 bytes more than if they were laid out as int, short, char. R. Martinho Fernandes has reminded me that the best thing to do would be to order these in memory in an order that minimizes padding, which is neither the order given nor reverse order. (Naïve inheritance does reverse order).

If I write std::tuple<int, char, short, char>, a tuple that works by naïve inheritance would put these in the order char, short, int in memory, using 3 bytes of padding, when optimal has zero bytes of padding. (Either int, short, char, char or char, char, short, int).

Assuming I'm right that it's about padding, then R. Martinho Fernandes said "[my argument] doesn't preclude the use of recursive inheritance for the actual implementation in the optimal order.", so that is why I specify that naïve inheritance is bad.

(The order in memory does not mean that get<0> will give a different object, and R. Martinho Fernandes correctly notes that the order should be invisible to the user. However, these were the points as I have been reminded from the GoingNative event.)

The video is at http://channel9.msdn.com/Events/GoingNative/GoingNative-2012/Variadic-Templates-are-Funadic and the slides are at http://ecn.channel9.msdn.com/events/GoingNative12/GN12VariadicTemplatesAreFunadic.pdf.

Answer 3

One reason not to use a chain of base classes is that there is no chain of constructors involved: the arguments are directly forwarded to the appropriate subobject. Also, it seems that a non-recursive implementation puts a lot less strain on the compiler and creates a lot less [internal] symbols. Not to mention that it is actually easier not to a chain of base classes.