Search

Friday, September 26, 2008

Tail call optimization

wall

I had posted about tail call and how .NET handles it before. However there was some email exchanges and confusion on internal DLs around it and so I thought I'd try to elaborate more on how .NET goes about handling tail calls

Let’s try to break this down a bit.

a) A piece of C# code contains tail recursion .

static void CountDown(int num)
{
Console.WriteLine("{0} ", num);
if (num > 0)
CountDown(--num);
}

-


b) The C# compiler does not optimize this and generates a normal recursive call in IL

 IL_000c:  ...
IL_000d:  ...
IL_000e:  sub
IL_000f:  dup
IL_0010:  starg.s num
IL_0012:  call void TailRecursion.Program::CountDown(int32)

-


c) The Jitter on seeing this call doesn’t optimize it in any way and just inserts a normal call instruction for the platform it targets (call for x86)


However, if any compiler is smart enough to add the tail. recursive IL statement then things change.


a) Scheme code

(define (CountDown n)
(if (= n 0)
n
(CountDown (- n 1))))

-


b) Hypothetical IronScheme compiler will generate (note for scheme it has to do the optimization)

 IL_000c:  ...
IL_000d:  ...
IL_000e:  sub
  tail.
IL_0023:  call void TailRecursion.Program::CountDown(int32)
IL_0029:  ret

-


c) Based on which JIT you are using and various other scenarios the JIT now may honour the tail. IL instruction and optimize this with a jmp when generating machine instruction


Please note the may in the very last point and refer to here for some instances where the optimization still might not take place…

No comments: