Clever Geek Handbook

Memoisasi dalam komputasi waktu kompilasi di C ++

Pemrogram C ++ tahu betul (mudah-mudahan!) Bahwa berbagai macam perhitungan dapat dilakukan pada waktu kompilasi. Andai saja kalkulasi ini "bersih", tanpa efek samping. Ini dilakukan dalam template dan fungsi constexpr.





Ungkapan murni berarti tidak peduli berapa kali kita mencoba untuk mengevaluasinya, kita akan mendapatkan hasil yang sama. Oleh karena itu, demi alasan efisiensi, disarankan untuk menghafal hasilnya agar tidak melakukan pekerjaan yang sama untuk kedua kalinya. Tetapi seberapa baik kompiler melakukannya?





Untuk pengujian stres, mari kita ambil rumus Fibonacci yang naif:





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







Kami tertarik karena beberapa alasan:





  • kedalaman rekursi secara linier tergantung pada n





  • tanpa memoisasi, ia mereduksi menjadi penjumlahan dari f (n), dan ini, ingat, adalah eksponen di dasar rasio emas





  • dengan memoization - untuk menghafal nilai n





Bagaimana cara menghitung rumus ini pada waktu kompilasi?

Ada 3 teknik untuk ini.





Yang pertama, terkenal sejak lama (sejak C ++ 98): template dengan parameter integer dan anggota konstan. (Di zaman kuno, enum digunakan, kemudian konstanta statis muncul).





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

(kami akan menggunakan unsigned, karena kami tidak memerlukan nilai sebenarnya dari angka tersebut untuk eksperimen, dan kami tidak ingin mengalami overflow integer).





Teknik kedua tersedia di C ++ 11: fungsi 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

CT::G

1798

1798

2048

expression template

(ET)

ET::F

899

899

702

ET::G

1796

1796

1402

constexpr

(CE)

CE::F

512

35

26

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





Fungsi yang menghitung jumlah operasi untuk menghitung angka Fibonacci





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

Template ekspresi akan terlihat seperti ini.





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

Selama 26 - dentang bekerja selama sekitar setengah menit. Untuk usia 30, dia melahap lebih dari 8 gigabyte memori dan membawa laptop saya ke swap, setelah itu eksperimen harus dihentikan.







More articles:


All Articles