Modern C++:初始化constexpr表

Question

假设我有一个类X,哪个功能需要很多常量表值,比如一个数组A[1024].我有一个f计算其值的重复函数,就像

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

假设这A[0]是一个已知常量,因此数组的其余部分也是常量.使用现代C++的功能预先计算这些值的最佳方法是什么,并且没有使用此数组的硬编码值存储文件？我的解决方法是一个const静态虚拟变量:

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

从C++ 14开始,函数for中允许循环constexpr.而且,由于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

Answer 2

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

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

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

但我提出的方式有很多优点:

1. 编译器不会占用所有内存并且无法扩展模板,这是非常安全的.
2. 编译速度明显加快
3. 使用数组时使用C++ - ish接口
4. 代码通常更具可读性

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

更新

感谢Navin,我找到了一种方法来强制对数组进行编译时评估.

如果按值返回,可以强制它在编译时运行: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.我也更新了测量结果.

在装配输出上

正如我之前提到的,模板变体更简洁.请在这里查看更多细节.

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

main:
  mov eax, 1024
  ret

而对于std :: array变量我有一个循环:

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

使用std :: array并按值返回,汇编与包含模板的版本相同:

main:
  mov eax, 1024
  ret

关于编译速度

我比较了这两个变种:

测试2.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.