Compile Time vs Run time speed-CodePudding

Why is getting a number of the Fibonacci sequence at compile-time using templates much faster than run-time using a recursive function?

#include <iostream>
using namespace std;

template<unsigned long long int I>
struct Fib
{
    static const unsigned long long int val = Fib<I - 1>::val   Fib<I - 2>::val;
};

template<>
struct Fib<0>
{
    static const unsigned long long int  val = 0;
};

template<>
struct Fib<1>
{
    static const unsigned long long int  val = 1;
};

int main()
{
    cout << Fib<100>::val << '\n';
    return 0;
}

CodePudding user response：

A recursive function has all of its code executed at runtime (unless the compiler optimizes it).

A template is typically faster at runtime because all of its code is executed by the compiler itself and only the result is stored in the final executable, so there is no code executed at runtime at all.

So, this code:

#include <iostream>
using namespace std;

template<unsigned long long int I>
struct Fib
{
    static const unsigned long long int val = Fib<I - 1>::val   Fib<I - 2>::val;
};

template<>
struct Fib<0>
{
    static const unsigned long long int  val = 0;
};

template<>
struct Fib<1>
{
    static const unsigned long long int  val = 1;
};

int main()
{
    cout << Fib<100>::val << '\n';
    return 0;
}

Once compiled, will behave as-if you had written this instead:

#include <iostream>
using namespace std;

struct Fib_100
{
    static const unsigned long long int val = 3736710778780434371ull;
};

int main()
{
    cout << Fib_100::val << '\n';
    return 0;
}

Or simply:

#include <iostream>
using namespace std;

int main()
{
    cout << 3736710778780434371ull << '\n';
    return 0;
}

CodePudding user response：

Compile-time evaluation

Templates are run at compilation time, while functions are run at run time.

This means that, in your code, Fib<100>::val is replaced by the value of fib(100) (3736710778780434371); no code is ever run.

On the other hand, a function isn't evaluated during compilation but only when your program is run. In the case of fib(100), this will take quite a while to run.

In some cases, the compiler can still optimize a normal function call. But this is not always the case, while templates are always run during compilation.

Memoization

One other reason templates are faster than a simple recursive function is that templates inherently have "memoization". This means that Fib<1> is only ever calculated one time, even if it's called multiple times. This makes a big difference when you calculate the Fibonacci series. For example: Let's say we want to calculate fib(5). To do so, we first have to calculate fib(i-1) and fib(i-2), i.e. fib(4) and fib(3). But in order to calculate fib(4), we have to first calculate fib(3) and fib(2). etc. Notice how we had to calculate fib(3) more than once? That's where memoization comes in. Memoization basically saves the return value, and then, the next time you call the function with the same argument, it just returns that value without having to calculate anything again. It could be implemented something like this:

#include <iostream>

unsigned long long mem[100001];
unsigned long long fib(unsigned long long i) {
    if (mem[i]) return mem[i];
    return mem[i] = (i <= 1 ? i : fib(i - 1)   fib(i - 2));
}

int main() {
    std::cout << fib(100000) << std::endl;
}

And if you run that now, it's much faster than just the simple recursive implementation!

Templates practically do the same thing: if you write Fib<1> once, it saves the result for the next time you use it.

Edit:

As @user17732522 pointed out, your value member should be a constexpr, not a const:

template <int N>
struct Fib {
    static constexpr val = Fib<N-1>::val   Fib<N-2>::val;
};

// ... other cases ...

CodePudding user response：

Because the compiler computes every Fib<??>::val just once, regardless of enabled optimizations.

On the other hand, a naive implementation using a recursive function (assuming no optimizations) would repeatedly compute the same fib(??) number, way more times than than necessary.