Modern C++: initialize constexpr tables

I think this way is more readable:

#include <array> constexpr int f(int a) { return a + 1; } constexpr void init(auto &A) { A[0] = 1; for (int i = 1; i < A.size(); i++) { A[i] = f(A[i - 1]); } } int main() { std::array<int, 1024> A; A[0] = 1; init(A); } 

I need to make a disclaimer, that for big array sizes it is not guaranteed to generate array in constant time. And the accepted answer is more likely to generate the full array during template expansion.

But the way I propose has number of advantages:

1. It is quite safe that the compiler will not eat up all your memory and fails to expand the template.
2. The compilation speed is significantly faster
3. You use C++-ish interface when you use an array
4. The code is in general more readable

In a particular example when you need only one value, the variant with templates generated for me only a single number, while the variant with std::array generated a loop.

Update

Thanks to Navin I found a way to force compile time evaluation of the array.

You can force it to run at compile time if you return by value: std::array A = init();

So with slight modification the code looks as follows:

#include <array> constexpr int f(int a) { return a + 1; } constexpr auto init() { // Need to initialize the array std::array<int, SIZE> A = {0}; A[0] = 1; for (unsigned i = 1; i < A.size(); i++) { A[i] = f(A[i - 1]); } return A; } int main() { auto A = init(); return A[SIZE - 1]; } 

To have this compiled one needs C++17 support, otherwise operator [] from std::array is not constexpr. I also update the measurements.

On assembly output

As I mentioned earlier the template variant is more concise. Please look here for more detail.

In the template variant, when I just pick the last value of the array, the whole assembly looks as follows:

main: mov eax, 1024 ret 

While for std::array variant I have a loop:

main: subq $3984, %rsp movl $1, %eax .L2: leal 1(%rax), %edx movl %edx, -120(%rsp,%rax,4) addq $1, %rax cmpq $1024, %rax jne .L2 movl 3972(%rsp), %eax addq $3984, %rsp ret 

With std::array and return by value the assemble is identical to version with templates:

main: mov eax, 1024 ret 

On compilation speed

I compared these two variants:

test2.cpp:

#include <utility> constexpr int f(int a) { return a + 1; } template<int... Idxs> constexpr void init(int* A, std::integer_sequence<int, Idxs...>) { auto discard = {A[Idxs] = f(A[Idxs - 1])...}; static_cast<void>(discard); } int main() { int A[SIZE]; A[0] = 1; init(A + 1, std::make_integer_sequence<int, sizeof A / sizeof *A - 1>{}); } 

test.cpp:

#include <array> constexpr int f(int a) { return a + 1; } constexpr void init(auto &A) { A[0] = 1; for (int i = 1; i < A.size(); i++) { A[i] = f(A[i - 1]); } } int main() { std::array<int, SIZE> A; A[0] = 1; init(A); } 

The results are:

| Size | Templates (s) | std::array (s) | by value | |-------+---------------+----------------+----------| | 1024 | 0.32 | 0.23 | 0.38s | | 2048 | 0.52 | 0.23 | 0.37s | | 4096 | 0.94 | 0.23 | 0.38s | | 8192 | 1.87 | 0.22 | 0.46s | | 16384 | 3.93 | 0.22 | 0.76s | 

How I generated:

for SIZE in 1024 2048 4096 8192 16384 do echo $SIZE time g++ -DSIZE=$SIZE test2.cpp time g++ -DSIZE=$SIZE test.cpp time g++ -std=c++17 -DSIZE=$SIZE test3.cpp done 

And if you enable optimizations, the speed of code with template is even worse:

| Size | Templates (s) | std::array (s) | by value | |-------+---------------+----------------+----------| | 1024 | 0.92 | 0.26 | 0.29s | | 2048 | 2.81 | 0.25 | 0.33s | | 4096 | 10.94 | 0.23 | 0.36s | | 8192 | 52.34 | 0.24 | 0.39s | | 16384 | 211.29 | 0.24 | 0.56s | 

How I generated:

for SIZE in 1024 2048 4096 8192 16384 do echo $SIZE time g++ -O3 -march=native -DSIZE=$SIZE test2.cpp time g++ -O3 -march=native -DSIZE=$SIZE test.cpp time g++ -O3 -std=c++17 -march=native -DSIZE=$SIZE test3.cpp done 

My gcc version:

$ g++ --version g++ (Debian 7.2.0-1) 7.2.0 Copyright (C) 2017 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 

One example:

#include <utility> constexpr int f(int a) { return a + 1; } template<int... Idxs> constexpr void init(int* A, std::integer_sequence<int, Idxs...>) { auto discard = {A[Idxs] = f(A[Idxs - 1])...}; static_cast<void>(discard); } int main() { int A[1024]; A[0] = 1; init(A + 1, std::make_integer_sequence<int, sizeof A / sizeof *A - 1>{}); } 

Requires -ftemplate-depth=1026 g++ command line switch.

Example how to make it a static member:

struct B { int A[1024]; B() { A[0] = 1; init(A + 1, std::make_integer_sequence<int, sizeof A / sizeof *A - 1>{}); }; }; struct C { static B const b; }; B const C::b; 

just for fun, a c++17 compact one-liner might be ( requires an std::array A, or some other memory-contiguous tuple-like ):

std::apply( [](auto, auto&... x){ ( ( x = f((&x)[-1]) ), ... ); }, A ); 

note that this can be used in a constexpr function too.

That said, from c++14 we can use loops in constexpr functions, so we can write a constexpr function returning an std::array directly, written (almost) the usual way.