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

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

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

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

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

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

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

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

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

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

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


c++ optimization tail-recursion
person Magnus Hoff    schedule 29.08.2008    source источник

Ответы (5)


arrow_upward
136
arrow_downward

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

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

person Konrad Rudolph    schedule 29.08.2008
comment
Я считаю, что ICC так и поступит. Насколько мне известно, ICC производит самый быстрый код на рынке. - person Paul Nathan; 21.10.2008
comment
@Paul Вопрос в том, какая часть скорости кода ICC вызвана алгоритмической оптимизацией, такой как оптимизация хвостового вызова, а какая - оптимизацией кеша и микрокоманд, которую может сделать только Intel с ее глубоким знанием своих процессоров. - person Imagist; 28.09.2009
comment
gcc имеет более узкую опцию -foptimize-sibling-calls для оптимизации одноуровневых и хвостовых рекурсивных вызовов. Эта опция (согласно gcc(1) страницам руководства для версий 4.4, 4.7 и 4.8, предназначенных для различных платформ) включена на уровнях -O2, -O3, -Os. - person FooF; 10.01.2014
comment
Кроме того, работа в режиме DEBUG без явного запроса оптимизации НЕ будет выполнять НИКАКОЙ оптимизации вообще. Вы можете включить PDB для истинного режима выпуска EXE и попробовать пройти через него, но обратите внимание, что отладка в режиме выпуска имеет свои сложности - невидимые / разделенные переменные, объединенные переменные, переменные выходят из области видимости в неизвестной / неожиданной области, переменные, в которые они никогда не входят области и стали истинными константами с адресами на уровне стека, и - ну - слитыми или отсутствующими кадрами стека. Обычно объединенные кадры стека означают, что вызываемый объект встроен, а отсутствующие / объединенные кадры, вероятно, являются хвостовым вызовом. - person Петър Петров; 07.01.2015

arrow_upward
21
arrow_downward

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;
}
person Tom Barta    schedule 21.10.2008
comment
Тем не менее, вы можете активировать оптимизацию времени компоновки, и я предполагаю, что тогда даже метод extern может быть встроен. - person Konrad Rudolph; 01.02.2010
comment
Странный. Я только что протестировал gcc 4.2.3 (x86, Slackware 12.1) и gcc 4.6.2 (AMD64, Debian wheezy), и с -O1 нет встраивания и нет оптимизация хвостовой рекурсии. Вы должны использовать -O2 для этого (ну, в 4.2.x, который сейчас довольно древний, он по-прежнему не будет встроен). Кстати, также стоит добавить, что gcc может оптимизировать рекурсию, даже если она не является строго хвостовой (например, факториал без аккумулятора). - person przemoc; 15.01.2012

arrow_upward
19
arrow_downward

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

person Martin Bonner supports Monica    schedule 26.02.2016

arrow_upward
11
arrow_downward

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

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

person Greg Whitfield    schedule 29.08.2008
comment
попробуйте gcc why -g -O3 и оптимизируйте отладочную сборку. xlC ведет себя так же. - person g24l; 11.01.2015
comment
Когда вы говорите «большинство компиляторов»: какие коллекции компиляторов вы рассматриваете? Как уже указывалось, существует по крайней мере два компилятора, которые выполняют оптимизацию во время отладочной сборки - и, насколько я знаю, VC тоже это делает (кроме случаев, когда вы, возможно, разрешаете изменение и продолжение). - person skyking; 23.10.2017

arrow_upward
7
arrow_downward

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

person 0124816    schedule 16.09.2008