G++ 尾递归优化失败

Question

我提出这个问题的依据是我对我之前提出的问题的评论。一位用户回答说我可以有无限的尾递归堆栈。然而，这不是我在实践中发现的。为了说明我的观点，请看一下我的代码：

#include <iostream>
#include <string>

void tail_print(string& in, size_t& index) //prints in backwards
{
  if (index == 0)
    {
      cout << '$' << endl;
      return;
    }

  cout << in[index];
  index--;
  tail_print(in, index);
}

int main()
{
  string a("abc$");
  size_t pos = a.length()-1;
  tail_print(a, pos);
  return 0;
}

假设输入字符串 in 包含以下范围内的字符：1

代码编译为：g++ -pipe -std=c++14 -O2 $file -lm -o exe

这会抛出信号 11 (SIGSEG)。我不能准确地说出这在哪个输入上失败了，但我可以肯定地说这个信号的原因来自这个子例程（如果我用 for 循环向后打印字符就可以正常工作）。请注意，这是一个更大计划的一部分，因此可能存在不可预见的并发症（可能性很小）。无论哪种方式，如果尾递归优化导致 Whosebug 在 measy O(million) 深度。

我使用的是以下 g++ 版本：

~$ g++ --version
g++ (Ubuntu 5.5.0-12ubuntu1~16.04) 5.5.0 20171010

Answer 1

如果您依赖尾递归，您将受制于编译器是否选择优化您的代码。调试版本不会被优化，所以总是会失败。

在您的情况下，通过 std::cout 打印单个字符似乎是导致问题的原因。 libstdc++ 似乎通过调用来实现打印单个字符：

std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)

出于某种原因，这似乎会阻碍 GCC 10 之前的尾递归优化。所有版本的 Clang 也无法对此进行优化。

用 std::cout.put(in[index]) 替换 cout << in[index] 似乎允许所有版本的 GCC（至少低至 4.1.2）和 Clang 优化尾递归：https://godbolt.org/z/Th1bT8

有趣的是，直接调用 std::__ostream_insert 也可以（但不要那样做，因为你会依赖内部 libstdc++ 实现细节）：https://godbolt.org/z/9M5xd4

我认为通过 libstdc++ 中的各个级别的函数调用，您最终会得到（由于函数 char 参数被取值）：

char c = in[index];
std::__ostream_insert<char, std::char_traits<char> >(std::cout, &c, 1);

创建指向局部变量的指针似乎是阻止尾递归的原因：https://godbolt.org/z/KM4jGY，大概是因为编译器不知道被调用函数将如何处理该指针，所以它不能'不保证使用循环会有相同的行为。

由于所有尾递归都应该可以简单地用循环替换，因此最好不要依赖编译器的变幻莫测来为您完成它，这样即使在未优化的构建中也能正常工作：

void tail_print(const std::string& in, size_t index) //prints in backwards
{
    for (size_t i = index; i > 0; i--)
    {
        std::cout << in[i];
    }
    std::cout << "$\n";
}

G++ 尾递归优化失败

G++ tail recursion optimization failing

c++

linux

g++