Сколько времени действительно может занять компиляция шаблона?

Question

Шаблон метапрограммирования может использоваться для вычисления таких вещей, как факториал, во время компиляции, а не во время выполнения. Я слышал, что некоторые конкурсы по программированию ввели ограничения на время компиляции именно для того, чтобы отсеять злоупотребление метапрограммированием шаблонов.

Есть ли какой-нибудь невинный пример использования шаблонов, который занимает очень-очень много времени (например, несколько часов) для компиляции?

Answer 1

Механизм шаблона является полным по Тьюрингу. Это означает, что, по крайней мере, теоретически любое вычисление, которое может быть выполнено, может быть выполнено таким образом во время компиляции (на практике вы можете столкнуться с жесткими ограничениями по глубине шаблона и т. Д. Довольно быстро, но это зависит от компилятора).

Хотите ли вы сделать это, это отдельный вопрос. Вы можете тривиально соответствовать вашему критерию «часы для компиляции», используя дорогой алгоритм. Но есть и более практичные коды, такие как , в которых реализован FFT ; дать этому достаточно большой набор данных, и это займет некоторое время ...

Answer 2

Я слышал, что Международная олимпиада по информатике (одно из таких соревнований по программированию) впервые ввело ограничения по времени компиляции после того, как участник создал 7-мерный вектор с использованием техники, очень похожей на this . Его код нужно было компилировать на ночь, это было так плохо. Я думаю, что это произошло в конце 90-х годов.

Answer 3

Попробуйте (я использовал 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);
}

Это может показаться ужасным, я просто попытался написать эквивалент этой милой функции LISP

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

Наш учитель сказал, что это функция Фермы, но я не уверен ...