Cook Computing

Tailcalls in .NET

January 25, 2003 Written by Charles Cook

Pinku Surana has described why the lack of tagged datatypes in .NET makes it difficult for dynamically typed languages such as Scheme to perform as well as languages like C#. A couple of days ago Dejan Jelovic posted to the Advanced .NET list on the poor performance of tailcalls in .NET. This will also hinder languages such as Scheme:

Something seems to be wrong with the way tailcall is implemented in the .NET runtime. Instead of being faster than a regular call, it's roughly 70 percent slower.

Tailcalls occur where the last step in a method, say Foo, is a call to another method, say Bar, such that Foo simply returns the result of Bar. The significant point is that once the second method has been called we are no longer interested in the stack frame of the first method, so instead of extending the stack with another frame for method Bar, the frame for Foo can be discarded and replaced by Bars stack frame. This means that we dont have to worry about stack oveflow. In general the two methods can be different but the recursive case where a method calls itself is of particular interest.

Many Scheme programs rely heavily on recursion instead of the looping constructs used in languages such as C# and Java, and it is for this reason that tail call optimization is important in avoiding stack overflow; hence Dejans concern. His blog describes the code he used to demonstrate the performance hit of tailcall.

I wrote a tailcall recursive method for generating the factorial of a number and compiled it with both the Microsoft and Mono compilers:


// call with n = number for which factorial required, a = 1
static long Factorial(long n, long a)
{
  if (n == 0)
    return a;
  return Factorial(n - 1, n * a);
}

Neither compiler generates the tail. prefix instruction which would turn the recursive call into a tailcall:


  IL_0011:  tail.
  IL_0013:  call int64 clasas::Factorial(int64, int64)
  IL_0018:  ret
} // end of method clasas::Factorial

I guess this is an optimization which may be implemented later on. As an aside, gcc supports tailcall optimization to some extent.

Regarding the performance of tailcall in .NET, Jim Hogg of Microsoft replied that the JIT team has plans to improve it.

Postscript: while investigating tailcalls I came across continuations. These look very interesting, not something you come across as a C++/C# developer which is probably why I'm finding it difficult to get my head round them. But this is precisely why you need to explore other programming languages: to see software development from a different perspective so you can then work in your usual development environment in a more imaginative way.