Implementation C++14 make_integer_sequence

Question

I tried to implement the C++14 alias template make_integer_sequence, which simplifies the creation of the class template integer_sequence.

template< class T, T... I> struct integer_sequence
{
    typedef T value_type;
    static constexpr size_t size() noexcept { return sizeof...(I) ; }

};

template< class T, T N>
using make_integer_sequence = integer_sequence< T, 0,1,2, ... ,N-1 >; // only for illustration.

To implement make_integer_sequence we need a helper structure make_helper.

template< class T , class N >
using make_integer_sequence = typename make_helper<T,N>::type;

Implementing make_helper isn't too difficult.

template< class T, T N, T... I >
struct make_helper
{
   typedef typename mpl::if_< T(0) == N,  
                  mpl::identity< integer_sequence<T,I...> >,
                  make_helper< T, N-1, N-1,I...> 
               >::type;
};

To test make_integer_sequence I made this main function:

int main()
{
    #define GEN(z,n,temp)   \
     typedef make_integer_sequence< int, n >  BOOST_PP_CAT(int_seq,n) ;

   BOOST_PP_REPEAT(256, GEN, ~);
}

I compiled the program with GCC 4.8.0, on a quad-core i5 system with 8GBs of RAM. Successful compilation took 4 seconds.

But, when I changed the GEN macro to:

int main() {

#define GEN(z,n,temp) \
typedef make_integer_sequence< int, n * 4 > BOOST_PP_CAT(int_seq, n) ;

BOOST_PP_REPEAT(256, GEN, ~ );
}

The compilation was unsuccessful and outputted the error message:

virtual memory exhausted.

Could somebody explain this error and what caused it?

EDIT:

I simplified the test to:

int main()
{
   typedef make_integer_sequence< int, 4096 > int_seq4096;
}

I then successfully compiled with GCC 4.8.0 -ftemplate-depth=65536.

However this second test:

int main()
{
    typedef make_integer_sequence< int, 16384 > int_seq16384;
}

Did not compile with GCC 4.8.0 -ftemplate-depth=65536, and resulted in the error:

virtual memory exhausted.

So, my question is, how do I decrease template deep instantiation?

Regards, Khurshid.

Loon

In a talk by S.T.Lavavej I think I heard that Microsoft compiler has a hook to generate make_integer_sequence automatically, (basically?) in O(1). The irony is that one works a lot to implement this for something that a compiler may produce by itself. – Nutbrown

Answer 1

Here's a log N implementation that doesn't even need an increased max-depth for template instantiations and compiles pretty fast:

// using aliases for cleaner syntax
template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>
using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};
template<> struct gen_seq<1> : seq<0>{};

Provolone

Very nice! I would just precise that the depth of instantiations is O(log N) (the number of operations is O(N)). In any case, this is a very fast implementation. – Sciamachy

Should that really be called Concat? – Sear

And for generally( not only for unsigned, for general type T), you couldn't specialization with N = 0, and N=1. Compiler shows following error: error: non-type template argument depends on a template parameter of the partial specialization. – Loon

@Provolone I would read Concat as "take two lists and put them one after the other". Adding "and add the the length of the leftmost list to the contents of the rightmost list" to what Concat does would surprise me. template<class S, unsigned I=1> struct inc; template<unsigned... Is, unsigned I> struct inc<seq<Is...>, I>:seq<(Is+I)...> {}; template<class S, unsigned I=1> using Inc=Invoke<inc<S,I>>; then template<unsigned N>struct gen_seq:Concat<GenSeq<N/2>, Inc<GenSeq<N-N/2>,N/2>>{};, where Concat doesn't add anything to second list, would decouple that operation from concatenation. – Sear

template<unsigned N>struct gen_seq:Concat<GenSeq<N/2>, Inc<GenSeq<N-N/2> , N/2>>{}; \ here last N/2 should be N%2, may be ! – Loon

filed as gcc bug 66059, since 4.9.0 through current trunk have an O(N) implementation. – Freedman

I had trouble using this code, and then realized I should be using GenSeq, not gen_seq, for make_index_sequence. – Adult

From experiments with a similar implementation I found that the sizeof...(I1) in concat is quite inefficient (at least for g++) and it can be improved by passing that number into concat instead of recalculating it. – Brote

@JonathanWakely: Interesting. Seems kinda weird for that to be inefficient. Shouldn't it be some kinda constant-time check? – Provolone

It's surprising to me too. See the code at gcc.gnu.org/ml/gcc-bugs/2015-11/msg01615.html -- the #ifdef DUP one is very slow when using sizeof..., the #else one which is similar to yours is quite fast with sizeof... but even faster without it. – Brote

Can I put in a plea for an example of how to use this! – Astrodynamics

Even if value is passed directly instead of sizeof...(I1), this implementation is ~2x times slower than Apple Clang. – Abney

Answer 2

This is basically me hacking around Xeo's solution: Making community wiki - if appreciative, please upvote Xeo.

...just modified until I felt it couldn't get any simpler, renamed and added value_type and size() per the Standard (but only doing index_sequence not integer_sequence), and code working with GCC 5.2 -std=c++14 could run otherwise unaltered under older/other compilers I'm stuck with. Might save someone some time / confusion.

// based on https://mcmap.net/q/17483/-implementation-c-14-make_integer_sequence by Xeo
namespace std  // WARNING: at own risk, otherwise use own namespace
{
    template <size_t... Ints>
    struct index_sequence
    {
        using type = index_sequence;
        using value_type = size_t;
        static constexpr std::size_t size() noexcept { return sizeof...(Ints); }
    };

    // --------------------------------------------------------------

    template <class Sequence1, class Sequence2>
    struct _merge_and_renumber;

    template <size_t... I1, size_t... I2>
    struct _merge_and_renumber<index_sequence<I1...>, index_sequence<I2...>>
      : index_sequence<I1..., (sizeof...(I1)+I2)...>
    { };

    // --------------------------------------------------------------

    template <size_t N>
    struct make_index_sequence
      : _merge_and_renumber<typename make_index_sequence<N/2>::type,
                            typename make_index_sequence<N - N/2>::type>
    { };

    template<> struct make_index_sequence<0> : index_sequence<> { };
    template<> struct make_index_sequence<1> : index_sequence<0> { };
}

Notes:

• the "magic" of Xeo's solution is in the declaration of _merge_and_renumber (concat in his code) with exactly two parameters, while the specilisation effectively exposes their individual parameter packs

• the typename...::type in...

  struct make_index_sequence
    : _merge_and_renumber<typename make_index_sequence<N/2>::type,
                          typename make_index_sequence<N - N/2>::type>
  

    avoids the error:

invalid use of incomplete type 'struct std::_merge_and_renumber<std::make_index_sequence<1ul>, std::index_sequence<0ul> >'

Serica

Why is this index_sequence rather than integer_sequence? – Bellyful

@einpoklum: because integer_sequence is obliged to have the data type be a template parameter, whereas I've hardcoded size_t, which suited me just fine at the time.... – Psychognosis

@Bellyful To add a little detail to Tony's response: you can't partially specialize on a template argument of a template type. You can't implement integer_sequence this way. The best you could do to get integer_sequence this was is to but fully specialize for every integer type. (this code length for each integer type) – Snipe

Answer 3

I found very fast and needless deep recursion version of implementation of make_index_sequence. In my PC it compiles with N = 1 048 576 , with 2 s. (PC : Centos 6.4 x86, i5, 8 Gb RAM, gcc-4.4.7 -std=c++0x -O2 -Wall).

#include <cstddef> // for std::size_t

template< std::size_t ... i >
struct index_sequence
{
    typedef std::size_t value_type;

    typedef index_sequence<i...> type;

    // gcc-4.4.7 doesn't support `constexpr` and `noexcept`.
    static /*constexpr*/ std::size_t size() /*noexcept*/
    { 
        return sizeof ... (i); 
    }
};


// this structure doubles index_sequence elements.
// s- is number of template arguments in IS.
template< std::size_t s, typename IS >
struct doubled_index_sequence;

template< std::size_t s, std::size_t ... i >
struct doubled_index_sequence< s, index_sequence<i... > >
{
    typedef index_sequence<i..., (s + i)... > type;
};

// this structure incremented by one index_sequence, iff NEED-is true, 
// otherwise returns IS
template< bool NEED, typename IS >
struct inc_index_sequence;

template< typename IS >
struct inc_index_sequence<false,IS>{ typedef IS type; };

template< std::size_t ... i >
struct inc_index_sequence< true, index_sequence<i...> >
{
    typedef index_sequence<i..., sizeof...(i)> type;
};



// helper structure for make_index_sequence.
template< std::size_t N >
struct make_index_sequence_impl : 
           inc_index_sequence< (N % 2 != 0), 
                typename doubled_index_sequence< N / 2,
                           typename make_index_sequence_impl< N / 2> ::type
               >::type
       >
{};

 // helper structure needs specialization only with 0 element.
template<>struct make_index_sequence_impl<0>{ typedef index_sequence<> type; };



// OUR make_index_sequence,  gcc-4.4.7 doesn't support `using`, 
// so we use struct instead of it.
template< std::size_t N >
struct make_index_sequence : make_index_sequence_impl<N>::type {};

//index_sequence_for  any variadic templates
template< typename ... T >
struct index_sequence_for : make_index_sequence< sizeof...(T) >{};


// test
typedef make_index_sequence< 1024 * 1024 >::type a_big_index_sequence;
int main(){}

Loon

Answer 4

You are missing a -1 here:

typedef typename mpl::if_< T(0) == N,  
              mpl::identity< integer_sequence<T> >,
              make_helper< T, N, N-1,I...> 
           >::type;

in particular:

typedef typename mpl::if_< T(0) == N,  
              mpl::identity< integer_sequence<T> >,
              make_helper< T, N-1, N-1,I...> 
           >::type;

Next, the first branch shouldn't be integer_sequence<T>, but rather integer_sequence<T, I...>.

typedef typename mpl::if_< T(0) == N,  
              mpl::identity< integer_sequence<T, I...> >,
              make_helper< T, N-1, N-1,I...> 
           >::type;

which should be enough to get your original code to compile.

In general, when writing serious template metaprogramming, your main goal should be to keep the depth of template instantiation down. A way to think about this problem is imagining you have an infinite-thread computer: each independent calculation should be shuffled off onto its own thread, then shuffled together at the end. You have a few operations that take O(1) depth, like ... expansion: exploit them.

Usually, pulling of logarithmic depth is enough, because with a 900 depth, that allows 2^900 sized structures, and something else breaks first. (To be fair, what is more likely to happen is 90 different layers of 2^10 sized structures).

Sear

Answer 5

Here is another slightly more general variation of Xeo's logarithmic answer which provides make_integer_sequence for arbitrary types. This is done by using std::integral_constant in order to avoid the dreaded "template argument involves template parameter" error.

template<typename Int, Int... Ints>
struct integer_sequence
{
    using value_type = Int;
    static constexpr std::size_t size() noexcept
    {
        return sizeof...(Ints);
    }
};

template<std::size_t... Indices>
using index_sequence = integer_sequence<std::size_t, Indices...>;

namespace
{
    // Merge two integer sequences, adding an offset to the right-hand side.
    template<typename Offset, typename Lhs, typename Rhs>
    struct merge;

    template<typename Int, Int Offset, Int... Lhs, Int... Rhs>
    struct merge<
        std::integral_constant<Int, Offset>,
        integer_sequence<Int, Lhs...>,
        integer_sequence<Int, Rhs...>
    >
    {
        using type = integer_sequence<Int, Lhs..., (Offset + Rhs)...>;
    };

    template<typename Int, typename N>
    struct log_make_sequence
    {
        using L = std::integral_constant<Int, N::value / 2>;
        using R = std::integral_constant<Int, N::value - L::value>;
        using type = typename merge<
            L,
            typename log_make_sequence<Int, L>::type,
            typename log_make_sequence<Int, R>::type
        >::type;
    };

    // An empty sequence.
    template<typename Int>
    struct log_make_sequence<Int, std::integral_constant<Int, 0>>
    {
        using type = integer_sequence<Int>;
    };

    // A single-element sequence.
    template<typename Int>
    struct log_make_sequence<Int, std::integral_constant<Int, 1>>
    {
        using type = integer_sequence<Int, 0>;
    };
}

template<typename Int, Int N>
using make_integer_sequence =
    typename log_make_sequence<
        Int, std::integral_constant<Int, N>
    >::type;

template<std::size_t N>
using make_index_sequence = make_integer_sequence<std::size_t, N>;

Demo: coliru

Seamanlike

Answer 6

Simple implementation O(N). Probably not what you want for large N, but my application is only for calling functions with indexed arguments, and I wouldn't expect an arity of more than about 10. I haven't filled in the members of integer_sequence. I'm looking forward to using a standard library implementation and nuking this :)

template <typename T, T... ints>
struct integer_sequence
{ };

template <typename T, T N, typename = void>
struct make_integer_sequence_impl
{
    template <typename>
    struct tmp;

    template <T... Prev>
    struct tmp<integer_sequence<T, Prev...>>
    {
        using type = integer_sequence<T, Prev..., N-1>;
    };

    using type = typename tmp<typename make_integer_sequence_impl<T, N-1>::type>::type;
};

template <typename T, T N>
struct make_integer_sequence_impl<T, N, typename std::enable_if<N==0>::type>
{ using type = integer_sequence<T>; };

template <typename T, T N>
using make_integer_sequence = typename make_integer_sequence_impl<T, N>::type;

Berny

Answer 7

Here is another implementation technique (for T=size_t), it uses C++17 fold expressions and bitwise generation (i.e. O(log(N)):

template <size_t... Is>
struct idx_seq {
  template <size_t N, size_t Offset>
  struct pow2_impl {
    using type = typename idx_seq<Is..., (Offset + Is)...>::template pow2_impl<N - 1, Offset + sizeof...(Is)>::type;
  };
  template <size_t _> struct pow2_impl<0, _> { using type = idx_seq; };
  template <size_t _> struct pow2_impl<(size_t)-1, _> { using type = idx_seq<>; };

  template <size_t Offset>
  using offset = idx_seq<(Offset + Is)...>;
};

template <size_t N>
using idx_seq_pow2 = typename idx_seq<0>::template pow2_impl<N, 1>::type;

template <size_t... Is, size_t... Js>
constexpr static auto operator,(idx_seq<Is...>, idx_seq<Js...>)
  -> idx_seq<Is..., Js...>
{ return {}; }

template <size_t N, size_t Mask, size_t... Bits>
struct make_idx_seq_impl {
  using type = typename make_idx_seq_impl<N, (N >= Mask ? Mask << 1 : 0), Bits..., (N & Mask)>::type;
};

template <size_t N, size_t... Bits>
struct make_idx_seq_impl<N, 0, Bits...> {
  using type = decltype((idx_seq<>{}, ..., typename idx_seq_pow2<Bits>::template offset<(N & (Bits - 1))>{}));
};

template <size_t N>
using make_idx_seq = typename make_idx_seq_impl<N, 1>::type;

Wiener

Brilliant👌. I came up with a very similar technique 😁, around the same time; even the same decltype((idx,...)) trick. It is the superior solution. Keeps the number of template instantiations lower too; M*log(N) is a generous upper bound, where M is the number of user requested instantiations, and N is the maximum among the values for which the user requested instances. Later, however I found a way to get rid of the fold expression and perform a simple concatenation. So unfortunate ☹️ this answer showed up at the bottom of the list. It could just be the top-rated accepted answer. – Undersell

By the way Bits... in make_idx_seq_impl, must become shift counts instead of binary powers; because idx_seq_pow2 works with shift counts(not binary powers). – Undersell

Answer 8

Here is a very simple solution implemented with recursion based on tag dispatching

template <typename T, T M, T ... Indx>
constexpr std::integer_sequence<T, Indx...> make_index_sequence_(std::false_type)
{
    return {};
}

template <typename T, T M, T ... Indx>
constexpr auto make_index_sequence_(std::true_type)
{
    return make_index_sequence_<T, M, Indx..., sizeof...(Indx)>(
            std::integral_constant<bool, sizeof...(Indx) + 1 < M>());
}

template <size_t M>
constexpr auto make_index_sequence()
{
    return make_index_sequence_<size_t, M>(std::integral_constant<bool, (0 < M)>());
}

However, this solution can not be extended to C++11.

Negligent