JPz'log Coin Coin and Plop da Plop

The Joy of C++ Templates Metaprogramming

I am in charge (with 2 fellow snipers) of a lecture about Advanced Programming. This includes the C++ standard library and we will probably include some stuff regarding dynamic languages (how they work, functional-style features like closures or continuations, and so on). This morning, I had a look at C++ templates metaprogramming.

In fact, not that many people know about C++ templates metaprogramming. It has many funny use-cases, including loops unrolling and performing computations at compile-time rather than at runtime. It is also at the heart of many parts of the STL and libraries such as the Boost ones.

I would not use it for everything as it is quite a tricky way of writing programs. In fact, it either compiles fine, or you most probably get errors and warnings that you just can't understand at all

Here is an example that I wrote this morning:

#include<iostream>
 
using namespace std;
 
template<int N> struct Fibo
{
  static const unsigned long long
    value = Fibo<N - 1>::value + Fibo<N -2>::value;
};
 
template<> struct Fibo<1>
{
  static const unsigned long long value = 1;
};
 
template<> struct Fibo<0>
{
  static const unsigned long long value = 0;
};
 
template<int N> void unroll_fibo()
{
  unroll_fibo<N - 1>();
  cout << Fibo<N>::value << endl;
}
 
template<> void unroll_fibo<0>()
{
  cout << Fibo<0>::value << endl;
}
 
int main()
{
  unroll_fibo<60L>();
  return 0;
}

It computes the Fibonacci number. In fact when you run it, you will get the Fibonacci numbers from 0 to 60 instantly! It leverages the two techniques mentionned above: loops unrolling and compile-time computations.

By constrast, the following is a more traditional way of computing the Fibonacci numbers... and the execution time is not even comparable (it has not finished after 3 minutes on my G4 processor).

#include <iostream>
 
using namespace std;
 
long long fibo(const long long &n)
{
  if (n == 0L)
  {
    return 0L;
  }
  else if (n == 1L)
  {
    return 1L;
  }
  else
  {
    return fibo(n - 1) + fibo(n - 2);
  }
}
 
void display_fibo(const int &max)
{
  for (int i = 0; i <= max; ++i)
  {
    cout << fibo((long long) i) << endl;
  }
}
 
int main()
{
  display_fibo(60);
  return 0;
}

Funny isn't it?