Mr Andersson

An e-mail landed in my mailbox at work. It was a discussion which ended up in the following statement by my collegue Morten:
“- In theory you could also write that method using tail call recursion and in that way avoid eating up space on the call stack“.”

One of the brilliant guys I have the opportunity to work with is Morten. If you would put him in a movie, he would definitely play the role of the crazy scientist! He’s a guy which I love to discuss computer science with, when time allows for it.
So this time he made me dig deeper into how one could practially make our little recursive method “tail call recursive”.

I started out with two questions:
1) What the h-ck is tail call recursion? (no, I have no degree in CS)
2) Why is the temperature minus 26 degress celsius here in Rättvik, Sweden which makes me dig deeper into question 1 and prevents me and the kids go out dig deeper/play in the snow?

IF you now would try to do tail call recursion with our recursive method, would it be possible with C#?
Well, sure it is POSSIBLE. But it requires a bit more than Ctrl-Shift-B in Visual Studio. As we all know, in C#, we have little control of the native code being executed. For example we have the JIT compilator, which depends on which platform you are on. Code can also be inlined, something which now also applies to value types on the x86 platform (introduced in .NET 3.5 SP1). But except the jitter and the inlining we also have the seems-to-be-spot-on-target-at-first-look MSIL tail prefix…

Looking at a stack trace convering a call to a recursive method we can find the typical characteristics of a non-tail call recursive method:

at WaitForRunningThreads()at WaitForRunningThreads()at WaitForRunningThreads()at WaitForRunningThreads()at WaitForRunningThreads()at WaitForRunningThreads()…

By using tail call recursion it would look something like:

at WaitForRunningThreads()

Since there is no way I can make a tail call recursive method in C# produce such a stack trace by modifying the C# code, I need to patch the Release-compiled (using Visual Studio) IL code to make it use the MSIL tail prefix.

Suppose we have the following program:

class Program{static void Main(){ WaitForRunningThreads( 42 );}

static void WaitForRunningThreads( int n ){ System.Console.WriteLine( n ); System.Threading.Thread.Sleep( 100 ); if ( n < 2 )  throw new System.Exception(); WaitForRunningThreads( n / 2 );}}

With the following IL code output generated by csc.exe:

.class private auto ansi beforefieldinit Programextends [mscorlib]System.Object{.method private hidebysig static void  Main() cil managed{   .entrypoint   // Code size       8 (0x8)   .maxstack  8   IL_0000:  ldc.i4.s   42   IL_0002:  call       void Program::WaitForRunningThreads(int32)   IL_0007:  ret} // end of method Program::Main

.method private hidebysig static void  WaitForRunningThreads(int32 n) cil managed{   // Code size       32 (0x20)   .maxstack  8   IL_0000:  ldarg.0   IL_0001:  call       void [mscorlib]System.Console::WriteLine(int32)   IL_0006:  ldc.i4.s   100   IL_0008:  call       void [mscorlib]System.Threading.Thread::Sleep(int32)   IL_000d:  ldarg.0   IL_000e:  ldc.i4.2   IL_000f:  bge.s      IL_0017

   IL_0011:  newobj     instance void [mscorlib]System.Exception::.ctor()   IL_0016:  throw

   IL_0017:  ldarg.0   IL_0018:  ldc.i4.2   IL_0019:  div   IL_001a:  call       void Program::WaitForRunningThreads(int32)   IL_001f:  ret} // end of method Program::WaitForRunningThreads

.method public hidebysig specialname rtspecialname   instance void  .ctor() cil managed   {   // Code size       7 (0x7)   .maxstack  8   IL_0000:  ldarg.0   IL_0001:  call       instance void [mscorlib]System.Object::.ctor()   IL_0006:  ret} // end of method Program::.ctor}

When we execute the program it produces the following output:

422110521

Unhandled Exception: System.Exception: Exception of type 'System.Exception' was thrown.at Program.WaitForRunningThreads(Int32 n) in Program.cs:line 13at Program.WaitForRunningThreads(Int32 n) in Program.cs:line 14at Program.WaitForRunningThreads(Int32 n) in Program.cs:line 14at Program.WaitForRunningThreads(Int32 n) in Program.cs:line 14at Program.WaitForRunningThreads(Int32 n) in Program.cs:line 14at Program.WaitForRunningThreads(Int32 n) in Program.cs:line 14at Program.Main() in Program.cs:line 5

As mentioned before, we have no option giving the C# compiler a hint nor optimization option which will make it emit the MSIL tail prefix. What we can do for sure is patching the IL code using ILDASM/ILASM to include the tail prefix in WaitForRunningThreads():

.method private hidebysig static void  WaitForRunningThreads(int32 n) cil managed{// Code size       33 (0x21).maxstack  8IL_0000:  ldarg.0IL_0001:  call       void [mscorlib]System.Console::WriteLine(int32)IL_0006:  ldc.i4.s   100IL_0008:  call       void [mscorlib]System.Threading.Thread::Sleep(int32)IL_000d:  ldarg.0IL_000e:  ldc.i4.2IL_000f:  bge.s      IL_0017

IL_0011:  newobj     instance void [mscorlib]System.Exception::.ctor()IL_0016:  throw

IL_0017:  ldarg.0IL_0018:  ldc.i4.2IL_0019:  divIL_001a:  tail.IL_001b:  call       void Program::WaitForRunningThreads(int32)IL_0020:  ret}

The following is executed from a Visual Studio Command Prompt in the output directory:

> ildasm RTail.exe /out=rtail.il

> copy rtail.il rtail_modified.il

> notepad rtail_modified.il

(add the tail prefix as illustrated above)

> ilasm rtail_modified.il /out:rtail_modified.exe

..and the results are:

> rtail_modified.exe422110521

Unhandled Exception: System.Exception: Exception of type 'System.Exception' was thrown.at Program.WaitForRunningThreads(Int32 n)at Program.Main()

Voila!
The MSIL tail prefix pops the call stack BEFORE the call instruction and makes our stack trace look like we are using tail call recursion. Nice, huh?

But, if we dig deeper into the differencies of the platform dependent JIT compilators we can find that this is done by the jitter on 64-bit platforms:

“In fact, on 64-bit platforms, the CLR tries to do tail calls even if the tail. prefix is not specified. This is because platform-independent IL programs will get the same amount of stack space reserved for them by the OS, even though the 64-bit process will consume stack at a faster rate. Hence, we try to reduce stack usage by doing tail calls.“

Which part do I not get here?

Why can’t the C# compilator do this optimization?

Why rely on the JIT compilator to do such an optimization?

Luke Hoban (nowadays on the F# team) gives me some answers in a feedback response:

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

Also this statement (and the code in context) makes me think this is something closer to functional programming languages like F# rather than C#:

““I would have to assume the C# compiler team is using every trick in the book to make highly performant IL”

Are you kidding? The C# compiler does far less stuff, as you just saw right here. The F# compiler determined the code was a loop, and compiled it so. (It didn’t need to use the tail prefix ’cause it did even better.) I’m not saying the C# compiler doesn’t optimize, but it tries to keep a direct mapping from source to IL. (I think this is even sort of a goal for the C# compiler).“

More knowledge is brought to me by Jomo Fishers (also member of the F# team) with his post Adventures in F# – Recursion in Three Languages:

“This tradeoff frees up the C# team to focus on things like LINQ.“

=)

After reading the web pages linked from this post and a numerous of other about this topic, I believe I can stop bother about tail call recursion in my C# code.

Unfortunately I could not solve the problem of avoid having a recursive C# method eat up stack space, but at least I learned something about jitters, compiler optimization, the CLR and I definitely can say I now know the answer to my first question!