How long can template compilation really take?

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?

From stackoverflow

• 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.

• 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...

  sharptooth : It takes about 25 seconds on Core2 Duo 2,66 with N=1000. That's impressive but not very long. And this code is definitely not innocently looking.

  simon : N=1000 isn't very big at all for an FFT. I should be clear, I meant that it was "more practical" not because this is the way you'd want to compute an FFT, but because it's an extremely useful algorithm (and used all over the place) rather than implementing something just to take a long time (like and Ackerman function evaluation)

• 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...

  Adam Rosenfield : http://en.wikipedia.org/wiki/Ackermann_function

  sharptooth : Tried this with <116, 116> on VC7 on Core2 Duo 2,66 - takes about 20 seconds which is impressive but not very long. Larger values cause a compile-time error.