I was watching a C++11/14 metaprogramming talk, where some efficient alternatives for common algorithms and tmp patterns are described.
Most of that efficiency gains come from using variadic templates instead of recursive traversal, and in many cases the way to use variadic templates was to expand a variadic pack generated via the indices trick or other std::integer_sequence instantation tricks.
Since that efficiency comes from the fact that instancing a std::integer_sequence, and specifically the alias std::make_integer_sequence is not an expensive task, I want to be sure that the current state-of-the art implementation of C++1y Standard Library is efficient enough to make make_integer_sequence instantations not a complex and time/memory consuming task.
How exactly std::make_integer_sequence is actually implemented in C++1y-ready compilers?
Note that I'm not asking how to implement it efficiently, but how compiler vendors actually decided to implement it.
The only implementations of make_sequence I'm aware of are the simple O(n) recursive approach and the clever O(logN) divide and conquer one.
None of the major compiler standard libraries currently provide a sub-O(n) (logarithmic or otherwise) implementation of N3658 compile-time integer sequences.
Standard O(n) implementation walking a chain of typedefs. This is equivalent to a FP function concatenating to the end of a list returned by the recursive invocation.
O(n) implementation, but with an interesting 8x unrolled loop.
O(n), using recursive inheritance templated on an integral constant and integer sequence, the latter used as an accumulator (in the FP sense). (Note that the the VS14 implementation is actually located in the type_traits header, not in utility.)
ICC is not currently documented as providing compile-time integer constant support.
Worrying over the efficiency of std::integer_sequence is probably not worth it at this point; any problem for which compile-time integer sequences are suited is going to bump up against the limits of compilers (in terms of numbers of function and template arguments, etc.) long before the big-O performance of the algorithm used influences compile times. Consider also that if std::make_integer_sequence is used anywhere else in your compilation (e.g. in library template code) then the compiler will be able to reuse that invocation, as template metaprogramming is purely functional.