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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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