Как время компиляции может быть (экспоненциально) быстрее, чем время выполнения?

Question

Ниже код вычисляет числа Фибоначчи с помощью экспоненциально медленного алгоритма:

#include <cstdlib> 
#include <iostream> 

#define DEBUG(var) { std::cout << #var << ": " << (var) << std::endl; } 

constexpr auto fib(const size_t n) -> long long 
{ 
    return n < 2 ? 1: fib(n - 1) + fib(n - 2); 
} 

int main(int argc, char *argv[]) 
{ 
    const long long fib91 = fib(91); 

    DEBUG(fib91); 
    DEBUG(fib(45)); 

    return EXIT_SUCCESS; 
} 

И я расчета 45-го числа Фибоначчи во время выполнения, и 91st один во время компиляции.

Интересный факт состоит в том, что GCC 4.9 компилирует код и вычисляет fib91 в доли секунды, но требуется некоторое время, чтобы выплюнуть fib(45).

Мой вопрос: если GCC достаточно умен, чтобы оптимизировать вычисление fib(91), а не принимать экспоненциально медленный путь, что мешает ему делать то же самое для fib(45)?

Означает ли это, что GCC создает две скомпилированные версии функции fib, где одна быстро, а другая экспоненциально медленная?

Вопрос заключается в том не как компилятор оптимизирует fib(91) расчета (да! Это действительно использует свой род запоминание), но, если он знает, как оптимизировать функции fib, почему это не сделать то же самое для fib(45)? И есть ли две отдельные компиляции функции fib? Один медленный, а другой быстрый?

Answer 1

GCC, вероятно, memoizing constexpr функции (включение вычисления Θ (n) fib(n)). Это безопасно для компилятора, потому что функции constexpr являются чисто функциональными.

Сравните Q (п) «алгоритм компилятор» (с использованием запоминания) к вашему Q (φ ^п) время работы алгоритма (где φ является золотым сечением), и вдруг это имеет смысл, что компилятор так много Быстрее.

От the constexpr page on cppreference (подчеркивание добавлено):

constexpr спецификатор заявляет, что можно оценить значение функции или переменной во время компиляции.

constexpr спецификатор делает не объявить, что требуется, чтобы оценить значение функции или переменной во время компиляции. Поэтому можно только догадываться, какие эвристики GCC использует, чтобы выбрать, следует ли оценивать во время компиляции или времени выполнения, когда языковые правила не требуются для вычисления времени компиляции. Он может выбирать либо в каждом конкретном случае, и по-прежнему быть правильным.

Если вы хотите заставить компилятор оценить вашу функцию constexpr во время компиляции, вот простой трюк, который это сделает.

constexpr auto compute_fib(const size_t n) -> long long 
{ 
    return n < 2 ? n : compute_fib(n - 1) + compute_fib(n - 2); 
} 

template <std::size_t N> 
struct fib 
{ 
    static_assert(N >= 0, "N must be nonnegative."); 
    static const long long value = compute_fib(N); 
}; 

В остальной части кода вы можете получить доступ к fib<45>::value или fib<91>::value с гарантией того, что они будут оценены во время компиляции.

Answer 2

При компиляции компилятор может memoize результат функции.Это безопасно, потому что функция является constexpr и, следовательно, всегда будет возвращать один и тот же результат с теми же входами.

Во время выполнения теоретически можно было сделать то же самое. Однако большинство программистов на С ++ хмурились над прогонами оптимизации, которые приводят к скрытым выделениям памяти.

Answer 3

Когда вы запрашиваете, чтобы fib (91) дал значение вашему const fib91 в исходном коде, компилятор вынужден вычислить это значение из вас const expr. Он не компилирует функцию (как вы, кажется, думаете), просто она видит, что для вычисления fib91 ей нужны fib (90) и fib (89), чтобы вычислить ей нужно fib (87) ... так, пока он не вычислит fib (1). Это алгоритм $ O (n) $, и результат вычисляется достаточно быстро.

Однако, когда вы попросите оценить fib (45) во время выполнения, компилятор должен выбрать, используя фактический вызов функции или прекомпретировать результат. В конце концов он решает использовать скомпилированную функцию. Теперь скомпилированная функция должна точно выполнить экспоненциальный алгоритм, который вы решили, что компилятор не может реализовать memoization для оптимизации рекурсивной функции (подумайте о необходимости выделить некоторый кеш и понять, сколько значений сохранить и как управлять их между вызовами функций).