🔎 👩🏾‍🤝‍👨🏿 👃🏽 Memoização em cálculos de tempo de compilação em C ++ ◀️ 🙍🏾 🥋

Os programadores de C ++ sabem bem (espero!) Que uma variedade de cálculos podem ser executados em tempo de compilação. Se ao menos esses cálculos fossem "limpos", sem efeitos colaterais. Isso é feito em modelos e funções constexpr.

Uma expressão pura significa que não importa quantas vezes tentemos avaliá-la, obteremos o mesmo resultado. Portanto, por razões de eficiência, é aconselhável memorizar o resultado para não fazer o mesmo trabalho uma segunda vez. Mas quão bem o compilador faz isso?

Para o teste de estresse, vamos usar uma fórmula ingênua de Fibonacci:

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

Estamos interessados nele por vários motivos:

profundidade de recursão linearmente depende de n
sem memoização, ele se reduz à soma de f (n) uns, e este, lembre-se, é o expoente na base da proporção áurea
com memoização - para memorizar n valores

Como faço para calcular esta fórmula em tempo de compilação?

Existem 3 técnicas para isso.

O primeiro, conhecido há muito tempo (desde C ++ 98): templates com parâmetros inteiros e membros constantes. (Antigamente, enums eram usados e, em seguida, constantes estáticas apareciam).

//     ,     
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 não precisamos dos valores reais dos números para os experimentos e não queremos correr para um estouro de inteiro).

A segunda técnica tornou-se disponível em C ++ 11: funções 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-, ... .

Função que conta o número de operações para calcular o número de Fibonacci

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

Os modelos de expressão terão esta aparência.

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

Para 26 - o clang funcionou por cerca de meio minuto. Para 30, ele engoliu mais de 8 gigabytes de memória e fez meu laptop fazer uma troca, após a qual o experimento teve que ser interrompido.

Memoização em cálculos de tempo de compilação em C ++

Como faço para calcular esta fórmula em tempo de compilação?

, , .

?

GodBolt

?

" "

More articles: