Why are C++ template calculations so fast?

  • A+
Category:Languages

I wonder about the next code.

#include <iostream> using std::cout; template<int N> struct Fib {     enum { v = Fib<N - 1>::v + Fib<N - 2>::v }; }; template<> struct Fib<0> {     enum { v = 0 }; }; template<> struct Fib<1> {     enum { v = 1 }; }; int fib(int n) {     return n < 2 ? n : fib(n - 1) + fib(n - 2); } int main() {     cout << Fib<46>::v << '/n'; //    cout << fib(46) << '/n';     return 0; } 

It calculates the result at the compilation time without any noticeable delay. How is it possible? If we use the call to fib(46) we will have to wait for several seconds even with the fastest PC. The template uses the same schema of calculation and it makes it instantly. I am also surprised by the fact that the size of the executable file produced with the template is almost the same as without template. I used GCC.


It's due to inherent memoization in the template solution.

During compilation, each instantiation like Fib<1>, Fib<2>, etc, is performed (by the compiler) only once and remembered.

When you run fib(n) on the other hand, fib(1), fib(2), etc. are calculated many times. The solution could be to memoize it, i.e. remember the result of each fib call in a map or an array, and return that if a result already exists.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: