How do I reduce compile times for constexpr functions?

user_4832499 0
Viewed 186

Suppose we want to build a non-trivial table at compile time

template<int N, int M>
constexpr auto foo()
{
    std::array<std::array<int, N>, M> a = {};
    for(int m = 1; m < M; m++)
        for(int n = 1; n < N; n++)
        {
            // For exposition only
            auto x = (m ^ 42) + (n << 3) - m;
            auto y = (n ^ 420) + (m % 420);
            a[m][n] = (a[(x + m) % m][(y + n) % n] + (x ^ y)) % 0xFACADE;
        }
    return a;
}

constexpr auto bar(int n, int m)
{
    constexpr auto dim = /* something */;
    constexpr auto table = foo<dim, dim>();
    return table[n][m];
}

It doesn't take much to push compile times over the top. The alternative is to generate the table as source code via a script, which is obviously much less nice.

How do I reduce the compile times such functions?

Some motivation

constexpr functions differ hugely from regular functions, evident by the extreme slowness compared to regular functions. Aside from being executed by the compiler, they have bounds checking, overflow checking and pretty much all UB preventing checks in place. I suspect this renders most intuition gathered from regular functions useless.

constexpr optimization c++
1 Answers

I suppose the compiler just optimize the following points, so probably you get no advantages, but:

1) m ^ 42 and m % 420 doesn't depends from n, so you can compute they outside the inner loop

2) if I'm not wrong,

(x + m) % m  ==  x % m + m % m
             ==  x % m + 0
             ==  x % m

and

(y + n) % n  ==  y % n + n % n
             ==  y % n + 0
             ==  y % n

3) you can try adding some const to auto variables.

So you can try with

template <int N, int M>
constexpr auto foo ()
{
    std::array<std::array<int, N>, M> a = {};

    for(int m = 1; m < M; m++)
    {
        auto const m42 = m ^ 42;
        auto const m420 = m % 420;

        for(int n = 1; n < N; n++)
        {
            // For exposition only
            auto const x = m42 + (n << 3) - m;
            auto const y = (n ^ 420) + m420;
            a[m][n] = (a[x % m][y % n] + (x ^ y)) % 0xFACADE;
        }
    }
    return a;
}

If this works, you can try working over x % m, splitting components of x that arn't dependent from n (m42 - m) and the dependent one (n << 3), so you can compute part of x % m outside the inner loop.

user_60226560
Related