通过

Tail calling in .NET

  • 项目

Thought I would give a little details on one type of optimization that it is possible to see and explain what it is and how it affects things so that if you come across it, you will understand what is happening.

So there is this concept of tail calling which is where the compiler will optimize code to save execution of instructions as well as saving some reads and writes of stack memory.  This happens under certain circumstances when a function ends by calling another function (hence tail calling).  For example, if we have the following:

 static public void Main()

 {

     Test();

 }

  

 static public void Test()

 {

     First();

     Second();

     Third();

 }

  

 static public void Third()

 {

 }

In this sample, it is possible for the compiler to make the call to Third() a tail call.  So to better explain this, under normal situations we would see something like this on a callstack while we are executing in the function Second():

 Second()
Test()
Main()

When Third() runs, it is possible for it to be a little different.  Instead of creating a new allocation on the stack for Third, it can replace Test() with Third().  So then we would see:

 Third()
Main()

When Third() returns, it will return directly to Main() and not have to go through Test() at all.  This saves time and memory for the application overall.

To tail or not to tail

So how does the compiler decide if it should use this optimization?  Well, first there is the discussion of which compiler we are referring to.  There are two compilers at play with .NET.  The first takes the source code and compiles it into IL.  Then the JIT compiler will take the IL and create native code.  The creation of IL can set up hints to try to help with the creation of tail calls, but it is ultimately the JIT compilers job to create them.  There are a lot of rules that determine if it can do this but a quick summary of the rules that will make us NOT use this option are:

Note: This is subject to change and you shouldn’t base anything on this behavior.  This is just for general knowledge.

  • Caller doesn’t return immediately after the call
  • Stack arguments between caller and callee are incompatible in a way that would require shifting things around in the caller’s frame before the callee could execute
  • Caller and callee return different types
  • We inline the call instead (inlining is way better than tail calling, and opens the door to many more optimizations)
  • Security gets in the way
  • The debugger/profiler/config turned off JIT optimizations

If you really want to see the full list, check this this post.

Who cares about tail calls, sounds like a trip to the zoo

Normally this kind of thing won’t matter to you unless you are trying to write a profiler, but there are times that you may see a callstack that doesn’t make any sense because one of the functions is missing.  As someone that has done a lot of debugging, I have come across this from time to time and thought others may find it useful to know about.

Comments

  • Anonymous
    October 01, 2008
    PingBack from http://www.easycoded.com/tail-calling-in-net/

  • Anonymous
    October 23, 2008
    Tom I noticed that the First() method is missing from both callstack examples. Is there some particular reason why?

  • Anonymous
    October 26, 2008
    When we are in the Second method, First will have already executed and been removed from the stack.  The same holds true for when Third is executing.