🚞 🌧️ 🤳 C ++でのコンパイル時計算のメモ化 📹 ✂️ 🍣

C ++プログラマーは、コンパイル時にさまざまな計算を実行できることをよく知っています（願わくば！）。これらの計算だけが「クリーン」で、副作用がない場合。これは、テンプレートとconstexpr関数で行われます。

純粋な表現とは、何度評価しようとしても同じ結果が得られることを意味します。したがって、効率の理由から、同じ作業を2回行わないように、結果を記憶することをお勧めします。しかし、コンパイラはそれをどれだけうまくやっていますか？

ストレステストのために、素朴なフィボナッチの公式を見てみましょう。

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

私たちはいくつかの理由でそれに興味を持っています：

再帰の深さはnに線形に依存します
メモ化しないと、f（n）の合計になります。これは、黄金比の底にある指数です。
メモ化あり-n個の値を記憶する

コンパイル時にこの数式を計算するにはどうすればよいですか？

これには3つのテクニックがあります。

最初の、長い間よく知られている（C ++ 98以降）：整数パラメーターと定数メンバーを持つテンプレート。（古代では、列挙型が使用され、静的定数が表示されていました）。

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

（実験には数値の実際の値は必要なく、整数オーバーフローに遭遇したくないため、unsignedを使用します）。

2番目の手法はC ++ 11で利用可能になりました：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-, ... .

フィボナッチ数を計算するための演算数をカウントする関数

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

式テンプレートは次のようになります。

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

26の場合-clangは約30分間機能しました。30年間、彼は8ギガバイト以上のメモリを飲み込み、私のラップトップをスワップに入れました。その後、実験を停止する必要がありました。

C ++でのコンパイル時計算のメモ化

コンパイル時にこの数式を計算するにはどうすればよいですか？

, , .

?

GodBolt

?

" "

More articles: