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

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

143 голосов
/ 29 августа 2008

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

Какие-нибудь компиляторы C ++ выполняют эту оптимизацию? Зачем? Почему нет?

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

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

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

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

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

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

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

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

Ответы [ 5 ]

118 голосов
/ 29 августа 2008

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

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

21 голосов
/ 21 октября 2008

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;
}
12 голосов
/ 26 февраля 2016

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

11 голосов
/ 29 августа 2008

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

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

7 голосов
/ 16 сентября 2008

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

...