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.

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>{};

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 http://stackoverflow.com/a/17426611/410767 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> >'

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(){}

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).