How exactly is std::make_integer_sequence implemented?

Question

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.

Answer 1

None of the major compiler standard libraries currently provide a sub-O(n) (logarithmic or otherwise) implementation of N3658 compile-time integer sequences.

libstdc++ (gcc):

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.

libc++ (clang):

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

MSVC (VS14 CTP1):

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.

Answer 2

6+ years later, compilers support builtins to do this fast. Clang and MSVC have __make_integer_seq. GCC has __integer_pack. In fact, STL implementations assume such builtins exist! Between these three compilers, only clang's/libc++ seems to have a fallback implementation for make_integer_sequence.

The C++ extensions: type traits section of GCC's manual describes __integer_pack by:

__integer_pack (length)

When used as the pattern of a pack expansion within a template definition, expands to a template argument pack containing integers from 0 to length-1. This is provided for efficient implementation of std::make_integer_sequence.

I haven't found a section in the clang manual that describes __make_integer_seq, but there is this review of the commit that added it to clang.

In the libstdcxx installed with my copy of GCC 11.1.0, this is the code in <utility> (line 328) for make_integer_sequence:

/// Alias template make_integer_sequence
template<typename _Tp, _Tp _Num>
using make_integer_sequence
#if __has_builtin(__make_integer_seq)
      = __make_integer_seq<integer_sequence, _Tp, _Num>;
#else
      = integer_sequence<_Tp, __integer_pack(_Num)...>;
#endif

Similarly, Microsoft's STL defines this in <type_traits>, line 34:

template <class _Ty, _Ty _Size>
using make_integer_sequence = __make_integer_seq<integer_sequence, _Ty, _Size>;

Finally, in libcxx/include/__utility/integer_sequence.h starting at line 39 there's a preprocessor conditional to check if we need to use the fallback:

#if __has_builtin(__make_integer_seq) && !defined(_LIBCPP_TESTING_FALLBACK_MAKE_INTEGER_SEQUENCE)

template <class _Tp, _Tp _Ep>
using __make_integer_sequence _LIBCPP_NODEBUG = __make_integer_seq<integer_sequence, _Tp, _Ep>;

#else
// fallback implementation that uses recursive templates