c++ - 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.