哪个(如果有的话)C ++编译器会进行尾递归优化?

哪个(如果有的话)C ++编译器会进行尾递归优化?

Which, if any, C++ compilers do tail-recursion optimization?

在我看来,在C和C ++中进行尾递归优化是完美的,但是在调试时我似乎永远不会看到表示此优化的帧堆栈。这有点好,因为堆栈告诉我递归的深度。但是,优化也会很好。

是否有任何C ++编译器进行此优化?为什么?为什么不?

我如何告诉编译器这样做?

  • 对于MSVC:/O2/Ox
  • 对于GCC:-O2-O3

如何在某种情况下检查编译器是否已完成此操作?

  • 对于MSVC,启用PDB输出以跟踪代码,然后检查代码
  • 对于GCC ..?

我仍然会建议如何确定编译器是否对某个函数进行了优化(尽管我发现它让人放心,Konrad告诉我假设它)

总是可以通过进行无限递归来检查编译器是否完成此操作,并检查它是否导致无限循环或堆栈溢出(我用GCC做了这个并发现-O2就足够了),但是我希望能够检查我知道会终止的某个功能。我很想有一个简单的方法来检查这个:)

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

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


所有当前的主流编译器都能很好地执行尾调优化(并且已经完成了十多年),即使对于相互递归的调用,例如:

1
2
3
4
5
6
7
8
9
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

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

作为一个有趣的历史记录,在Mark Probst的毕业论文中,C的尾调优化被添加到GCC。论文描述了实施中的一些有趣的警告。值得一读。


gcc 4.3.2将此函数(crappy / trivial atoi()实现)完全内联到main()中。优化级别-O1。我注意到如果我玩它(甚至将它从static更改为extern,尾递归相当快,所以我不会依赖它来获得程序的正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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
"
, argv[i], atoi(argv[i], 0));
    return 0;
}


除了显而易见之外(编译器不会进行这种优化),C ++中的尾调用优化存在一个复杂性:析构函数。

给出如下内容:

1
2
3
4
5
6
   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

编译器不能(通常)尾调用优化它,因为它需要
在递归调用返回后调用cls的析构函数。

有时编译器可以看到析构函数没有外部可见的副作用(因此可以尽早完成),但通常不能。

其中特别常见的形式是Funky实际上是std::vector或类似的。


大多数编译器在调试版本中不进行任何类型的优化。

如果使用VC,请尝试打开PDB信息的版本构建 - 这将允许您跟踪优化的应用程序,您应该希望看到您想要的。但请注意,调试和跟踪优化的构建将使您四处奔走,并且通常无法直接检查变量,因为它们只会在寄存器中结束或完全被优化掉。这是一次"有趣"的体验......


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


推荐阅读

    3500元超额值学生娱乐结构的优化配置

    3500元超额值学生娱乐结构的优化配置,,作为一个DIY的主流用户领域的学生,每个用户51学生攒机的高峰。因为学生用户没有稳定的收入来源,攒机

    优化PostgreSQL中的批量更新性能

    优化PostgreSQL中的批量更新性能,数据,表格,在Ubuntu 12.04上使用PG 9.1. 我们目前需要24小时才能运行大量UPDATE数据库上的语句,其形式

    512内存的电脑优化|笔记本内存512

    512内存的电脑优化|笔记本内存512,,1. 笔记本内存512够用,因为运行非常流畅,苹果笔记本 16g512的运行内存是16g内存,机身内存是512g内存,运行

    Windows7下固态硬盘的优化技术

    Windows7下固态硬盘的优化技术,,当微软开发Windows Vista时,固态硬盘没有那么热,所以没有进行优化。Windows 7是不同的。微软从一开始就把SS

    记一次服务端系统性能优化

    记一次服务端系统性能优化,在线,设备, 首先简单介绍一下业务场景,物联网设备,关注公众号,免费领取环保袋。12月8号,也就是昨天上午,突然接

    计算机主板故障调试代码

    计算机主板故障调试代码,,核心提示:故障代码含义查找表的调试代码查找表来读:(注1),特殊代码00和FF等起始码有三种情况:一系列其他代码:00或FF,好

    幻灯片放映慢优化可以加快速度

    幻灯片放映慢优化可以加快速度,,用于制作幻灯片的一些技术更复杂,这些幻灯片在一些旧机器上运行缓慢或缓慢。在这种情况下,我们应该如何优化

    电脑cpu调整软件|电脑优化cpu的软件

    电脑cpu调整软件|电脑优化cpu的软件,,1. 电脑优化cpu的软件出现这个问题归根到底是因为你是用的模拟器,而模拟器是比较卡顿的,尤其在配置比

    bios优化设置|bios的优化设置

    bios优化设置|bios的优化设置,,1. bios的优化设置开机按del键,在bios设置菜单中选择loadfall-safe defaults,在弹出的确认提示中按y键即可