beh*_*uri 48 c++ compiler-construction gcc constexpr c++11
以下代码通过指数缓慢的算法计算斐波纳契数:
#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个Fibonacci数,在编译时计算第91个.
有趣的是,GCC 4.9编译代码并fib91在几分之一秒内完成计算,但需要一段时间才能吐出fib(45).
我的问题:如果GCC足够聪明以优化fib(91)计算而不是采用指数缓慢的路径,那么它会阻止它做同样的事情fib(45)吗？
以上是否意味着GCC产生两个编译版本的fib函数,其中一个是快速的而另一个是指数级的慢？
问题不在于编译器如何优化fib(91)计算(是的!它确实使用了一种记忆),但如果它知道如何优化fib函数,为什么它不会这样做fib(45)呢？并且,是否有两个单独的fib函数编译？一个慢,另一个快？
Tim*_*lds 38
GCC可能是记忆constexpr功能(启用Θ(n)计算fib(n)).这对编译器来说是安全的,因为constexpr函数纯粹是功能性的.
比较Θ(N)"编译器算法"(使用记忆化)到您的Θ(φ ñ运行时间算法)(其中φ是黄金比例),突然它非常有意义,编译器是如此之快.
从对constexpr上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保证在编译时对它们进行评估.
pdw*_*pdw 16
在编译时,编译器可以记住函数的结果.这是安全的,因为该函数是constexpr,因此将始终返回相同输入的相同结果.
在运行时它理论上可以做同样的事情.但是,大多数C++程序员都会对优化传递感到不满,导致隐藏的内存分配.