Why doesn't .NET/C# optimize for tail-call recursion?

Question

I found this question about which languages optimize tail recursion. Why C# doesn't optimize tail recursion, whenever possible?

For a concrete case, why isn't this method optimized into a loop (Visual Studio 2008 32-bit, if that matters)?:

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

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

    Foo(i+1);
}

Answer 1

JIT compilation is a tricky balancing act between not spending too much time doing the compilation phase (thus slowing down short lived applications considerably) vs. not doing enough analysis to keep the application competitive in the long term with a standard ahead-of-time compilation.

Interestingly the NGen compilation steps are not targeted to being more aggressive in their optimizations. I suspect this is because they simply don't want to have bugs where the behaviour is dependent on whether the JIT or NGen was responsible for the machine code.

The CLR itself does support tail call optimization, but the language-specific compiler must know how to generate the relevant opcode and the JIT must be willing to respect it. F#'s fsc will generate the relevant opcodes (though for a simple recursion it may just convert the whole thing into a while loop directly). C#'s csc does not.

See this blog post for some details (quite possibly now out of date given recent JIT changes). Note that the CLR changes for 4.0 the x86, x64 and ia64 will respect it.

Answer 2

This Microsoft Connect feedback submission should answer your question. It contains an official response from Microsoft, so I'd recommend going by that.

Thanks for the suggestion. We've considered emiting tail call instructions at a number of points in the development of the C# compiler. However, there are some subtle issues which have pushed us to avoid this so far: 1) There is actually a non-trivial overhead cost to using the .tail instruction in the CLR (it is not just a jump instruction as tail calls ultimately become in many less strict environments such as functional language runtime environments where tail calls are heavily optimized). 2) There are few real C# methods where it would be legal to emit tail calls (other languages encourage coding patterns which have more tail recursion, and many that rely heavily on tail call optimization actually do global re-writing (such as Continuation Passing transformations) to increase the amount of tail recursion). 3) Partly because of 2), cases where C# methods stack overflow due to deep recursion that should have succeeded are fairly rare.

All that said, we continue to look at this, and we may in a future release of the compiler find some patterns where it makes sense to emit .tail instructions.

By the way, as it has been pointed out, it is worth noting that tail recursion is optimised on x64.

Answer 3

C# does not optimize for tail-call recursion because that's what F# is for!

For some depth on the conditions that prevent the C# compiler from performing tail-call optimizations, see this article: JIT CLR tail-call conditions.

Interoperability between C# and F#

C# and F# interoperate very well, and because the .NET Common Language Runtime (CLR) is designed with this interoperability in mind, each language is designed with optimizations that are specific to its intent and purposes. For an example that shows how easy it is to call F# code from C# code, see Calling F# code from C# code; for an example of calling C# functions from F# code, see Calling C# functions from F#.

For delegate interoperability, see this article: Delegate interoperability between F#, C# and Visual Basic.

Theoretical and practical differences between C# and F#

Here is an article that covers some of the differences and explains the design differences of tail-call recursion between C# and F#: Generating Tail-Call Opcode in C# and F#.

Here is an article with some examples in C#, F#, and C++\CLI: Adventures in Tail Recursion in C#, F#, and C++\CLI

The main theoretical difference is that C# is designed with loops whereas F# is designed upon principles of Lambda calculus. For a very good book on the principles of Lambda calculus, see this free book: Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman.

For a very good introductory article on tail calls in F#, see this article: Detailed Introduction to Tail Calls in F#. Finally, here is an article that covers the difference between non-tail recursion and tail-call recursion (in F#): Tail-recursion vs. non-tail recursion in F sharp.

Answer 4

I was recently told that the C# compiler for 64 bit does optimize tail recursion.

C# also implements this. The reason why it is not always applied, is that the rules used to apply tail recursion are very strict.

Answer 5

I had a happy surprise today :-)

I am reviewing my teaching material for my upcoming course on recursion with C#. And it seems that finally tail call optimization has made its way into C#.

I am using NET5 with LINQPad 6 (optimization activated).

Here is the Tail call optimizable Factorial function I used:

long Factorial(int n, long acc = 1)
{
    if (n <= 1)
        return acc;
    return Factorial(n - 1, n * acc);
}

And here is the X64 assembly code generated for this function:

See, there is no call, only a jmp. The function is agressively optimized as well (no stack frame setup/teardown). Oh Yes!

Answer 6

You can use the trampoline technique for tail-recursive functions in C# (or Java). However, the better solution (if you just care about stack utilization) is to use this small helper method to wrap parts of the same recursive function and make it iterative while keeping the function readable.

Answer 7

As other answers mentioned, CLR does support tail call optimization and it seems it was under progressive improvements historically. But supporting it in C# has an open Proposal issue in the git repository for the design of the C# programming language Support tail recursion #2544.

You can find some useful details and info there. For example @jaykrell mentioned

Let me give what I know.

Sometimes tailcall is a performance win-win. It can save CPU. jmp is cheaper than call/ret It can save stack. Touching less stack makes for better locality.

Sometimes tailcall is a performance loss, stack win. The CLR has a complex mechanism in which to pass more parameters to the callee than the caller recieved. I mean specifically more stack space for parameters. This is slow. But it conserves stack. It will only do this with the tail. prefix.

If the caller parameters are stack-larger than callee parameters, it usually a pretty easy win-win transform. There might be factors like parameter-position changing from managed to integer/float, and generating precise StackMaps and such.

Now, there is another angle, that of algorithms that demand tailcall elimination, for purposes of being able to process arbitrarily large data with fixed/small stack. This is not about performance, but about ability to run at all.

Also let me mention (as extra info), When we are generating a compiled lambda using expression classes in System.Linq.Expressions namespace, there is an argument named 'tailCall' that as explained in its comment it is

A bool that indicates if tail call optimization will be applied when compiling the created expression.

I was not tried it yet, and I am not sure how it can help related to your question, but Probably someone can try it and may be useful in some scenarios:

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

var myFunc =  myFuncExpression.Compile();