C++11: Compile-time Array with Logarithmic Evaluation Depth

Question

One way to implement a C++11 array that has its elements initialized by a function of their index calculated by the compiler and have the results stored in the data section (.rodata) of the application image is to use templates, partial specialization and constexpr as follows:

#include <iostream>
#include <array>
using namespace std;

constexpr int N = 1000000;
constexpr int f(int x) { return x*2; }

typedef array<int, N> A;

template<int... i> constexpr A fs() { return A{{ f(i)... }}; }

template<int...> struct S;

template<int... i> struct S<0,i...>
{ static constexpr A gs() { return fs<0,i...>(); } };

template<int i, int... j> struct S<i,j...>
{ static constexpr A gs() { return S<i-1,i,j...>::gs(); } };

constexpr auto X = S<N-1>::gs();

int main()
{
        cout << X[3] << endl;
}

This doesn't work for large values of N:

error: constexpr evaluation depth exceeds maximum of 512 

This is because of the head-tail style of recursive template evaluation, that has linear depth in terms of N.

Is there a way to do it such that the evaluation depth is logarithmic in terms of N, rather than linear? (and hence would avoid the default depth limit)

Answer 1

In c++14 with general constexpression function needn't any sequence, make_sequence

static constexpr int f(int i) noexcept { return i * 2; }

template< int N, typename F >
static constexpr std::array<int,N> generate_array( F fo ) noexcept
{
     std::array< int, N > result{}; // init with zero
     int i = 0; 
     for( auto& x : result) x = fo(++i);

     return result;
}

// test
constexpr auto arr = generate_array<10>( f );

Only has one problem, there is no compiler which can compile it :)

Answer 2

If what you're using in the code is a weird form of the indices trick, here's an implementation that has O(log N) instantiations:

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

// example

template<unsigned... Is>
void f(seq<Is...>);

int main(){
  f(gen_seq<6>());
}

Live example.

Answer 3

The only tail recursive template, that's causing the linear template instantiation depth, is the construction of the list of integers in the template parameter list of S.

This can be done in logarithmic instantiation depth, as you suggest:

template <int ... Ints> struct seq;

template <int Start, int End> 
struct range
{
  typedef concat_seq<range<Start, Start+(End-Start)/2>::type, range<Start+(End-Start)/2, End>::type>::type type;
};

template<int Singleton>
struct range<Singleton, Singleton+1>
{
  typedef seq<Singleton> type;
};

template <int NoSingleton>
struct range<NoSinleton, NoSingleton>
{
  typedef seq<> type;
};

Add a bunch of typenames where appropriate, implement concat_seq (easy), extract the argument list for fs from range<0, N>::type and there you go.