C++ metaprogramming

Table of contents

Traditional recursive factorial

int factorial( int n )
{
  if( n <= 1 )
    return 1;
  return n * factorial( n - 1 );
}

Recursive factorial using metaprogramming

template <int N>
struct MetaFactorial {
  enum { value = N * MetaFactorial<N - 1>::value };
};

template <>
struct MetaFactorial<0> {
  enum { value = 1 };
};

Why metaprogramming?

In the book Expert C++ Vardan Grigoryan and Shunguang Wu wrote:

Why would we bother to write so much code just for a factorial that we wrote in the previous section in fewer than five lines of code? The reason is due to its efficiency. While it will take a little bit more time to compile the code, it is super efficient compared to the normal factorial function (implemented either recursively or iteratively). And the reason behind this efficiency is the fact that the actual calculation of the factorial is happening at compile time. That is, when the executable is run, the results are already ready to use. We just used the calculated value when we run the program; no calculation happens at runtime. If you’re seeing this code for the first time, the following explanation will make you fall in love with metaprogramming.

Very simple speed test

  const auto t1_meta = chrono::high_resolution_clock::now();

  res1_meta = MetaFactorial<10>::value;
  res2_meta = MetaFactorial<11>::value;

  const auto t2_meta = chrono::high_resolution_clock::now();

  const chrono::duration<double, nano> ns_meta = t2_meta - t1_meta;
  cout << "MetaFactorial";
  cout << "\nf(10) = " << res1_meta;
  cout << "\nf(11) = " << res2_meta;
  cout << "\ntook " << ns_meta.count() << "ns\n\n";

  const auto t1_recursive = chrono::high_resolution_clock::now();

  res1_recursive = factorial( 10 );
  res2_recursive = factorial( 11 );

  const auto t2_recursive = chrono::high_resolution_clock::now();

  const chrono::duration<double, nano> ns_recursive = t2_recursive - t1_recursive;
  cout << "Recursive";
  cout << "\nf(10) = " << res1_recursive;
  cout << "\nf(11) = " << res2_recursive;
  cout << "\ntook " << ns_recursive.count() << "ns\n\n";

Then the time consuming ratio between both approaches is about 3 to 5 times (in my box):

  cout << "Ratio: " << ns_recursive.count() / ns_meta.count() << endl;

Possible output

MetaFactorial
f(10) = 3628800
f(11) = 39916800
took 37ns

Recursive
f(10) = 3628800
f(11) = 39916800
took 150ns

Ratio: 4.05405