Modern C++: initialize constexpr tables

Question

Suppose I have a class X, which functionality requires a lot of constant table values, say an array A[1024]. I have a recurrent function f that computes its values, smth like

A[x] = f(A[x - 1]);

Suppose that A[0] is a known constant, therefore the rest of the array is constant too. What is the best way to calculate these values beforehand, using features of modern C++, and without storaging file with hardcoded values of this array? My workaround was a const static dummy variable:

const bool X::dummy = X::SetupTables();

bool X::SetupTables() {
    A[0] = 1;
    for (size_t i = 1; i <= A.size(); ++i)
        A[i] = f(A[i - 1]);
}

But I believe, it’s not the most beautiful way to go. Note: I emphasize that array is rather big and I want to avoid monstrosity of the code.

Why are you tagging both C++11 and C++1z? What do you mean _beuatiful_? — Passer By, Nov 14 '17 at 11:53
Possible duplicate of [Programmatically create static arrays at compile time in C++](https://stackoverflow.com/questions/2978259/programmatically-create-static-arrays-at-compile-time-in-c) Look at Georg Fritzsche's answer. You just need to define recursive `MetaFunc` structure. — freakish, Nov 14 '17 at 12:00
@freakish it looks alike, but wouldn’t it be an overkill for a huge array ~1024? I mean template instantiation depth? — Aleksandr Samarin, Nov 14 '17 at 12:09
@AleksandrSamarin The maximum template instantiation depth can be modified depending on your compiler. For gcc via `-ftemplate-depth=n` flag. Note that the C++11 standard sets the default at 1024. If the table is still too big then you can pregenerate the entire table, save it as a C++ header file and just include it. — freakish, Nov 14 '17 at 12:13
If you are running into template depth issues, you can switch from linear visit pattern to a binary tree. You can arrange this so it still visits all elements in the same order, but has a recursion depth of only `lg N` instead of `N`. — Ben Voigt, Nov 14 '17 at 16:19

score 28 · Accepted Answer · answered Nov 14 '17 at 15:07

Since C++14, for loops are allowed in constexpr functions. Moreover, since C++17, std::array::operator[] is constexpr too.

So you can write something like this:

template<class T, size_t N, class F>
constexpr auto make_table(F func, T first)
{
    std::array<T, N> a {first};
    for (size_t i = 1; i < N; ++i)
    {
        a[i] = func(a[i - 1]);
    }
    return a;
}

Example: https://godbolt.org/g/irrfr2

mcsim · Answer 2 · 2017-11-14T16:28:46.057

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:

It is quite safe that the compiler will not eat up all your memory and fails to expand the template.
The compilation speed is significantly faster
You use C++-ish interface when you use an array
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.

This answer is good is well! _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_. Could you please clarify this line? — Aleksandr Samarin, Nov 14 '17 at 15:07
[It is just a loop at run-time](https://godbolt.org/g/Y3tEUY), this is why the compile time is O(1). — Maxim Egorushkin, Nov 14 '17 at 15:17
You can force it to run at compile time if you return by value: `std::array A = init();` — Navin, Nov 14 '17 at 16:04

Maxim Egorushkin · Answer 3 · 2017-11-14T12:45:24.893

4

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;

edited Nov 14 '17 at 12:45

answered Nov 14 '17 at 12:27

Maxim Egorushkin

131,725
17
180
271

`{A[Idxs] = f(A[Idxs - 1])...}` I didn't know this magic trick! – YSC Nov 14 '17 at 12:31
And I thought fold expression only worked with specific binary operators. C++17 houray! – YSC Nov 14 '17 at 12:33
@YSC This is not a C++17 fold expression, rather C++11 template value pack expansion. – Maxim Egorushkin Nov 14 '17 at 12:34
Epiphany! Nice answer. It requires [-std=c++1z](http://coliru.stacked-crooked.com/a/f638f4d374b1fe21) though. [-std=c++14](http://coliru.stacked-crooked.com/a/63f7ee811d0b12d8) is not enough. – YSC Nov 14 '17 at 12:38
I love the compactness of it, but I have one question: if `A` is a static member of some class, where should I put `init` function? – Aleksandr Samarin Nov 14 '17 at 12:39
@YSC I compile it with `-std=c++14`. `std::integer_sequence` is a C++14 feature, although it can be ported to C++11. – Maxim Egorushkin Nov 14 '17 at 12:40
2

@YSC `size_t` → `std::size_t`! – Konrad Rudolph Nov 14 '17 at 16:33
What's the point of `C`? It seems to me that `B` could be a namespace scoped static variable. – Matthieu M. Nov 14 '17 at 17:20
@MatthieuM. The point of `C` is demonstration of the use case the OP requiested. – Maxim Egorushkin Nov 14 '17 at 17:24
@KonradRudolph Ho! At least! It's a good thing the SL implementation of GCC no longer pollute the global namespace! – YSC Nov 15 '17 at 09:29

Massimiliano Janes · Answer 4 · 2017-11-14T13:55:11.710

4

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.

edited Nov 14 '17 at 13:55

answered Nov 14 '17 at 13:37

Massimiliano Janes

5,524
1
10
22

Modern C++: initialize constexpr tables

4 Answers4

Linked