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

Question

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

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

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

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

    Foo(i+1);
}

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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: Приключения в хвостовой рекурсии на C #, F # и C ++ \ CLI

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

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

Answer 4

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

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

Answer 5

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