Какие компиляторы C++, если таковые имеются, выполняют оптимизацию хвостовой рекурсии?

Мне кажется, что было бы очень хорошо выполнить оптимизацию хвостовой рекурсии как в C, так и в C++, но при отладке я никогда не вижу стека фреймов, который указывает на эту оптимизацию. Это хорошо, потому что стек говорит мне, насколько глубока рекурсия. Тем не менее, оптимизация тоже была бы неплохой.

Есть ли в C++ компиляторы такую ​​оптимизацию? Зачем? Почему бы и нет?

Как мне сказать компилятору сделать это?

  • Для MSVC: /O2 или же /Ox
  • Для GCC: -O2 или же -O3

Как насчет проверки, если компилятор сделал это в определенном случае?

  • Для MSVC включите вывод PDB, чтобы иметь возможность отслеживать код, а затем проверить код
  • Для GCC..?

Я бы по-прежнему принимал предложения о том, как определить, оптимизирована ли определенная функция таким образом компилятором (хотя я нахожу обнадеживающим, что Конрад говорит мне принять это)

Всегда можно проверить, делает ли это компилятор вообще, выполняя бесконечную рекурсию и проверяя, приводит ли это к бесконечному циклу или переполнению стека (я сделал это с GCC и выяснил, что -O2 достаточно), но я хочу иметь возможность проверить определенную функцию, которая, как я знаю, в любом случае прекратится. Я хотел бы иметь простой способ проверить это:)

После некоторого тестирования я обнаружил, что деструкторы разрушают возможность такой оптимизации. Иногда может стоить изменить область видимости определенных переменных и временных значений, чтобы убедиться, что они выходят за пределы области действия до начала оператора return.

Если какой-либо деструктор должен быть запущен после хвостового вызова, оптимизация хвостового вызова не может быть выполнена.

Источник

5 ответов

Решение

Все текущие основные компиляторы выполняют оптимизацию хвостовых вызовов достаточно хорошо (и делают это более десяти лет), даже для взаимно рекурсивных вызовов, таких как:

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 была добавлена ​​в GCC в ходе дипломной работы Марка Пробста. Диссертация описывает некоторые интересные предостережения в реализации. Это стоит прочитать.

Источник

Помимо очевидного (компиляторы не выполняют такого рода оптимизацию, пока вы не попросите об этом), есть сложность в оптимизации хвостового вызова в 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 или похожие.

Источник

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;
}
Источник

Большинство компиляторов не выполняют никакой оптимизации в отладочной сборке.

Если вы используете VC, попробуйте сборку релиза с включенной информацией о PDB - это позволит вам проследить через оптимизированное приложение, и вы должны надеяться увидеть то, что вам нужно. Обратите внимание, однако, что отладка и отслеживание оптимизированной сборки повсеместно обскакивает вас, и часто вы не можете проверять переменные напрямую, поскольку они только попадают в регистры или полностью оптимизируются. Это "интересный" опыт...

Источник

Как упоминает Грег, компиляторы не будут делать это в режиме отладки. Это нормально для отладочных сборок, которые работают медленнее, чем сборка prod, но они не должны давать сбои чаще: и если вы зависите от оптимизации хвостового вызова, они могут сделать именно это. Из-за этого часто лучше переписать хвостовой вызов как обычный цикл.:-(

Источник
Другие вопросы по тегам