如何使编译时(指数)快于运行时? [英] How can the compile-time be (exponentially) faster than run-time?
问题描述
下面的代码通过指数慢的算法计算斐波那契数字:
#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个斐波那契数,一个在编译时。
有趣的是,GCC 4.9编译代码并计算 fib91
第二个,但需要一段时间吐出 fib(45)
。
我的问题:如果GCC智能足以优化 fib(91)
计算,而不是采取指数缓慢的路径,阻止它做同样 fib(45)
?
上面的意思是GCC产生两个编译版本的 fib
fib(91)$ c $ c>计算(是的!它使用一种记忆),但如果它知道如何优化 fib
函数,为什么它不做同样的 fib(45)
?还有, fib
函数有两个单独的编译?一个慢,另一个快?解决方案 GCC可能记住 constexpr
函数(启用 fib(n)
的Θ(n)计算)。这对于编译器来说是安全的,因为 constexpr
函数是纯函数。
比较Θ编译器算法(使用memoization)到你的Θ(φ 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必须是非负。
static const long long value = compute_fib(N);
};
在其余代码中,您可以访问 fib< 45> ;: :value
或 fib< 91> :: value
,并保证在编译时进行评估。
The below code calculates Fibonacci numbers by an exponentially slow 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;
}
And I am calculating the 45th Fibonacci number at run-time, and the 91st one at compile time.
The interesting fact is that GCC 4.9 compiles the code and computes fib91
in a fraction of a second, but it takes a while to spit out fib(45)
.
My question: If GCC is smart enough to optimize fib(91)
computation and not to take the exponentially slow path, what stops it to do the same for fib(45)
?
Does the above mean GCC produces two compiled versions of fib
function where one is fast and the other exponentially slow?
The question is not how the compiler optimizes fib(91)
calculation (yes! It does use a sort of memoization), but if it knows how to optimize the fib
function, why does it not do the same for fib(45)
? And, are there two separate compilations of the fib
function? One slow, and the other fast?
解决方案 GCC is likely memoizing constexpr
functions (enabling a Θ(n) computation of fib(n)
). That is safe for the compiler to do because constexpr
functions are purely functional.
Compare the Θ(n) "compiler algorithm" (using memoization) to your Θ(φn) run time algorithm (where φ is the golden ratio) and suddenly it makes perfect sense that the compiler is so much faster.
From the constexpr
page on cppreference (emphasis added):
The constexpr specifier declares that it is possible to evaluate the value of the function or variable at compile time.
The constexpr
specifier does not declare that it is required to evaluate the value of the function or variable at compile time. So one can only guess what heuristics GCC is using to choose whether to evaluate at compile time or run time when a compile time computation is not required by language rules. It can choose either, on a case-by-case basis, and still be correct.
If you want to force the compiler to evaluate your constexpr
function at compile time, here's a simple trick that will do it.
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);
};
In the rest of your code you can then access fib<45>::value
or fib<91>::value
with the guarantee that they'll be evaluated at compile time.
这篇关于如何使编译时(指数)快于运行时?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!