Ошибка оптимизации хвостовой рекурсии G ++ - PullRequest
Новая
       42

Ошибка оптимизации хвостовой рекурсии G ++

1 голос
/ 01 августа 2020

Я основываю этот вопрос на комментарии, который я получил к предыдущему вопросу, который я задал здесь . Пользователь ответил, что у меня могут быть бесконечные стеки рекурсии хвоста. Однако это не то, что я обнаружил на практике. Чтобы проиллюстрировать мою точку зрения, взгляните на мой код: 

#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

1 Ответ

1 голос
/ 01 августа 2020

Если вы полагаетесь на хвостовую рекурсию, вы зависите от компилятора, решит ли он оптимизировать ваш код. Сборки отладки не будут оптимизированы, поэтому всегда будут терпеть неудачу.

В вашем случае печать одного символа через 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)

По какой-то причине это, похоже, сбивает оптимизацию хвостовой рекурсии до G CC 10. Все версии Clang тоже не могут оптимизировать это. .

Замена cout << in[index] на std::cout.put(in[index]), похоже, позволяет всем версиям G CC (по крайней мере, до 4.1.2) и Clang оптимизировать хвостовую рекурсию: https://godbolt.org/z/Th1bT8

Интересно, что вызов std::__ostream_insert напрямую также работает (но не делайте этого, поскольку в этом случае вы полагаетесь на внутренние детали реализации libstdc ++): https://godbolt.org/z/9M5xd4

I продумайте различные уровни вызова функций в libstdc ++ , которые вы получите (из-за того, что аргумент функции char принимается по значению): 

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

Создание указателя на локальный кажется, что именно переменная предотвращает хвостовую рекурсию: https://godbolt.org/z/KM4jGY, по-видимому, это потому, что компилятор не может знать, что вызываемая функция будет делать с этим указателем, поэтому он не может гарантировать, что использование al oop wi будет иметь такое же поведение. сборка: 

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