👴🏾 👾 👨🏼‍🔧 Mémorisation dans les calculs de compilation en C ++ 🚮 🏯 🚃

Les programmeurs C ++ savent bien (espérons-le!) Qu'une variété de calculs peuvent être effectués au moment de la compilation. Si seulement ces calculs étaient "propres", sans effets secondaires. Cela se fait dans les modèles et les fonctions constexpr.

Une expression pure signifie que peu importe le nombre de fois que nous essayons de l'évaluer, nous obtiendrons le même résultat. Par conséquent, pour des raisons d'efficacité, il est conseillé de mémoriser le résultat afin de ne pas refaire le même travail une seconde fois. Mais dans quelle mesure le compilateur le fait-il?

Pour les tests de résistance, prenons une formule naïve de Fibonacci:

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

Nous nous y intéressons pour plusieurs raisons:

la profondeur de récursivité dépend linéairement de n
sans mémorisation, il se réduit à la somme de f (n) uns, et ceci, rappelons-le, est l'exposant à la base du nombre d'or
avec mémorisation - pour mémoriser n valeurs

Comment calculer cette formule au moment de la compilation?

Il existe 3 techniques pour cela.

Le premier, bien connu depuis longtemps (depuis C ++ 98): des modèles avec des paramètres entiers et des membres constants. (Dans les temps anciens, les énumérations étaient utilisées, puis des constantes statiques sont apparues).

//     ,     
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;

(nous utiliserons unsigned, car nous n'avons pas besoin des valeurs réelles des nombres pour les expériences, et nous ne voulons pas courir dans un débordement d'entier).

La deuxième technique est devenue disponible en C ++ 11: les fonctions 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-, ... .

Fonction qui compte le nombre d'opérations pour calculer le nombre de Fibonacci

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

Les modèles d'expression ressembleront à ceci.

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

Pendant 26 - clang a travaillé pendant environ une demi-minute. Pendant 30 ans, il a englouti plus de 8 gigaoctets de mémoire et a conduit mon ordinateur portable dans un échange, après quoi l'expérience a dû être arrêtée.

Mémorisation dans les calculs de compilation en C ++

Comment calculer cette formule au moment de la compilation?

, , .

?

GodBolt

?

" "

More articles: