Почему .NET / C # не оптимизирован для рекурсии хвостового вызова?

111

Я нашел этот вопрос о том, какие языки оптимизируют хвостовую рекурсию. Почему C # по возможности не оптимизирует хвостовую рекурсию?

В конкретном случае, почему этот метод не оптимизирован для создания цикла ( 32-разрядная версия Visual Studio 2008 , если это имеет значение) ?:

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}
ripper234
источник
Сегодня я читал книгу о структурах данных, в которой рекурсивная функция делится на две, а именно preemptive(например, факториальный алгоритм) и Non-preemptive(например, функция Аккермана). Автор привел всего два примера, о которых я упомянул, без должного обоснования этой раздвоения. Эта бифуркация такая же, как хвостовые и нехвостовые рекурсивные функции?
RBT
5
Полезный разговор об этом Джона Скита и Скотта Хансельмана в
Дэниел Б.
@RBT: Я думаю, что это другое. Это относится к количеству рекурсивных вызовов. Хвостовые вызовы относятся к вызовам, которые появляются в хвостовой позиции, то есть последнее, что делает функция, так как она возвращает результат напрямую от вызываемого объекта.
JD

Ответы:

84

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

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

Сама среда CLR поддерживает оптимизацию хвостового вызова, но компилятор, зависящий от языка, должен знать, как сгенерировать соответствующий код операции, и JIT должен быть готов его уважать. F # F # будет генерировать соответствующие коды операций (хотя для простой рекурсии он может просто преобразовать все это в whileцикл напрямую). C # в CSC нет.

См. Это сообщение в блоге для получения некоторых подробностей (вполне возможно, что оно устарело, учитывая недавние изменения JIT). Обратите внимание, что CLR изменяется для 4.0, x86, x64 и ia64 будут уважать это .

ShuggyCoUk
источник
2
См. Также этот пост: social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/… в котором я обнаружил, что хвост работает медленнее, чем обычный вызов. Ээп!
плинтус
77

Этот отправленный отзыв Microsoft Connect должен ответить на ваш вопрос. Он содержит официальный ответ от Microsoft, поэтому я бы рекомендовал пойти по нему.

Спасибо за предложение. Мы рассмотрели создание инструкций хвостового вызова на нескольких этапах разработки компилятора C #. Однако есть некоторые тонкие проблемы, которые заставили нас избегать этого до сих пор: 1) На самом деле существует нетривиальные накладные расходы на использование инструкции .tail в CLR (это не просто инструкция перехода, поскольку хвостовые вызовы в конечном итоге становятся во многих менее строгих средах, таких как среды выполнения функционального языка, где хвостовые вызовы сильно оптимизированы). 2) Существует несколько реальных методов C #, в которых было бы законно генерировать хвостовые вызовы (другие языки поощряют шаблоны кодирования, которые имеют больше хвостовой рекурсии, и многие, которые в значительной степени полагаются на оптимизацию хвостового вызова, фактически выполняют глобальную перезапись (например, преобразования с продолжением передачи), чтобы увеличить количество хвостовой рекурсии). 3) Отчасти из-за 2) случаи переполнения стека методов C # из-за глубокой рекурсии, которая должна была пройти, довольно редки.

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

Кстати, как это было указано, стоит отметить , что хвостовая рекурсия будет оптимизирована на x64.

нолдорин
источник
3
Вы тоже можете найти это полезным: weblogs.asp.net/podwysocki/archive/2008/07/07/…
Нолдорин
Без проблем, рад, что ты нашел это полезным.
Noldorin
17
Спасибо, что процитировали это, потому что теперь это 404!
Роман Старков
3
Ссылка теперь исправлена.
luksan
15

C # не оптимизирован для рекурсии хвостового вызова, потому что для этого и предназначен F #!

Более подробно об условиях, которые не позволяют компилятору C # выполнять оптимизацию хвостового вызова, см. В этой статье: Условия хвостового вызова JIT CLR .

Взаимодействие между C # и F #

C # и F # очень хорошо взаимодействуют, и поскольку среда .NET Common Language Runtime (CLR) разработана с учетом этой возможности взаимодействия, каждый язык разработан с оптимизацией, специфичной для его целей и задач. Пример, показывающий, насколько легко вызвать код F # из кода C #, см. В разделе Вызов кода F # из кода C # ; пример вызова функций C # из кода F # см. в разделе « Вызов функций C # из F #» .

Информацию о взаимодействии делегатов см. В этой статье: Взаимодействие делегатов между F #, C # и Visual Basic .

Теоретические и практические различия между C # и F #

Вот статья, в которой рассматриваются некоторые различия и объясняются различия в конструкции рекурсии хвостового вызова между C # и F #: Генерация кода операции хвостового вызова в C # и F # .

Вот статья с некоторыми примерами на C #, F # и C ++ \ CLI: Adventures in Tail Recursion в C #, F # и C ++ \ CLI

Основное теоретическое различие заключается в том, что C # разработан с использованием циклов, тогда как F # разработан на принципах лямбда-исчисления. Если вам нужна очень хорошая книга по принципам лямбда-исчисления, см. Эту бесплатную книгу: « Структура и интерпретация компьютерных программ» Абельсона, Сассмана и Сассмана .

Очень хорошую вводную статью о хвостовых вызовах в F # см. В этой статье: Подробное введение в хвостовые вызовы в F # . Наконец, вот статья, которая описывает разницу между рекурсией без хвоста и рекурсией с хвостовым вызовом (в F #): хвостовая рекурсия и не хвостовая рекурсия в F-диез .

Devinbost
источник
8

Недавно мне сказали, что компилятор C # для 64-битной версии оптимизирует хвостовую рекурсию.

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

Александр Бризебуа
источник
8
Джиттер x64 делает это, а компилятор C # - нет
Марк Совул
Спасибо за информацию. Этот белый цвет отличается от того, что я думал ранее.
Alexandre Brisebois
3
Чтобы прояснить эти два комментария, C # никогда не испускает код операции CIL 'tail', и я считаю, что это все еще верно в 2017 году. Однако для всех языков этот код операции всегда является рекомендательным только в том смысле, что соответствующие колебания (x86, x64 ) будет молча игнорировать его, если различные условия не выполняются (ну, никакой ошибки, кроме возможного переполнения стека ). Это объясняет, почему вы вынуждены следовать за «хвостом» с помощью «ret» - это для этого случая. Между тем, джиттеры также могут применить оптимизацию, когда в CIL нет префикса «хвоста», опять же, если это считается целесообразным, и независимо от языка .NET.
Гленн
3

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

наием
источник
Батуты агрессивны (они представляют собой глобальное изменение соглашения о вызовах), примерно в 10 раз медленнее, чем надлежащее исключение хвостового вызова, и они скрывают всю информацию трассировки стека, что значительно затрудняет отладку и профилирование кода
JD
1

Как упоминалось в других ответах, CLR поддерживает оптимизацию хвостового вызова, и, похоже, исторически происходили прогрессивные улучшения. Но поддержка его в C # имеет нерешенную Proposalпроблему в репозитории git для разработки языка программирования C # Support tail recursion # 2544 .

Здесь вы можете найти полезные подробности и информацию. Например, @jaykrell упомянул

Позвольте мне поделиться тем, что я знаю.

Иногда обратный вызов - беспроигрышный результат. Это может сэкономить CPU. jmp дешевле, чем call / ret. Он может сохранить стек. Прикосновение к меньшему количеству стопки обеспечивает лучшую локальность.

Иногда хвостовой вызов - это потеря производительности, выигрыш стека. CLR имеет сложный механизм, в котором вызываемой стороне передается больше параметров, чем получено вызывающей стороной. Я имею в виду, в частности, больше места в стеке для параметров. Это медленно. Но это сохраняет стек. Он будет делать это только с хвостом. префикс.

Если параметры вызывающего объекта больше, чем параметры вызываемого объекта, это обычно довольно простое беспроигрышное преобразование. Могут быть такие факторы, как изменение позиции параметра с управляемого на целое число / число с плавающей запятой, создание точных карт StackMaps и т. Д.

Теперь есть еще один аспект - алгоритмы, требующие устранения хвостовых вызовов, чтобы иметь возможность обрабатывать произвольно большие данные с фиксированным / малым стеком. Дело не в производительности, а в способности бегать вообще.

Также позвольте мне упомянуть (в качестве дополнительной информации): когда мы генерируем скомпилированную лямбду с использованием классов выражений в System.Linq.Expressionsпространстве имен, есть аргумент с именем tailCall, который, как объясняется в его комментарии,

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

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


var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func<  >>(body:  , tailCall: true, parameters:  );

var myFunc =  myFuncExpression.Compile();
образ жизни
источник