How exactly is std :: make_integer_sequence implemented?

Question

I watched a C ++ 11/14 metaprogramming conversation where some effective alternatives for common algorithms and tmp templates are described.

Most of this performance improvement comes from using variable templates instead of recursive traversal, and in many cases the way to use variable templates was to extend the variational package created using index tricks or other std::integer_sequence .
Since this efficiency comes from the fact that a instancing std::integer_sequence and, in particular, alias std::make_integer_sequence not a costly task, I want to make sure that the current modern implementation of the standard library C ++ 1y effectively enough to make make_integer_sequence not a difficult task and time / memory. How exactly is std::make_integer_sequence actually implemented in C ++ 1y-ready compilers?

Please note that I am not asking how to implement it effectively , but how the compiler developers actually decided to implement it.

The only make_sequence implementations I know of is the simple recursive approach of O (n), and the clever O (logN) approach is separation and victory.

Answer 1

None of the main compiler standard libraries currently provide sub-O (n) (logarithmic or otherwise) implementations of whole N3658 compile-time sequences.

libstdc ++ (gcc):

The standard implementation of O (n), going along the chain of typedef s. This is equivalent to the FP function concatenating to the end of the list returned by the recursive call.

libc ++ (clang):

O (n), but with an interesting 8x expanded loop.

MSVC ( VS14 CTP1 ):

O (n), using recursive inheritance built on an integral constant and an integer sequence, the latter is used as a drive (in the sense of FP). (Please note that the implementation of the VS14 is actually in the title type_traits , rather than utility .)

ICC is currently not documented as providing constant ongoing support for compile time.

---

std::integer_sequence about the effectiveness of std::integer_sequence is probably not at this stage; any problem for which integer compilation time sequences are suitable will encounter compiler constraints (in terms of the number of function arguments and template, etc.) long before the performance of the algorithm used by a large value affects compilation time. Also think that if std::make_integer_sequence used elsewhere in your compilation (for example, in a library template), then the compiler will be able to reuse this call, since template metaprogramming is purely functional.