编译时间如何（按指数规律）比运行时更快？
下面的代码通过指数式慢algorithm计算斐波纳契数：
#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个斐波纳契数，以及编译时的第91个斐波纳契数。
有趣的是，GCC 4.9编译代码，并在一秒钟内计算出fib91 ，但是需要花费一些时间来完成fib(45) 。
我的问题：如果GCC足够聪明，可以优化fib(91)计算，而不是采取指数级慢速path，那么阻止它对fib(45)做同样的事情呢？
以上是否意味着GCC会产生两个编译版本的fib函数，其中一个是快速的，另一个是指数级慢的？
问题不在于编译器如何优化fib(91)计算（是的，它使用了一种记忆方式），但是如果它知道如何优化fib函数，为什么它对fib(45)不会这么做呢？ 而且，是否有两个独立的fib函数汇编？ 一个很慢，另一个很快？
GCC可能记忆constexpr函数（使fib(n)的Θ（n）计算）。 这对编译器来说是安全的，因为constexpr函数是纯粹的function。
比较Θ（n）“编译器algorithm”（使用memoization）到你的Θ（φn）运行时algorithm（其中φ是黄金比例），突然间编译器的速度非常快。
从cppreference的constexpr页面 （重点加）：
constexpr说明符声明可以在编译时评估函数或variables的值。
constexpr说明符没有声明在编译时需要评估函数或variables的值。 所以人们只能猜测GCC正在使用什么样的启发式方法来select在编译时还是运行时计算编译时间，而不需要语言规则。 它可以根据具体情况select，但仍然是正确的。
如果你想强制编译器在编译时评估你的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 ，并保证它们在编译时被评估。
在编译时，编译器可以记忆函数的结果。 这是安全的，因为函数是一个constexpr，因此将始终返回相同input的相同结果。
在运行时，理论上可以这样做。 然而大多数C ++程序员会在导致隐藏内存分配的优化过程中皱眉头。
当你要求fib（91）给源代码中的const fib91赋值时，编译器将被迫从你的const expr中计算出这个值。 它没有编译函数（就像你似乎认为的那样），只是它看到计算fib91需要fib（90）和fib（89），计算它需要fib（87）…直到他计算fib（1）这是给出的。 这是一个$ O（n）$algorithm，并且计算结果足够快。
但是当你要求在运行时评估fib（45）时，编译器必须使用实际的函数调用来select它，或者预先计算结果。 最终它决定使用编译的function。 现在，编译的函数必须完全执行指数algorithm，您已经决定编译器无法实现记忆来优化recursion函数（考虑需要分配一些caching并了解需要保留多less值以及如何pipe理他们之间的函数调用）。
