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

StackOverflow https://stackoverflow.com/questions/34125

Вопрос

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

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

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

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

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

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

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

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

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

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

Это было полезно?

Решение

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top