在我看来,在C和C++中同时进行尾递归优化会非常好,但在调试过程中,我似乎从来没有看到一个框架堆栈来表示这种优化。这很好,因为堆栈告诉我递归有多深。然而,优化也是很好的。
有没有C++编译器做过这样的优化?为什么?为什么不行?
我该如何告诉编译器这样做呢?
微软-O3
的
/O2
或 GCC:-O2
或MSVC如何检查编译器在特定情况下是否已经这样做了?
对于MSVC的
我仍然建议如何确定某个函数是否被编译器像这样优化(即使我发现Konrad告诉我假设它是可靠的)
始终可以通过进行无限递归并检查它是否会导致无限循环或堆栈溢出来检查编译器是否做到了这一点(我和GCC一起做了这件事,发现-O2
就足够了),但我希望能够检查某个我知道无论如何都会终止的函数。我希望有一个简单的方法来检查这一点:)
经过一些测试后,我发现析构函数破坏了进行这种优化的可能性。有时,更改某些变量和临时变量的作用域以确保它们在返回语句开始之前超出作用域是值得的。
如果在尾部调用之后需要运行任何析构函数,则无法进行尾部调用优化。
发布于 2008-08-29 07:40:32
当前所有主流编译器都能很好地执行尾部调用优化(并且已经做了十多年了),even for mutually recursive calls例如:
int bar(int, int);
int foo(int n, int acc) {
return (n == 0) ? acc : bar(n - 1, acc + 2);
}
int bar(int n, int acc) {
return (n == 0) ? acc : foo(n - 1, acc + 1);
}
让编译器进行优化很简单:只需打开优化以提高速度:
用于MSVC的
/O2
或/Ox
.-O3
检查编译器是否进行了优化的一种简单方法是执行调用,否则会导致堆栈溢出-或者查看汇编输出。
作为一个有趣的历史注释,在Mark Probst的diploma thesis课程中,对C语言的尾部调用优化被添加到了GCC中。本文描述了实现过程中一些有趣的注意事项。这本书值得一读。
发布于 2008-10-21 03:13:21
gcc 4.3.2完全内联了这个函数(糟糕/琐碎的atoi()
实现)到main()
中。优化级别为-O1
。我注意到,如果我尝试使用它(即使将它从static
改为extern
,尾递归也会很快消失,所以我不会依赖它来保证程序的正确性。
#include <stdio.h>
static int atoi(const char *str, int n)
{
if (str == 0 || *str == 0)
return n;
return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
for (int i = 1; i != argc; ++i)
printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
return 0;
}
发布于 2016-02-26 18:28:47
除了显而易见的(编译器不会做这种优化,除非你要求),C++中的尾部调用优化也有一个复杂性:析构函数。
假设如下所示:
int fn(int j, int i)
{
if (i <= 0) return j;
Funky cls(j,i);
return fn(j, i-1);
}
编译器不能(通常)对此进行尾调用优化,因为它需要在递归调用返回后调用cls
的析构函数。
有时编译器可以看到析构函数没有外部可见的副作用(所以它可以提前完成),但通常不能。
一种特别常见的形式是Funky
实际上是一个std::vector
或类似的东西。
https://stackoverflow.com/questions/34125
复制相似问题