C ++ programmers know well (hopefully!) That a variety of computations can be performed at compile time. If only these calculations were "clean", without side effects. This is done in templates and constexpr functions.
A pure expression means that no matter how many times we try to evaluate it, we will get the same result. Therefore, for reasons of efficiency, it is advisable to memorize the result so as not to do the same work a second time. But how well does the compiler do it?
For stress testing, let's take a naive Fibonacci formula:
f(n) = (n < 2) ? 1 : f(n-1) + f(n-2)
We are interested in it for several reasons:
recursion depth linearly depends on n
without memoization, it reduces to the summation of f (n) ones, and this, recall, is the exponent at the base of the golden ratio
with memoization - to memorize n values
How do I calculate this formula at compile time?
There are 3 techniques for this.
The first, well known for a long time (since C ++ 98): templates with integer parameters and constant members. (In ancient times, enums were used, then static constants appeared).
// ,
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;
(we will use unsigned, because we do not need the actual values of the numbers for experiments, and we do not want to run into an integer overflow).
The second technique became available in C ++ 11: constexpr functions.
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
,
-
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::F |
899 |
899 |
1024 |
CT::G |
1798 |
1798 |
2048 |
|
expression template
|
ET::F |
899 |
899 |
702 |
ET::G |
1796 |
1796 |
1402 |
|
constexpr
|
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-, ... .
Function that counts the number of operations to calculate the Fibonacci number
f(n, t) = n < 2 ? t+1 : f(n-1, f(n-2, t))
f(n) = f(n, 0)
The expression templates will look like this.
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;
}
For 26 - clang worked for about half a minute. For 30, he gobbled up more than 8 gigabytes of memory and drove my laptop into a swap, after which the experiment had to be stopped.