🏎️ 👩🏽‍🏭 ✝️ Memoisierung bei Berechnungen zur Kompilierungszeit in C ++ 🌵 🤣 🧛🏽

C ++ - Programmierer wissen (hoffentlich!) Gut, dass zur Kompilierungszeit verschiedene Berechnungen durchgeführt werden können. Wenn nur diese Berechnungen "sauber" wären, ohne Nebenwirkungen. Dies erfolgt in Vorlagen und constexpr-Funktionen.

Ein reiner Ausdruck bedeutet, dass wir unabhängig davon, wie oft wir versuchen, ihn zu bewerten, das gleiche Ergebnis erzielen. Aus Gründen der Effizienz ist es daher ratsam, sich das Ergebnis zu merken, um nicht die gleiche Arbeit ein zweites Mal auszuführen. Aber wie gut macht der Compiler das?

Nehmen wir für Stresstests eine naive Fibonacci-Formel:

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

Wir sind aus mehreren Gründen daran interessiert:

Die Rekursionstiefe hängt linear von n ab
Ohne Memoisierung reduziert es sich auf die Summe von f (n), und dies ist, wie man sich erinnert, der Exponent an der Basis des Goldenen Schnitts
mit memoization - um n Werte zu speichern

Wie berechne ich diese Formel zur Kompilierungszeit?

Hierfür gibt es 3 Techniken.

Die erste, seit langem bekannte (seit C ++ 98): Vorlagen mit ganzzahligen Parametern und konstanten Elementen. (In der Antike wurden Aufzählungen verwendet, dann erschienen statische Konstanten).

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

(Wir werden unsigned verwenden, da wir die tatsächlichen Werte der Zahlen für Experimente nicht benötigen und nicht auf einen ganzzahligen Überlauf stoßen möchten.)

Die zweite Technik wurde in C ++ 11 verfügbar: constexpr-Funktionen.

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

Funktion, die die Anzahl der Operationen zur Berechnung der Fibonacci-Zahl zählt

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

Die Ausdrucksvorlagen sehen folgendermaßen aus.

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

Für 26 - Clang arbeitete etwa eine halbe Minute. Für 30 verschlang er mehr als 8 Gigabyte Speicher und fuhr meinen Laptop in einen Tausch, wonach das Experiment abgebrochen werden musste.

Memoisierung bei Berechnungen zur Kompilierungszeit in C ++

Wie berechne ich diese Formel zur Kompilierungszeit?

, , .

?

GodBolt

?

" "

More articles: