IL Tweaks

IL Tweaks Part2


first part can be found here.

This time around the code example can be called a jigsaw then a real functional code, but it will show some very important code optimization that can be made in C#, a little tip is that F# uses this technique when generating IL code, so this might ring some bells to those that program in F# :-).

Let's jump straight to code, so consider the following:

public static T f1<T>(int n)
{
    return f2<T>(n + 1);
}

public static T f2<T>(int n)
{
    return f1<T>(n + 1);
}

When we run the code calling either of those two methods, we will get stack overflow exception, as recurrence calls are using a local stack where the local data of the function call is stored, but as you can see here it will go to infinity and our stack just can't handle infinity, thus resulting in a exception. Another thing of the stack based recurrence is that it's slow.

Let The Magic Begin

Ok so now let's decompile the code (my exe was on C):

ildasm C:\Test.exe /out=C:\test.il

So now lets locate our methods part in IL, and see how can we make it work without exceptions.

.method public hidebysig static !!T f1(int32 n) cil managed
{
// Code size 9 (0x9)
.maxstack 8
IL_0000: ldarg.0
IL_0001: ldc.i4.1
IL_0002: add
IL_0003: call !!0 ConsoleApplication2.Program::f2(int32)
IL_0008: ret
} // end of method Program::f1

.method public hidebysig static !!T f2(int32 n) cil managed
{
// Code size 9 (0x9)
.maxstack 8
IL_0000: ldarg.0
IL_0001: ldc.i4.1
IL_0002: add
IL_0003: call !!0 ConsoleApplication2.Program::f1(int32)
IL_0008: ret
} // end of method Program::f2


The key thing here is something thats called a Tail call. Normally a recursive call is a stack based, meaning it is stored in a stack, but with tall calls it isn't the subroutine can be considered a jump call, so there is no exception as the code will jump from place to place and never use up the stack. With tail calls a recursive problem can be just as fast as non recursive or sometimes even faster, building up sequences can be an excellent example.


To make a tail call add a "tail." opcode in both methods here:

IL_0002: add
tail.
IL_0003: call ...
IL_0008: ret

and assemble the code.


ilasm C:\test.il /out=C:\TestTail.exe


Now when you run the code, you will not get any exceptions, meaning that the tail call works as it should.

Now why C# compiler doesn't use this feature? This probably due the backwards capability, but I can't be sure of this, but it's possible as the newer languages on the NET platform make use of this feature. One language that uses tail calls is F# but in this exact example tail calls will not be used, because F# compiles is kinda 'smart' and will use other techniques of optimization.

The F# Way


When I tried this example in F# I did get an compile time exception.

let rec f1 n = f2(n+1);
let rec f2 n = f1(n+1);

"The value or constructor 'f2' is not defined".

So it would seam that such scenario is impossible in the first place, but then again this would mean a big limitation in some subset of scenarios. So i goggled around and found that in F# there is a special syntax for that.

let rec f1 n = 
    f2 (n+1)
and f2 n = 
    f1 (n+1)

Now it would seam that F# will use a tail call here, but no. I'm not going to get into IL this time as it's bigger this time around, but instead we will look, what code the compiler generated in C# using the reflector or some other disassembler.

public static a f1<a>(int n)
{
    return f2<a>(n + 1);
}

public static a f2<a>(int n)
{
    while (true)
    {
        int num = n + 1;
        n = num + 1;
    }
}

As you see the code is actually a infinite loop, so we could say that the F# compiler is smart enough to detect that, and generate the best possible code.

Concluding


Tail calls can be a game changer when dealing with recursive problems, like tree parsing etc, I can think of at least of two such problems I had to do in my previous jobs that would fit tail calling just fine, so if you are dealing with a lot of recursion you might want to check that out.