Современный С++: инициализировать таблицы constexpr

Предположим, что у меня есть класс X, для которого функциональность требует много значений постоянной таблицы, например массив A[1024]. У меня есть рекуррентная функция f, которая вычисляет ее значения, smth like

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

Предположим, что A[0] - известная константа, поэтому остальная часть массива также является константой. Каков наилучший способ заранее рассчитать эти значения, используя функции современного С++ и без хранения файла с жестко заданными значениями этого массива? Моим обходным решением была константная статическая фиктивная переменная:

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

Но я верю, что это не самый красивый способ пойти. Примечание. Я подчеркиваю, что массив довольно большой, и я хочу избежать чудовищности кода.

Ответы

Ответ 1

Так как С++ 14, for разрешены в constexpr. Более того, поскольку С++ 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

Ответ 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);
}

Мне нужно сделать отказ от ответственности, что для больших размеров массива не гарантируется генерация массива в постоянное время. И принятый ответ скорее сгенерирует полный массив при расширении шаблона.

Но способ, который я предлагаю, имеет ряд преимуществ:

  • Совершенно безопасно, что компилятор не будет уничтожать всю вашу память и не сможет расширить шаблон.
  • Скорость компиляции значительно быстрее
  • Вы используете интерфейс С++ - ish при использовании массива
  • Код в целом более читабельный

В конкретном примере, когда вам нужно только одно значение, вариант с шаблонами генерировал для меня только один номер, а вариант с 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];
}

Чтобы скомпилировать эту команду, нужна поддержка С++ 17, иначе оператор [] из std:: array не является 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

При скорости компиляции

Я сравнивал эти два варианта:

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.

Ответ 3

Один пример:

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

Ответ 4

просто для удовольствия, компактный однострочный С++ 17 может быть (требуется std:: array A или какой-то другой подобный памяти кортеж):

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

обратите внимание, что это также можно использовать и в функции constexpr.

Тем не менее, из С++ 14 мы можем использовать циклы в функциях constexpr, поэтому мы можем написать функцию constexpr, возвращающую std:: array напрямую, написанную (почти) обычным способом.