Почему.NET/C# не оптимизируется для рекурсии хвостового вызова?
Я нашел этот вопрос о том, какие языки оптимизируют хвостовую рекурсию. Почему 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);
}
7 ответов
JIT-компиляция представляет собой сложный баланс между тем, чтобы не тратить слишком много времени на этап компиляции (таким образом, значительно замедляя недолговечные приложения), и не делать достаточно анализа, чтобы поддерживать конкурентоспособность приложения в долгосрочной перспективе с помощью стандартной опережающей компиляции.,
Интересно, что шаги компиляции NGen не направлены на то, чтобы быть более агрессивными в их оптимизации. Я подозреваю, что это потому, что они просто не хотят иметь ошибок, поведение которых зависит от того, был ли JIT или NGen ответственным за машинный код.
Сам CLR поддерживает оптимизацию хвостового вызова, но компилятор для конкретного языка должен знать, как генерировать соответствующий код операции, и JIT должен быть готов соблюдать его. Fsc F# сгенерирует соответствующие коды операций (хотя для простой рекурсии он может просто конвертировать все в while цикл непосредственно). C# не работает.
См. Этот пост в блоге для некоторых деталей (вполне возможно, теперь устарел, учитывая недавние изменения JIT). Обратите внимание, что CLR изменяется на 4.0, x86, x64 и ia64 будут уважать его.
Это сообщение обратной связи от Microsoft Connect должно ответить на ваш вопрос. Он содержит официальный ответ от Microsoft, поэтому я бы рекомендовал пойти по этому.
Спасибо за предложение. Мы рассмотрели возможность использования команд хвостового вызова в ряде моментов при разработке компилятора C#. Однако, есть некоторые тонкие проблемы, которые подтолкнули нас к тому, чтобы избежать этого до сих пор: 1) На самом деле нет нетривиальных накладных расходов на использование инструкции.tail в CLR (это не просто инструкция перехода, поскольку конечные вызовы в конечном итоге становятся во многих менее строгих средах, таких как среды выполнения функциональных языков, где хвостовые вызовы сильно оптимизированы). 2) Существует немного реальных методов C#, в которых было бы законно выдавать хвостовые вызовы (другие языки поощряют шаблоны кодирования, которые имеют большую хвостовую рекурсию, и многие, которые в значительной степени полагаются на оптимизацию хвостовых вызовов, действительно выполняют глобальную переписывание (например, преобразования Continuation Pass) увеличить количество хвостовой рекурсии). 3) Частично из-за 2) случаи, когда методы C# переполняют стек из-за глубокой рекурсии, которая должна была быть успешной, довольно редки.
Все это говорит о том, что мы продолжаем смотреть на это и, возможно, в будущем выпуске компилятора найдут некоторые шаблоны, в которых имеет смысл выдавать инструкции.tail.
Кстати, как уже указывалось, стоит отметить, что хвостовая рекурсия оптимизирована на x64.
C# не оптимизирован для рекурсии хвостового вызова, потому что это то, для чего F#!
Для некоторой глубины об условиях, которые мешают компилятору C# выполнять оптимизацию хвостового вызова, см. Эту статью: Условия хвостового вызова JIT CLR.
Совместимость между C# и F#
C# и F# взаимодействуют очень хорошо, и, поскольку среда выполнения.NET (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: Приключения в Tail Recursion в C#, F# и C++ \ CLI
Основное теоретическое отличие состоит в том, что C# разработан с использованием циклов, тогда как F# разработан на принципах лямбда-исчисления. Очень хорошую книгу о принципах лямбда-исчисления см. В этой бесплатной книге Абелсона, Суссмана и Суссмана "Структура и интерпретация компьютерных программ".
Для очень хорошей вводной статьи по хвостовым вызовам в F# см. Эту статью: Подробное введение в хвостовые вызовы в F#. Наконец, вот статья, в которой рассматривается различие между рекурсией без хвоста и рекурсией с хвостовым вызовом (в F#): рекурсия с хвостом против рекурсии без хвоста в F sharp.
Мне недавно сказали, что компилятор C# для 64 бит оптимизирует хвостовую рекурсию.
C# также реализует это. Причина, по которой он не всегда применяется, состоит в том, что правила, применяемые для применения хвостовой рекурсии, очень строги.
Сегодня меня ждал приятный сюрприз :-)
Я просматриваю свой учебный материал для моего предстоящего курса по рекурсии с C#. И, кажется, наконец-то оптимизация хвостовых вызовов добралась и до C#.
Я использую NET5 с LINQPad 6 (активирована оптимизация).
Вот оптимизируемая функция Factorial, которую я использовал для вызова Tail:
long Factorial(int n, long acc = 1)
{
if (n <= 1)
return acc;
return Factorial(n - 1, n * acc);
}
А вот ассемблерный код X64, сгенерированный для этой функции:
Видишь, нет
call, только
jmp. Функция также агрессивно оптимизирована (без настройки/удаления фрейма стека). О да!
Вы можете использовать технику батута для хвостовых рекурсивных функций в 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();