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.

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

Solution 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> >'

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

Solution 4

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

Solution 5

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

View more solutions

Comments

[Cassio Neri]

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.

[Yakk - Adam Nevraumont]

Should that really be called Concat?

[Khurshid]

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.

[Yakk - Adam Nevraumont]

@Xeo 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.

[Khurshid]

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 !

[TemplateRex]

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

[jcai]

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

[Jonathan Wakely]

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.

[Xeo]

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

[Jonathan Wakely]

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.

[einpoklum]

Why is this index_sequence rather than integer_sequence?

[Tony Delroy]

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

[Martin Bonner supports Monica]

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

[David]

@einpoklum 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)

[김선달]

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