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);
}

Solution 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.

Solution 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.

Solution 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.

Solution 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.

Solution 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!

View more solutions

Comments

[Noldorin]

You might find this helpful too: weblogs.asp.net/podwysocki/archive/2008/07/07/…

[plinth]

See also this post: social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/‌​… wherein I discover that tail is slower than a regular call. Eep!

[Noldorin]

No prob, glad you find it helpful.

[Mark Sowul]

The x64 jitter does this, but the C# compiler does not

[David Carvalho]

thanks for the information. This is white different then what I previously thought.

[Roman Starkov]

Thank you for quoting it, because it's now a 404!

[luksan]

The link is now fixed.

[Glenn Slayden]

Just to clarify these two comments, C# never emits the CIL 'tail' opcode, and I believe this is still true in 2017. However, for all languages, that opcode is always advisory only in the sense that the respective jitters (x86, x64) will silently ignore it if sundry conditions are not met (well, no error except possible stack overflow). This explains why you're forced to follow 'tail' with 'ret' -- it's for this case. Meanwhile, the jitters are also free to apply the optimization when there's no 'tail' prefix in the CIL, again as deemed appropriate, and regardless of the .NET language.

[Totti]

Trampolines are invasive (they are a global change to the calling convention), ~10x slower than proper tail call elimination and they obfuscate all stack trace information making it much harder to debug and profile code