当前位置：文江博客话题详情

其中，如果有的话，C++ 编译器进行尾递归优化吗？

发布于 2024-07-04 02:46:16 字数 703 浏览 6 评论 0原文

在我看来，在 C 和 C++ 中进行尾递归优化都可以很好地工作，但在调试时我似乎从未看到表明这种优化的帧堆栈。这很好，因为堆栈告诉我递归的深度。不过，优化也会很好。

有 C++ 编译器进行此优化吗？为什么？为什么不？

我该如何告诉编译器去做呢？

对于 MSVC：/O2 或 /Ox
对于 GCC：-O2 或 -O3

如何检查编译器是否在某种情况下这样做过吗？

对于 MSVC，启用 PDB 输出以便能够跟踪代码，然后检查代码
对于 GCC..？

我仍然会建议如何确定编译器是否像这样优化某个函数（尽管康拉德告诉我假设它让我放心）

总是可以通过以下方式检查编译器是否这样做进行无限递归并检查它是否导致无限循环或堆栈溢出（我使用 GCC 执行此操作并发现 -O2 就足够了），但我希望能够检查某个我知道无论如何都会终止的函数。我很想有一种简单的方法来检查这一点:)

经过一些测试，我发现析构函数破坏了进行此优化的可能性。有时更改某些变量和临时变量的范围是值得的，以确保它们在返回语句开始之前超出范围。

如果尾部调用后需要运行任何析构函数，则无法进行尾部调用优化。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

不再见 2024-07-11 02:46:17

正如 Greg 提到的，编译器不会在调试模式下执行此操作。调试构建比产品构建慢是可以的，但它们不应该更频繁地崩溃：如果您依赖尾部调用优化，它们可能会这样做。因此，通常最好将尾部调用重写为普通循环。 :-(

回复收藏 0 原文

动听の歌 2024-07-11 02:46:16

当前所有主流编译器都可以很好地执行尾调用优化（并且已经这样做了十多年），即使对于相互递归调用，例如：

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.
对于 GCC、Clang 和 ICC，请使用 -O3

检查编译器是否进行优化的一种简单方法是执行否则会导致堆栈溢出的调用，或者查看汇编输出。

作为一个有趣的历史记录，C 的尾部调用优化在

All current mainstream compilers perform tail call optimisation fairly well (and have done for more than a decade), even for mutually recursive calls such as:

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);
}

Letting the compiler do the optimisation is straightforward: Just switch on optimisation for speed:

For MSVC, use /O2 or /Ox.
For GCC, Clang and ICC, use -O3

An easy way to check if the compiler did the optimisation is to perform a call that would otherwise result in a stack overflow — or looking at the assembly output.

As an interesting historical note, tail call optimisation for C was added to the GCC in the course of a diploma thesis by Mark Probst. The thesis describes some interesting caveats in the implementation. It's worth reading.

回复收藏 0 原文

掐死时间 2024-07-11 02:46:16

除了显而易见的事情（除非您要求，否则编译器不会执行此类优化），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 或类似的。

As well as the obvious (compilers don't do this sort of optimization unless you ask for it), there is a complexity about tail-call optimization in C++: destructors.

Given something like:

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

The compiler can't (in general) tail-call optimize this because it needs
to call the destructor of cls after the recursive call returns.

Sometimes the compiler can see that the destructor has no externally visible side effects (so it can be done early), but often it can't.

A particularly common form of this is where Funky is actually a std::vector or similar.

回复收藏 0 原文

私藏温柔 2024-07-11 02:46:16

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;
}

gcc 4.3.2 completely inlines this function (crappy/trivial atoi() implementation) into main(). Optimization level is -O1. I notice if I play around with it (even changing it from static to extern, the tail recursion goes away pretty fast, so I wouldn't depend on it for program correctness.

#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;
}

回复收藏 0 原文