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

Я нашел этот вопрос о том, какие языки оптимизируют хвостовую рекурсию. Почему 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);
}
5 92
c# .net optimization tail-recursion

5 ответов:

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

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

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

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

75

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

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

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

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

67

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

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

совместимость между C# и F#

C# и F# взаимодействуют очень хорошо, и поскольку среда CLR .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:приключения в хвостовой рекурсии в C#, F# и C++\CLI

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

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

13

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

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

8

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

3