👨🏿‍🌾 👩🏼‍🤝‍👨🏾 🤚 Memorización en cálculos de tiempo de compilación en C ++ 💇🏿 🤰🏼 👩🏾‍🌾

Los programadores de C ++ saben bien (¡con suerte!) Que se pueden realizar una variedad de cálculos en tiempo de compilación. Si tan solo estos cálculos fueran "limpios", sin efectos secundarios. Esto se hace en plantillas y funciones constexpr.

Una expresión pura significa que no importa cuántas veces intentemos evaluarla, obtendremos el mismo resultado. Por tanto, por motivos de eficacia, conviene memorizar el resultado para no volver a realizar el mismo trabajo. Pero, ¿qué tan bien lo hace el compilador?

Para las pruebas de estrés, tomemos una fórmula ingenua de Fibonacci:

f(n) = (n < 2) ? 1 : f(n-1) + f(n-2)

Nos interesa por varias razones:

la profundidad de recursión depende linealmente de n
sin memorización, se reduce a la suma de f (n) unos, y esto, recordemos, es el exponente en la base de la proporción áurea
con memorización - para memorizar n valores

¿Cómo calculo esta fórmula en tiempo de compilación?

Hay 3 técnicas para esto.

La primera, conocida desde hace mucho tiempo (desde C ++ 98): plantillas con parámetros enteros y miembros constantes. (En la antigüedad, se usaban enumeraciones, luego aparecieron las constantes estáticas).

//     ,     
template<unsigned n> struct int_ { static constexpr unsigned value = n; };

template<unsigned n> struct f;

template<> struct f<0> : int_<1> {};
template<> struct f<1> : int_<1> {};
template<unsigned n> struct f : int_< f<n-1>::value + f<n-2>::value > {};

template<unsigned n> constexpr unsigned F = f<n>::value;

(usaremos unsigned, porque no necesitamos los valores reales de los números para los experimentos, y no queremos encontrarnos con un desbordamiento de enteros).

La segunda técnica estuvo disponible en C ++ 11: funciones constexpr.

constexpr unsigned f(unsigned n) {
  return n < 2 ? f(n-1) + f(n-2);
}

template<unsigned n> constexpr unsigned F = f(n);

, . : . , , ( ).

constexpr unsigned f(unsigned n) {
  unsigned a = 1, b = 1;
  for (i = 1; i < n; ++i) {
    unsigned c = a + b;
    a = b; b = c;
  }
  return b;
}

— , — expression template. , . , , expression template (, ). .

//   ,  
template<unsigned n> struct int_ { static constexpr unsigned value = n; };

//    expression template,     :
template<unsigned x, unsigned y> auto operator + (int_<x>, int_<y>) {
  return int_<x+y>{};
}

template<unsigned n> auto f(int_<n> /*arg*/) {
  if constexpr (n < 2) {
    return int_<1>{};
  } else {
    //    (expression template !)
    return f(int_<n-1>{}) + f(int_<n-2>{});
    
    //   - ,       ,
    //      :
    return decltype( f(int_<n-1>{}) + f(int_<n-2>{}) ){};
    //  :
    using t1 = decltype(f(int_<n-1>{}));
    using t2 = decltype(f(int_<n-2>{}));
    return int_<t1::value + t2::value>{};
  }
}

template<unsigned n> constexpr unsigned F = decltype(f(int_<n>{}))::value;

, : / , if constexpr

, C++17. . ( : , ; , , ).

: constexpr. .

, , .

(instantiate) n, n-1 n-2, , , n-2 n-3, 1 0, 2 1 ( ), 3 2 ( ), . , .

, — .

gcc -ftemplate-depth

900, clang -ftemplate-backtrace-limit

— 1024.

— . ? , : . expression template .

, constexpr . , : gcc -fconxtexpr-depth

, clang — -fconstexpr-backtrace-limit

, 512.

, .

gcc 9.3 ! F<512>

F<1022>

, .

, 10.1, gcc . -fconstexpr-ops-limit

, 33554432.

?

F<512>

F<1022>

— ? -? , .

template<unsigned n> struct f;
template<unsigned n> struct g;

template<> struct f<0> : int_<1> {};
template<> struct f<1> : int_<1> {};
template<unsigned n> struct f : int_< f<n-1>::value + f<n-2>::value > {};

template<> struct g<0> : int_<1> {};
template<> struct g<1> : int_<1> {};
template<unsigned n> struct g : int_< g<n-2>::value + g<n-1>::value > {};

template<unsigned n> constexpr unsigned F = f<n>::value;
template<unsigned n> constexpr unsigned G = g<n>::value;

1, — 2. , , , .

expression template.

GodBolt

gcc.godbolt.org

gcc 10.1
clang 11.0.0 — expression template
clang 9.0.0 — expression template, , : -
gcc 9.3 — !

		gcc 9.3	gcc 10.1	clang 11.0.0
class template (CT)	CT::F	899	899	1024
class template (CT)	CT::G	1798	1798	2048
expression template (ET)	ET::F	899	899	702
expression template (ET)	ET::G	1796	1796	1402
constexpr (CE)	CE::F	512	35	26
constexpr (CE)	CE::G	1022	41	26

#include <iostream>

template<unsigned n> struct int_ { static constexpr unsigned value = n; };

template<unsigned x, unsigned y> auto operator + (int_<x>, int_<y>) {
  return int_<x+y>{};
}

namespace CT {  // class template

template<unsigned n> struct f;
template<> struct f<0> : int_<1> {};
template<> struct f<1> : int_<1> {};
template<unsigned n> struct f : int_<f<n-1>::value + f<n-2>::value> {};

template<unsigned n> struct g;
template<> struct g<0> : int_<1> {};
template<> struct g<1> : int_<1> {};
template<unsigned n> struct g : int_<g<n-2>::value + g<n-1>::value> {};

template<unsigned n> constexpr unsigned F = f<n>::value;
template<unsigned n> constexpr unsigned G = g<n>::value;

}  // namespace CT

namespace ET {  // expression template

template<unsigned n> auto f(int_<n>) {
  if constexpr (n < 2) {
    return int_<1>{};
  } else {
    return f(int_<n-1>{}) + f(int_<n-2>{});
  }
}

template<unsigned n> auto g(int_<n>) {
  if constexpr (n < 2) {
    return int_<1>{};
  } else {
    return g(int_<n-2>{}) + g(int_<n-1>{});
  }
}

template<unsigned n> constexpr unsigned F = decltype(f(int_<n>{}))::value;
template<unsigned n> constexpr unsigned G = decltype(g(int_<n>{}))::value;

}  // namespace ET

namespace CE {  // constexpr

constexpr unsigned f(unsigned n) {
  return n < 2 ? 1 : f(n-1) + f(n-2);
}

constexpr unsigned g(unsigned n) {
  return n < 2 ? 1 : g(n-2) + g(n-1);
}

template<unsigned n> constexpr unsigned F = f(n);
template<unsigned n> constexpr unsigned G = g(n);

}  // namespace CE

int main() {
  std::cout << CT::F<899> << std::endl;
  std::cout << CT::G<1798> << std::endl;

  std::cout << ET::F<899> << std::endl;
  std::cout << ET::G<1796> << std::endl;

  std::cout << CE::F<35> << std::endl;
  std::cout << CE::G<35> << std::endl;
}

?

. , , constexpr' — -, , . , , .

. , .

" "

— , , , — , constexpr-, ... .

Función que cuenta el número de operaciones para calcular el número de Fibonacci

f(n, t) = n < 2 ? t+1 : f(n-1, f(n-2, t))
f(n) = f(n, 0)

Las plantillas de expresión se verán así.

template<unsigned n, unsigned t>
auto f(int_<n>, int_<t>) {
  if constexpr (n < 2) {
    return int_<t+1>{};
  } else {
    return f(int_<n-1>{}, f(int_<n-2>{}, int_<t>{}));
  }
}

int main() {
  std::cout << decltype(f(int_<30>{}, int_<0>{}))::value << std::endl;
}

Durante 26, el clang funcionó durante aproximadamente medio minuto. Por 30, engulló más de 8 gigabytes de memoria y convirtió mi computadora portátil en un intercambio, después de lo cual el experimento tuvo que detenerse.

Memorización en cálculos de tiempo de compilación en C ++

¿Cómo calculo esta fórmula en tiempo de compilación?

, , .

?

GodBolt

?

" "

More articles: