Thursday, January 23, 2003

Tailcall

It seems that the .NET runtime is significantly slower in executing tailcalls than in executing "regular" function calls.

For those that have't used a functional programming language, a tailcall is just like a regular function call except you don't blow the stack if you call a function recursively too many times. This is done by effectively jumping into the function you are calling instead of calling it.

One usually expects a tailcall to be significantly faster than a regular call. In functional languages like OCaml you use recursion instead of loops, and things work just as fast as they do when you code the loop in C. Not so in .NET.

I wrote two versions of a recursive function, one that uses a tailcall and one that doesn't. Here is the original C# source of the function:

private static double Test1 (double d, int k) {
    if (k > 1) {
        return Test1 (d * (k + 1) / k, k - 1);
    }
    else {
        return d;
    }
}

The corresponding IL code is:

.method private hidebysig static float64 
        Test1(float64 d,
              int32 k) cil managed
{
  // Code size       24 (0x18)
  .maxstack  3
  IL_0000:  ldarg.1
  IL_0001:  ldc.i4.1
  IL_0002:  ble.s      IL_0016
  IL_0004:  ldarg.0
  IL_0005:  ldarg.1
  IL_0006:  ldc.i4.1
  IL_0007:  add
  IL_0008:  conv.r8
  IL_0009:  mul
  IL_000a:  ldarg.1
  IL_000b:  conv.r8
  IL_000c:  div
  IL_000d:  ldarg.1
  IL_000e:  ldc.i4.1
  IL_000f:  sub
  IL_0010:  call       float64 TailCallTest.EntryPoint::Test1(float64,
                                                              int32)
  IL_0015:  ret
  IL_0016:  ldarg.0
  IL_0017:  ret
}

To make that into a tailcall, simply add the tail. token before the call token:

.method public hidebysig static float64  Test2(float64 d,
                                               int32 k) cil managed
{
  // Code size       26 (0x1a)
  .maxstack  3
  IL_0000:  ldarg.1
  IL_0001:  ldc.i4.1
  IL_0002:  ble.s      IL_0018
  IL_0004:  ldarg.0
  IL_0005:  ldarg.1
  IL_0006:  ldc.i4.1
  IL_0007:  add
  IL_0008:  conv.r8
  IL_0009:  mul
  IL_000a:  ldarg.1
  IL_000b:  conv.r8
  IL_000c:  div
  IL_000d:  ldarg.1
  IL_000e:  ldc.i4.1
  IL_000f:  sub
  IL_0010:  tail.
  IL_0012:  call       float64 TailCallClass::Test2(float64,
                                                    int32)
  IL_0017:  ret
  IL_0018:  ldarg.0
  IL_0019:  ret
}

I have a test that calls each of these 10000 times, with parameters d = 1 and k = 20000 (k is chosen so as not to blow the stack of the non-tailcall version). The regular function executes in ~ 15 seconds on my laptop, while the tailcall version takes ~ 25 seconds.

So much for language neutrality in .NET.

The code that demonstrates this can be found here.

   12:45 AM