Man*_*726 12 c++ recursion performance template-meta-programming c++11
常见的编译器优化是将尾递归函数转换为循环,从而加快执行时间并减少内存(堆栈)消耗:
int go_to_zero( int n )
{
if( n == 0 )
return 0;
else
return go_to_zero( n - 1 );
}
我的问题很简单:在模板元编程上执行尾递归算法是否有任何性能优势(即减少编译时间)？
这是一个例子:
template<typename... Ts>
struct list {};
template<typename LIST>
struct reverse;
template<typename HEAD , typename... TAIL>
struct reverse<list<HEAD,TAIL...>>
{
using result = concat<typename reverse<list<TAIL...>>::result,list<HEAD>>;
};
template<>
struct reverse<list<>>
{
using result = list<>;
};
与:
template<typename INPUT , typename OUTPUT>
struct reverse_impl;
template<typename HEAD , typename... TAIL , tyename... Ts>
struct reverse_impl<list<HEAD,TAIL...>,list<Ts...>>
{
using result = typename reverse_impl<list<TAIL...>,list<Ts...,HEAD>>::result;
};
template<typename... Ts>
struct reverse_impl<list<>,list<Ts...>>
{
using result = list<Ts...>;
};
template<typename LIST>
using reverse = typename reverse_impl<LIST,list<>>::result;
在C++模板元编程附录C"编译时间性能"中,Abraham和Gurtovoy弄清楚了模板实例化的memoization如何影响编译时间.这本书写于2005年,我认为今天的备忘录更好实施(我没有测量).所以要回答的问题是哪些实现可以从memoization中获益更多.我已经编辑了一些版本1和版本2的代码.现在它将在reverse_impl实例化时发出错误,因此我们可以简单地计算错误.我反向2个列表list<int, short, char>和list<short, char>.版本1发出4个错误,版本2发出7个错误.在这种特殊情况下,版本1受益于这两个列表的memoization(list2是list1的尾部)而版本2没有.所以我希望版本1更快.
因此,最好根据已知从记忆中受益的其他算法实现算法,我认为大多数算法都使用头递归.