Какие компиляторы C ++, если таковые имеются, выполняют оптимизацию хвостовой рекурсии?
Когда процесс заканчивается, большая часть его состояния все еще существует в ядре, потому что его родитель может все же захотеть рассмотреть несколько вещей, например его возвращаемое значение, которое необходимо сохранить где-то. Когда родитель вызывает wait () или waitpid (), он сообщает ядру выбросить все это, потому что это сделано с ним. Пока это не произойдет, ребенок сохраняет pid и использует ресурсы. Эти невоспитанные дочерние процессы называются зомби. Даже убийство зомби не удалит его, оно должно быть получено (wait-ed-on) его родителем. Если родитель умирает, они передаются в «init» в unix-системах, единственной задачей которых является ожидание того, что вещи очищают их.
Я никогда не слышал о «объектах зомби», но я предполагаю что это относится к вещам, которые либо не были очищены сборщиком мусора, либо имеют круговые ссылки или некоторые такие вещи, что они не будут очищены сборщиком мусора. Метафора довольно похожа: fork () == malloc (), wait () == free () на определенном уровне. (Конечно, не идеальная метафора.)
4 ответа
Все текущие основные компиляторы выполняют оптимизацию последнего вызова довольно хорошо (и делали больше десятилетия), даже для взаимно рекурсивных вызовов , таких как:
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, Лязга и ICC, использования
-O3
простой способ проверить, сделал ли компилятор оптимизацию, состоит в том, чтобы выполнить вызов, который иначе привел бы к переполнению стека — или рассмотрение вывода блока.
Как интересный исторический очерк, оптимизация последнего вызова для C была добавлена к GCC в ходе тезис диплома Mark Probst. Тезис описывает некоторые интересные протесты в реализации. Это стоит считать.
-
1Нет, как кавычка говорит, это игнорирует строку Замены (т.е. " whatever" в моем примере). – mercator 15 March 2010 в 13:25
Большинство компиляторов не делает никакого вида оптимизации в отладочная сборка.
При использовании VC, попробуйте сборку конечных версий включенной информацией PDB - это позволит Вам проследить через оптимизированное приложение, и необходимо, надо надеяться, видеть то, что Вы хотите тогда. Обратите внимание, однако, что отладка и трассировка оптимизированной сборки перейдут Вы вокруг повсеместно, и часто Вы не можете осмотреть переменные непосредственно, поскольку они только когда-либо заканчиваются в регистрах или оптимизированы далеко полностью. Это - "интересный" опыт...
-
1Присутствие или отсутствие продвижения "/" зависит от того, является ли правило перезаписи в глобальной конфигурации (где это существует) или .htaccess (где it' s разделенный ИМЯ ФАЙЛА К URL, отображающееся ). Используйте
/?для подшаблона, который будет работать в любом контексте. – outis 4 February 2011 в 21:06
Как Greg упоминает, компиляторы не сделают этого в режиме отладки. Для сборок отладки нормально быть медленнее, чем сборка напоминания, но они не должны отказывать чаще: и если Вы зависите от оптимизации последнего вызова, они могут сделать точно это. Из-за этого часто лучше переписать последний вызов как нормальный цикл.:-(
-
1или для ясности, обстоятельно объясните его как [redirect=404]. – Mark Stosberg 22 June 2012 в 14:56
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