如何如此快速地评估 const expr

Question

我一直在尝试在编译时计算的 const 表达式。但是我玩了一个在编译时执行时看起来非常快的示例。

#include<iostream> 

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

int main () {  
    long int res = fib(45); 
    std::cout << res; 
    return 0; 
} 

当我运行此代码时，大约需要 7 秒才能运行。到现在为止还挺好。但是，当我更改long int res = fib(45)到const long int res = fib(45)它需要没有哪怕一秒钟。据我了解，它是在编译时评估的。 但是编译大约需要0.3秒

编译器怎么能这么快地评估它，但在运行时却需要更多的时间？我正在使用 gcc 5.4.0。

Answer 1

编译器缓存较小的值，不需要像运行时版本那样重新计算。
（优化器非常好，会生成大量代码，包括我无法理解的特殊情况的诡计；天真的 2^45 递归需要几个小时。）

如果您还存储以前的值：

int cache[100] = {1, 1};

long int fib(int n) {
    int res = cache[n];
    return res ? res : (cache[n] = fib(n-1) + fib(n-2));
} 

运行时版本比编译器快得多。