Почему вычисления шаблонов C ++ такие быстрые?

Question

Интересно насчет следующего кода.

#include <iostream>
using std::cout;
template<int N> struct Fib {
    enum { v = Fib<N - 1>::v + Fib<N - 2>::v };
};
template<> struct Fib<0> {
    enum { v = 0 };
};
template<> struct Fib<1> {
    enum { v = 1 };
};
int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int main() {
    cout << Fib<46>::v << '\n';
//    cout << fib(46) << '\n';
    return 0;
}

Он вычисляет результат во время компиляции без какой-либо заметной задержки.Как это возможно?Если мы используем вызов fib (46), нам придется ждать несколько секунд даже с самым быстрым ПК.Шаблон использует ту же схему расчета и делает это мгновенно.Я также удивлен тем, что размер исполняемого файла, созданного с шаблоном, почти такой же, как и без шаблона.Я использовал GCC.

Answer 1

Это связано с присущей памяткой в шаблонном решении.

Во время компиляции каждое создание, например Fib<1>, Fib<2> и т. Д., Выполняется (компилятором) только один раз и запоминается.

Когда вы запускаете fib(n), с другой стороны, fib(1), fib(2) и т. Д. Вычисляются много раз. Решением может быть запоминание этого, т. Е. Запоминание результата каждого вызова fib на карте или в массиве, и возврат его, если результат уже существует.

Answer 2

Они не быстрые, они уже есть. Если вам удастся написать такую ​​программу-шаблон, то значение, которое вы используете, будет там до запуска программы.
Этого также можно добиться с помощью constexpr.
Однако тот факт, что вам нужна вся информация во время компиляции, делает ее применимо к очень немногим случаям использования.

Я переделал ваш пример, чтобы показать вам ( ссылка на пример ).

main:
.LFB0:
  .file 1 "/tmp/compiler-explorer-compiler118417-63-1cf1gj5.e1tp/example.cpp"
  .loc 1 12 0
  .cfi_startproc
  .loc 1 14 0
  mov eax, 1836311903
  ret

eax заполняется числом 1836311903, которое в точности соответствует 46-му числу Фибоначчи.

Answer 3

fib() - это рекурсивная функция, которая в данном случае плохо сказывается на производительности из-за множественных итераций вызова функции и создания стека.

Значение шаблона будет вычислять значение статически, поскольку N известно при компиляциивремя.Также попробуйте:

constexpr int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

Это сделает его эквивалентным шаблонному решению, значение функции будет вычислено во время компиляции, если это возможно) с флагом -O2: P