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

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

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

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

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

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

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

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

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

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

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

Взаимодействие между 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 #: Создание кода операции Tail-Call на C # и F #.

Вот статья с некоторыми примерами на C #, F # и C ++ \ CLI: Приключения в хвостовой рекурсии в C #, F # и C ++ \ CLI

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

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

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

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

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

Как упоминалось в других ответах, CLR поддерживает оптимизацию хвостового вызова, и, похоже, исторически происходили прогрессивные улучшения. Но поддержка его на C # имеет открытую Proposal проблему в репозитории git для разработки языка программирования C # Поддержка хвостовой рекурсии № 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();