在C ++ 11中计算编译时间中的斐波纳契数（递归方法）（constexpr） [英] Calculate the Fibonacci number (recursive approach) in compile time (constexpr) in C++11

问题描述

我写了程序斐波那契数字计算在编译时（constexpr）
问题使用模板元编程技术支持在C + + 11。其目的是计算模板元编程方法和旧的常规方法之间的运行时间差异。

  //模板元编程方法
 template< int N> 
 constexpr int fibonacci（）{return fibonacci N-1（）+ fibonacci N-2（）; } 
 template<> 
 constexpr int fibonacci< 1>（）{return 1; } 
 template<> 
 constexpr int fibonacci< 0>（）{return 0; } 
 
 
 
 //传统方法
 int fibonacci（int N）{
 if（N == 0）return 0; 
 else if（N == 1）return 1; 
 else 
 return（fibonacci（N-1）+ fibonacci（N-2））; 
} 
  

我为 N = 40 我的GNU / Linux系统并测量时间，
发现常规解决方案（1.15秒）比基于模板的解决方案（0.55秒）慢两倍。这是一个重大的改进，因为两种方法都是基于递归。

为了理解它，我编译程序（ -fdump-tree-all flag），并且发现编译器实际生成了40个不同的函数（如fibonacci 40，fibonacci 39 ... fibonacci o）。

  constexpr int fibonacci（）[with int N = 40]（）{
 int D.29948， 29949，D.29950， 
 D.29949 = fibonacci< 39> （）; 
 D.29950 = fibonacci< 38> （）; 
 D.29948 = D.29949 + D.29950; 
 return D.29948; 
} 
 
 constexpr int fibonacci（）[with int N = 39]（）{
 int D.29952，D.29953，D.29954; 
 D.29953 = fibonacci< 38> （）; 
 D.29954 = fibonacci< 37> （）; 
 D.29952 = D.29953 + D.29954; 
 return D.29952; 
} 
 ... 
 ... 
 ... 
 constexpr int fibonacci（）[with int N = 0]（）{
 int D.29962; 
 D.29962 = 0; 
 return D.29962; 
} 
  

我也调试了GDB中的程序，发现所有上述函数都是
执行与传统递归方法相同的次数。
如果两个版本的程序都执行相同的次数（递归），那么这是如何通过模板元编程技术实现的？我还想知道你对如何和为什么基于模板元编程的方法比其他版本花费一半时间的意见？这个程序可以比当前的程序更快吗？

基本上我的意图是尽可能了解内部发生了什么。

我的机器是使用GCC 4.8.1的GNU / Linux，我对这两个程序使用优化 -o3 。

解决方案

试试这个：

  template< size_t N& 
 struct fibonacci：integral_constant< size_t，fibonacci< N-1> {} + fibonacci< N-2> {} {}; 
 
模板<>结构纤维蛋白1 ：integral_constant< size_t，1> {}; 
模板<> struct fibonacci 0 ：integral_constant< size_t，0> {}; 
  

使用clang和 -Os 大约0.5秒，并且 N = 40 在零时间运行。你的常规方法编译大约0.4s和运行在0.8s。只是为了检查，结果是 102334155 对吗？

当我尝试你自己的 constexpr 解决方案编译器运行几分钟，然后我停止它，因为显然内存已满（计算机开始冻结）。

使用这个解决方案，在的模板实例化，当实例化 N 时，将重新使用N-2 ， N-1 。因此， fibonacci< 40> 在编译时实际上是一个值，在运行时没有什么可做。这是一个动态编程方法，当然你可以在运行时做同样的事情，如果你存储所有的值在 0 通过 N-1 可在 N >在编译时评估 fibonacci< N>（），但不需要。在你的情况下，所有或部分计算留给运行时间。在我的情况下，所有的计算在编译时尝试，因此永远不会结束。

I wrote the program Fibonacci number calculation in compile time (constexpr) problem using the template metaprogramming techniques supported in C++11. The purpose of this is to calculate the difference in the run-time between the template metaprogramming approach and the old conventional approach.

// Template Metaprograming Approach
template<int  N>
constexpr int fibonacci() {return fibonacci<N-1>() + fibonacci<N-2>(); }
template<>
constexpr int fibonacci<1>() { return 1; }
template<>
constexpr int fibonacci<0>() { return 0; }



// Conventional Approach
 int fibonacci(int N) {
   if ( N == 0 ) return 0;
   else if ( N == 1 ) return 1;
   else
      return (fibonacci(N-1) + fibonacci(N-2));
} 

I ran both programs for N = 40 on my GNU/Linux system and measured the time and found that that conventional solution (1.15 second) is around two times slower than the template-based solution (0.55 second). This is a significant improvement as both approaches are based on the recursion.

To understand it more I compiled the program (-fdump-tree-all flag) in g++ and found that compiler actually generated the 40 different functions (like fibonacci<40>, fibonacci<39>...fibonacci<0>).

constexpr int fibonacci() [with int N = 40] () {
  int D.29948, D.29949, D.29950;
  D.29949 = fibonacci<39> ();
  D.29950 = fibonacci<38> ();
  D.29948 = D.29949 + D.29950;
  return D.29948;
}

constexpr int fibonacci() [with int N = 39] () {
  int D.29952, D.29953, D.29954;
  D.29953 = fibonacci<38> ();
  D.29954 = fibonacci<37> ();
  D.29952 = D.29953 + D.29954;
  return D.29952;
}
...
...
...
constexpr int fibonacci() [with int N = 0] () {
  int D.29962;
  D.29962 = 0;
  return D.29962;
}

I also debugged the program in GDB and found that all the above functions are executed an equal number of times as with the conventional recursive approach. If both versions of the program are executing the function an equal number of times (recursive), then how is this achieved by template metaprogramming techniques? I would also like to know your opinion about how and why a template metaprogramming based approach is taking half time compared to the other version? Can this program be made faster than the current one?

Basically my intention here is to understand what's going on internally as much as possible.

My machine is GNU/Linux with GCC 4.8.1, and I used the optimization -o3 for both programs.

解决方案

Try this:

template<size_t N>
struct fibonacci : integral_constant<size_t, fibonacci<N-1>{} + fibonacci<N-2>{}> {};

template<> struct fibonacci<1> : integral_constant<size_t,1> {};
template<> struct fibonacci<0> : integral_constant<size_t,0> {};

With clang and -Os, this compiles in roughly 0.5s and runs in zero time for N=40. Your "conventional" approach compiles in roughly 0.4s and runs in 0.8s. Just for checking, the result is 102334155 right?

When I tried your own constexpr solution the compiler run for a couple of minutes and then I stopped it because apparently memory was full (computer started freezing). The compiler was trying to compute the final result and your implementation is extremely inefficient to be used at compile time.

With this solution, template instantiations at N-2, N-1 are re-used when instantiating N. So fibonacci<40> is actually known at compile time as a value, and there is nothing to do at run-time. This is a dynamic programming approach and of course you can do the same at run time if you store all values at 0 through N-1 before computing at N.

With your solution, the compiler can evaluate fibonacci<N>() at compile time but is not required to. In your case, all or part of computation is left for run time. In my case, all computation is attempted at compile time, hence never ending.

这篇关于在C ++ 11中计算编译时间中的斐波纳契数（递归方法）（constexpr）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！