现代 C++：初始化 constexpr 表

Question

假设我有一个 class X，它的功能需要很多常量 table 值，比如一个数组 A[1024]。我有一个循环函数 f 来计算它的值，就像

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

假设A[0]是一个已知常量，那么数组的其余部分也是常量。预先计算这些值的最佳方法是什么，使用现代 C++ 的特性，并且不存储包含该数组硬编码值的文件？我的解决方法是使用 const static 虚拟变量：

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

但我相信，这不是最美丽的方式。注意：我强调数组相当大，我想避免代码的畸形。

Answer 1

一个例子：

#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>{});
}

需要 -ftemplate-depth=1026 g++ 命令行开关。

如何使其成为静态成员的示例：

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;

Answer 2

只是为了好玩，一个 c++17 紧凑的单行代码可能是（需要一个 std::array A，或者一些其他的 memory-contiguous 类似元组） :

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

请注意，这也可以用在 constexpr 函数中。

也就是说，从 c++14 开始，我们可以在 constexpr 函数中使用循环，因此我们可以编写一个直接返回 std::array 的 constexpr 函数，（几乎）以通常的方式编写。

Answer 3

我认为这种方式更具可读性：

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

我需要做一个免责声明，对于大数组大小，不能保证在恒定时间内生成数组。并且接受的答案更有可能在模板扩展期间生成完整数组。

但我提出的方法有很多优点：

编译器不会把你所有的内存都吃光而无法扩展模板，这是非常安全的。
编译速度明显加快
使用数组时使用 C++-ish 接口
代码通常更具可读性

在一个特定的例子中，当你只需要一个值时，带有模板的变体只为我生成了一个数字，而带有 std::array 的变体生成了一个循环。

更新

感谢 Navin，我找到了一种强制对数组进行编译时评估的方法。

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

所以稍微修改一下代码如下：

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

要编译这个需要 C++17 支持，否则来自 std::array 的 operator [] 不是 constexpr。我也更新测量值。

汇编输出

正如我之前提到的，模板变体更简洁。请查看 here 了解更多详情。

在模板变体中，当我只选择数组的最后一个值时，整个程序集如下所示：

main:
  mov eax, 1024
  ret

虽然对于 std::array 变体我有一个循环：

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

std::array 和 return 按值 assemble 与模板版本相同：

main:
  mov eax, 1024
  ret

关于编译速度

我比较了这两个变体：

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

结果是：

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

我是如何生成的：

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

如果启用优化，使用模板的代码速度会更差：

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

我是如何生成的：

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

我的 gcc 版本：

$ 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.

Answer 4

自 C++14 起，constexpr 函数中允许 for 循环。此外，自 C++17 起，std::array::operator[] 也是 constexpr。

所以你可以这样写：

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

示例：https://godbolt.org/g/irrfr2

现代 C++：初始化 constexpr 表

Modern C++: initialize constexpr tables

c++

precompile

constexpr

c++11

c++17