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.

Illaffected

Well, since it's a compile-time construct, it's O(0)... do you want it even faster? – Daddylonglegs

@KerrekSB I think he's referring to the compile-time complexity of generating the sequence ? – Mittiemittimus

@quantdev: What does "generating" mean? – Daddylonglegs

Can you provide a link to that talk please? – Punke

@KerrekSB I was talking about compile-time complexity, i.e. the effort done by the compiler to generate the sequence. Measure it by template-instantation-depth required, time, RAM consuption, etc. – Illaffected

KerrekSB is right, there's no "generation" involved here, I was mistaken on what it does – Mittiemittimus

@0x499602D2 The talk was MPL11, a new metaprogramming library for C++11 – Illaffected

Well, compile time is certainly an interesting problem, but without a reasonably deep understanding of compiler internals I imagine it will be difficult to come up with a satisfactory, general answer. Perhaps if you could give the question some context with reference to existing technologies? – Daddylonglegs

@KerrekSB I was talking only about the implementation done by compiler vendors (Maybe GCC stdlibc++ and/or LLVM stdc++), and reasons about why that implementation was selected. I was thinking if a real Standard Library implementation relies on compiler-specific tricks, or its implemented with well known tmp approaches (Like those menctioned above in the answer). I'm not asking about in-depth knowledge of compiler internals, if thats what worries you. – Illaffected

@Illaffected so you basically want the source code ? (I can tell you, there is no "specific trick") – Mittiemittimus

@Mittiemittimus I can dive on the stdlibc++/stdlib++ sources myself, but I was asking more about the WHY than about the HOW. I was expecting some expert could answer this question, this is SE "Expert answers to your questions" isn't? ;) – Illaffected

@Illaffected Is there video of the talk? (sorry for being off-topic) – Punke

@kerrecksb both recursion depth and instantiation count are pretty objectivr abstract measures of performance, and compile times with large n may be long enough to measure (say, 3 trillion size_t?) if it does not go belly up first. – Putdown

@0x499602D2 Sure youtu.be/8c0aWLuEO0Y – Illaffected

@Rapptz thanks for that edit ;) I was thinking about this question when I have seen the comitee announcement. You beat me for minutes. You have started a campaign to fully update c++1y tags to c++14? – Illaffected

@Illaffected Yes. It's an on-going effort by Lounge<C++> to migrate from c++1y to c++14. Just need votes for the synonym approval now. – Anisomerous

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.

Casaubon

By O(1) you meant O(n)? – Aerate

By O(n) you really meant O(n^2)? Note that the size of each instantiation is O(n) and you perform O(n) instantiations, so the total compile time cost of the naive approach is O(n^2). – Manysided

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

Eyeshade