C++ moderno: inicializar tablas constexpr

c++11 c++17

Question

Supongamos que tengo una clase X , cuya funcionalidad requiere muchos valores de tabla constantes, digamos una matriz A[1024] . Tengo una función recurrente f que calcula sus valores, como smth

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

Supongamos que A[0] es una constante conocida, por lo tanto, el resto de la matriz también es constante. ¿Cuál es la mejor manera de calcular estos valores de antemano, utilizando las características de C ++ moderno y sin almacenar archivos con valores codificados de esta matriz? Mi solución fue una variable dummy estática constante:

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

Pero creo que no es la forma más hermosa de ir. Nota: enfatizo que la matriz es bastante grande y quiero evitar la monstruosidad del código.

Answer 1

Creo que esta forma es más legible:

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

Necesito hacer un descargo de responsabilidad, ya que para tamaños de matriz grandes no se garantiza que genere matriz en tiempo constante. Y es más probable que la respuesta aceptada genere la matriz completa durante la expansión de la plantilla.

Pero la forma en que propongo tiene varias ventajas:

1. Es bastante seguro que el compilador no se consumirá toda la memoria y no podrá expandir la plantilla.
2. La velocidad de compilación es significativamente más rápida.
3. Utiliza la interfaz C ++ - ish cuando usa una matriz
4. El código es en general más legible.

En un ejemplo particular, cuando necesita solo un valor, la variante con plantillas generadas para mí solo un número, mientras que la variante con std::array generó un bucle.

Actualizar

Gracias a Navin, encontré una manera de forzar la evaluación del tiempo de compilación de la matriz.

Puede forzar que se ejecute en tiempo de compilación si devuelve por valor: std :: array A = init ();

Así que con una ligera modificación el código se ve como sigue:

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

Para tener este compilado se necesita soporte para C ++ 17, de lo contrario el operador [] de std :: array no es constexpr. También actualizo las medidas.

En la salida de montaje

Como mencioné anteriormente, la variante de plantilla es más concisa. Por favor, busque here para más detalles.

En la variante de plantilla, cuando acabo de elegir el último valor de la matriz, todo el ensamblaje tiene el aspecto siguiente:

main:
  mov eax, 1024
  ret

Mientras que para std :: array variante tengo un bucle:

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

Con std :: array y retorno por valor, el ensamblaje es idéntico a la versión con plantillas:

main:
  mov eax, 1024
  ret

En velocidad de compilación

Comparé estas dos variantes:

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

Los resultados son:

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

Cómo generé:

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

Y si habilita las optimizaciones, la velocidad del código con la plantilla es aún peor:

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

Cómo generé:

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

Mi versión 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 2

Desde C ++ 14, los bucles están permitidos en constexpr funciones constexpr . Además, como C ++ 17, std::array::operator[] es constexpr .

Así que puedes escribir algo como esto:

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

Ejemplo: https://godbolt.org/g/irrfr2

Answer 3

Un ejemplo:

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

Requiere -ftemplate-depth=1026 g++ interruptor de línea de comando.

Ejemplo de cómo hacerlo un miembro estático:

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 4

solo por diversión, un c ++ 17 compacto de una sola línea podría ser (requiere un std :: array A, u otro tipo de tupla contigua a la memoria ):

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

tenga en cuenta que esto también se puede utilizar en una función constexpr.

Dicho esto, desde c ++ 14 podemos usar bucles en las funciones constexpr, por lo que podemos escribir una función constexpr que devuelva un std :: array directamente, escrito (casi) de la forma habitual.