CODEWITHSUNDEEP
c++templates
vollitwr
vollitwr

Reputation: 439

Why are C++ template calculations so fast?

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.

Upvotes: 5

Views: 360

Answers (3)

Petar Velev
Petar Velev

Reputation: 2355

They are not fast, they are already there. If you manage to write such a template program the value that you're using will be there before the program starts.
This can be also achieved with constexpr.
However, the fact that you need all the information at compile time is making it applicable to a very few use cases.

I've reworked your example to show you that(link to example).

main:
.LFB0:
  .file 1 "/tmp/compiler-explorer-compiler118417-63-1cf1gj5.e1tp/example.cpp"
  .loc 1 12 0
  .cfi_startproc
  .loc 1 14 0
  mov eax, 1836311903
  ret

The eax is filled with the number 1836311903 which happens to be exactly the 46th fibonnaci number.

Upvotes: 1

Swift - Friday Pie
Swift - Friday Pie

Reputation: 14589

fib() is a recursive function which is bad for performance in this case, because of multiple iterations of function call and stack creation.

Template value would be calculate value statically, because N is known at compile time. Also try:

constexpr int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

This would make it equivalent of template solution, value of function would be calculated in compile time if possible) with -O2 flag :P

Upvotes: 0

rustyx
rustyx

Reputation: 85351

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.

Upvotes: 17

Related Questions