How long can template compilation really take?

Question

Template metaprogramming can be used for computing things like factorial at compile time instead of during runtime. I've heard that some programming contests have introduced limitations on compilation time exactly to weed out template metaprogramming abuse.

Is there any innocent looking example of using templates that takes some really-really long time (like several hours) to compile?

Answer 1

I've heard that the International Olympiad in Informatics (one such programming contest) first introduced compile time limits after a contestant created a 7 dimensional vector using a technique much like this. His code had to be left compiling overnight it was so bad. I think this occured some time in the late 90's.

Answer 2

The template mechanism is Turing-complete. This means that in theory at least, any computation that can be done can be done at compile time this way (In practice you may run into hard limits on template depth etc. fairly quickly but this is compiler dependent).

Whether or not you'd want to do this is a separate question. You can trivially match your criterion of "hours to compile" by using an expensive algorithm. But there are also more practical codes like this one implementing an FFT; give that a large enough data set and it will take a while...

Answer 3

Try this (i used Visual Studio 2005)

template <int M, int N>
struct Ack 
{
    enum { value = Ack<M - 1, Ack<M, N - 1>::value >::value };
};

template <int M>
struct Ack<M, 0> 
{
    enum { value = Ack<M - 1, 0>::value };
};

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

template <int N>
struct Ack<0, N> 
{
    enum { value = N + 1 };
};

void main()
{
    printf("Result: %d\n",  Ack<150, 150>::value);
}

It maybe seems horribble, i just tried to write an equivalent to this cute lisp function

(defun ack(m, n)
cond ((= m 0) (+ n 1))
     ((= n 0) ack(- m 1) n)
     (t (ack (- m 1) (ack m (-n 1))) )
)

Our teacher said it is Ferma function, but i am not sure...