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

150

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

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

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

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

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

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

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

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


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

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

Магнус Хофф
источник

Ответы:

129

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

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

Конрад Рудольф
источник
Я думаю, что ICC сделает это. Насколько мне известно, ICC производит самый быстрый код на рынке.
Пол Натан
35
@Paul Вопрос состоит в том, какая часть скорости кода ICC обусловлена ​​алгоритмическими оптимизациями, такими как оптимизация хвостовых вызовов, и сколько вызвана оптимизацией кеша и микроинструкций, которую может сделать только Intel, обладая глубокими знаниями своих собственных процессоров.
Imagist
6
gccимеет более узкую опцию -foptimize-sibling-calls«оптимизировать родственные и хвостовые рекурсивные вызовы». Эта опция (по gcc(1)страницам справочника версий 4.4, 4.7 и 4.8 , ориентированный на различные платформы) включена на уровне -O2, -O3, -Os.
FooF
Кроме того, работа в режиме отладки без явного запроса на оптимизацию НЕ ДАЕТ никакой оптимизации. Вы можете включить PDB для истинного режима релиза EXE и попытаться пройти через это, но учтите, что отладка в режиме выпуска имеет свои сложности - невидимые / раздетые переменные, объединенные переменные, переменные выходят из области действия в неизвестной / неожиданной области видимости, переменные, в которые они никогда не попадут scope и стали настоящими константами с адресами стекового уровня и - хорошо - объединенными или отсутствующими кадрами стека. Обычно объединенные кадры стека означают, что вызываемый объект встроен, а отсутствующие / обратные кадры, вероятно, являются хвостовым вызовом.
Петър Петров
21

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;
}
Том Барта
источник
1
Вы можете активировать оптимизацию во время соединения, и я думаю, что тогда даже externметод может быть встроен.
Конрад Рудольф
5
Странный. Я просто проверял GCC 4.2.3 (x86, Slackware 12.1) и GCC 4.6.2 (AMD64, Debian свистящих) и с-O1 нет нет встраивания и нет оптимизации хвостовой рекурсии . Вы должны использовать -O2для этого (ну, в 4.2.x, который довольно древний, он все еще не будет встроен). Кстати, также стоит добавить, что gcc может оптимизировать рекурсию, даже если она не является строго хвостовой (как, например, факториал без аккумулятора).
przemoc
16

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

Мартин Боннер поддерживает Монику
источник
Не работает для меня. Системы говорят мне, что мой голос заблокирован, пока ответ не отредактирован.
hmuelner
Просто отредактировал ответ (убрал парантезы) и теперь я могу отменить свое отрицательное голосование.
Hmuelner
11

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

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

Грег Уитфилд
источник
2
попробуйте gcc why -g -O3 и получить оптимизацию в отладочной сборке. XLC имеет такое же поведение.
g24l
Когда вы говорите «большинство компиляторов»: какие коллекции компиляторов вы рассматриваете? Как указывалось, есть по крайней мере два компилятора, которые выполняют оптимизацию во время отладочной сборки - и, насколько я знаю, VC делает это тоже (за исключением случаев, когда вы, возможно, разрешаете изменять и продолжать).
скайкинг
7

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

0124816
источник