如何减少constexpr函数的编译时间？

Question

假设我们想要在编译时构建一个非平凡的表格

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];
}

只需要稍微一点点就能让编译时间超过极限。另一种方法是通过脚本生成表格作为源代码，显然这种方法要好得多。

如何减少此类函数的编译时间？

---

一些动机

constexpr函数与常规函数有很大的不同，明显表现在它们比普通函数执行得慢得多。除了由编译器执行外，它们还进行边界检查、溢出检查以及几乎所有防止UB的检查。我怀疑这使得从常规函数中获得的大部分直觉都变得无用了。

- Passer By

---

必须在编译时完成吗？您试图解决的真正问题是什么？有哪些用例？ - Some programmer dude

在本地运行它。您的本地计算机上没有* top *（或超时）。 - Codo

@Someprogrammerdude 不是。但原问题引起了我的兴趣。另外，我可以想到一个特定的constexpr解析器，我曾经试图在编译时构建东西。这对于folly/Format肯定是个问题。 - Passer By

@Codo 我的意思是它会使编译时间变得非常长。 - Passer By

我在想预编译头文件是否在这里有用？（它们不会直接减少编译时间，但是通过缓存第一次编译的结果以供重复使用，它们可以减少重新编译代码的次数） - Jeremy Friesner

Answer 1

我猜编译器只是优化以下几点，所以你可能得不到任何好处，但：

1）m ^ 42和m % 420不依赖于n，因此可以在内部循环之外计算它们

2）如果我没记错的话，

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

并且

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

3）您可以尝试在auto变量中添加一些const。

因此，您可以尝试使用以下代码：

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

如果这个方法有效，你可以尝试在 x % m 上工作，将与 n 无关的 x 组件（m42 - m）和有关的组件（n << 3）拆分开来，这样你就可以在内部循环之外计算出 x % m 的一部分。

- max66

---

(x + m) % m 可以防止出现负数。变量提升是优化器执行的其中一项操作。我相信在优化过程中，const 关键字会被完全忽略，因为它们的 SSA 形式是相同的。最后，这些都适用于运行时代码，但由于 constexpr 函数的工作方式和它们运行速度极慢，我怀疑它们之间存在很大差异，这些建议不一定适用。 - Passer By

作为轶事证据，我无法察觉这个版本和原始版本之间的任何区别。 - Passer By

@PasserBy - "防止负值" - Ops; 我没有考虑到。但是...所以你应该写x = m42 + (n << 3))，然后， ((x - m) ^ y)；如果我没记错的话， y 不能为负数。 - max66