How to initialize a constexpr multidimensional array at compile time?

Question

I am trying to initialize a multidimensional array, and while it's possible to populate this array once at startup, I really would prefer the array to be constexpr, so I am wondering if there is a way to get the compiler to do this for me, particularly since I can provide a constexpr function that takes parameters for each index and returns the value the array should be at the index.

eg:

constexpr bool test_values[64][64][64][64] = {
... // magic goes here
};

And I have a function constexpr bool f(int,int,int,int) that tells me what each element is supposed to be. I would prefer to access the entries via an array because it is faster to do an array lookup than it would be to call f() for non-const values.

Most of the other questions I've found relating to initializing an array at runtime used std::array rather than a C array, and none that I could find were multidimensional. I had tried unrolling the multidimensional array into a single dimensional one and using an std::array approach such as the what I found in one of the answers to this question, but I found that the resultant code produced by gcc 9.1 still populated the array once at startup, rather than the compiler generating the array directly.

Is there anything I can do to get the compiler to populate this kind of array, or am I stuck having to leave test_values as effectively non-constexpr, and initializing once at runtime?

EDIT:

for clarification, I am not intrinsically opposed to using an std::array instead of a builtin C-style array, but I do not think std::arrays are particularly friendly to multiple dimensions, and using a one-dimensional array obfuscates what my program needs to do (to be frank, I'll be willing to implement it as a one-dimensional std::array if I have to, but a multidimensional array feels less obfuscated than an equivalently sized one dimensional one that has been manually unwound, which is why I described it in terms of a multidimensional C array).

It's easy if you use `std::array` instead , is that an option for you? [This answer](https://stackoverflow.com/a/46779579/1505939) covers it — M.M, Jul 25 '19 at 22:43
Which version of C++ do you need to use? If you can use C++14, there's a really easy way to do it — Alecto Irene Perez, Jul 25 '19 at 22:43
C++ 14 is fine. I could unwind the array and use a single-dimensional std::array, as I said, but the approach that I tried (similar to what is linked above) which built an array inside of a constexpr function ended up still calling code at runtime to build the array rather than populating it at compile time. — markt1964, Jul 25 '19 at 22:48
Just curious, why do you need the array if you have a function that can do it at compile time ? You really need 16 MiB to be in the .rodata section of your binary ? Of which 7 bits in 8 are wasted anyway... — Arne J, Jul 25 '19 at 23:02
Because I will need to access the array with non const indexes as well as const ones, and accessing a single array member is faster than calling a complex function, even if it is a valid constexpr one, with non const arguments. — markt1964, Jul 25 '19 at 23:06
There is no way AFAIK if you insist on builtin arrays. But it is easy if you use `std::array`. — L. F., Jul 25 '19 at 23:56

score 3 · Accepted Answer · answered Jul 26 '19 at 06:11

C-array are not copyable, so using function is not really possible, but with std::array, you might create constexpr function (C++11 is more limited though)

constexpr auto generate()
{
    std::array<std::array<std::array<std::array<bool, 64>, 64>, 64>, 64> res{};

    for (int a = 0; a != 64; ++a) {
        for (int b = 0; b != 64; ++b) {
            for (int c = 0; c != 64; ++c) {
                for (int d = 0; d != 64; ++d) {
                     res[a][b][c][d] = f(a, b, c, d);
                }
            }
        }
    }

    return res;
}

constexpr auto test_values = generate();

If you really need C-array, you could wrap it in a struct and use similar code.

fifoforlifo · Answer 2 · 2019-07-26T05:45:23.337

With Meta-Programming

C++ doesn't allow returning literal arrays from functions (see https://stackoverflow.com/a/4264495) but as others stated, returning std::array<> results in functionally the same memory contents.

AFAICT the following approach generates prebaked constants (.rodata section) in gcc, msvc, and clang. I generalized to 3 dimensions. Unfortunately, it also blows up the compiler on any decent sized arrays (like 64x64x64) with a compiler error virtual memory exhausted: Cannot allocate memory. So I don't think it's very practical. [FWIW, 32x32x32 did succeed]

The basic approach is to create a parameter pack for each dimension containing the array indices 0,1,2,...,NumDim-1, with fixed indices for the larger dimensions. Then return a std::array whose contents are the indices applied to the Value(x, y, z) function, in a similar fashion to std::experimental::make_array.

https://godbolt.org/z/utDDBk

constexpr bool Value(size_t x, size_t y, size_t z)
{
    return (bool)((x ^ y ^ z) & 1);
}

namespace ValueArrayDetail {
    template <size_t NumX, size_t X>
    struct IteratorX
    {
        template <class... Xs>
        static constexpr std::array<bool, NumX> MakeXs(size_t z, size_t y, Xs... xs)
        {
            return IteratorX<NumX, X - 1>::template MakeXs(z, y, X - 1, xs...);
        }
    };
    template <size_t NumX>
    struct IteratorX<NumX, 0>
    {
        template <class... Xs>
        static constexpr std::array<bool, NumX> MakeXs(size_t z, size_t y, Xs... xs)
        {
            return { Value(xs, y, z)... };
        }
    };

    template <size_t NumX, size_t NumY, size_t Y>
    struct IteratorY
    {
        template <class... Ys>
        static constexpr std::array<std::array<bool, NumX>, NumY> MakeYs(size_t z, Ys... ys)
        {
            return IteratorY<NumX, NumY, Y - 1>::template MakeYs(z, Y - 1, ys...);
        }
    };
    template <size_t NumX, size_t NumY>
    struct IteratorY<NumX, NumY, 0>
    {
        template <class... Ys>
        static constexpr std::array<std::array<bool, NumX>, NumY> MakeYs(size_t z, Ys... ys)
        {
            return { IteratorX<NumX, NumX>::template MakeXs(z, ys)... };
        }
    };

    template <size_t NumX, size_t NumY, size_t NumZ, size_t Z>
    struct IteratorZ
    {
        template <class ... Zs >
        static constexpr std::array<std::array<std::array<bool, NumX>, NumY>, NumZ> MakeZs(Zs... zs)
        {
            return IteratorZ<NumX, NumY, NumZ, Z - 1>::template MakeZs(Z - 1, zs...);
        }
    };
    template <size_t NumX, size_t NumY, size_t NumZ>
    struct IteratorZ<NumX, NumY, NumZ, 0>
    {
        template <class... Zs>
        static constexpr std::array<std::array<std::array<bool, NumX>, NumY>, NumZ> MakeZs(Zs... zs)
        {
            return { IteratorY<NumX, NumY, NumY>::template MakeYs(zs)... };
        }
    };

    template <size_t NumX, size_t NumY, size_t NumZ>
    static constexpr std::array<std::array<std::array<bool, NumX>, NumY>, NumZ> MakeValues()
    {
        return IteratorZ<NumX, NumY, NumZ, NumZ>::template MakeZs();
    }
}

auto constexpr test_values = ValueArrayDetail::MakeValues<3, 4, 5>();

With Literal Constants

You can initialize test_values with literal constants, the same way as with a normal const array. Use nested brackets for each dimension. Example below is a bit lazyily written with only 4 values per row of 64, but it shows clearly in the output how each datum not explicitly specified has a default value of zero.

https://godbolt.org/z/cnzTn7

Input:

constexpr bool test_values[64][64][64][64] = {
    {
        {
            {true, false, false, true},
            {false, true, false, false},
            {true, true, true, true},
        },
        {
            {1, 0, 0, 1},
            {1, 1, 1, 0},
            {0, 0, 1, 1},
        },
    }
};

Output (x86-64 gcc 9.1):

test_values:
    .byte   1    <-- test_values[0][0][0][0]
    .byte   0
    .byte   0
    .byte   1
    .zero   60   <-- test_values[0][0][0][4 .. 63]
    .byte   0    <-- test_values[0][0][1][0]
    .byte   1
    .zero   62   <-- test_values[0][0][1][2 .. 63]
    .byte   1    <-- test_values[0][0][2][0]
    .byte   1
    .byte   1
    .byte   1
    .zero   60   <-- test_values[0][0][2][2 .. 63]
    .zero   3904
    .byte   1    <-- test_values[0][1][0][0]
    .byte   0
    .byte   0
    .byte   1
    .zero   60
    .byte   1
    .byte   1
    .byte   1
    .zero   61
    .byte   0
    .byte   0
    .byte   1
    .byte   1
    .zero   60
    .zero   3904
    .zero   253952
    .zero   16515072

While perhaps technically correct, it would be a bit tedious to have to enter all 16 million entries of the table. I am hoping to have the compiler generate the table for me. As I said, I can theoretically populate it at runtime, but I would like to make the table constexpr and built by the compiler. — markt1964, Jul 26 '19 at 02:26
Ah I see you're looking for a metaprogramming solution. Usually I suggest the low-tech solution of "generate the data table by running a separate program" but actually doing it within the bounds of C++ is an interesting challenge. — fifoforlifo, Jul 26 '19 at 05:02
One thing I did find, like the other posters, is that C++ does not permit returning a literal array by value. 8.3.5[dcl.fct]/6: Functions shall not have a return type of type array or function[...] https://stackoverflow.com/questions/4264304/how-to-return-an-array-from-a-function/4264495#4264495 — fifoforlifo, Jul 26 '19 at 05:03
See my additional comments at the end for clarification on using std::array, and why I did not describe the problem that way from the beginning — markt1964, Jul 26 '19 at 05:43

How to initialize a constexpr multidimensional array at compile time?

2 Answers2

With Meta-Programming

With Literal Constants