Jul 11 2011

Being recursive

When authoring recursive routines there are special memory and performance considerations to be made. Firstly, authors must consider the overall size the call Stack could reach given the point in the Stack where the call starts and the number of Stack Frames that could be added as a result of the recursion. In doing so, you can estimate some key factors.

  1. What is the likelihood of a StackOverflowException?
  2. How much memory will be required to support all the Stack Frames added by the recursive call?

With just these two elements, we can assert a couple performance implications:

  • If your recursion is expected to create a large number of Stack Frames, then your product may suffer from the direct impact of managing a large chunk of memory for the Stack and the indirect expense of collapsing the recursion results when the recursion is completed. In this case, optimizations may be valuable and will very likely result in an easily measureable performance advantage
  • In cases, where you’re creating very shallow recursions (e.g. few Stack Frames) this is rarely a concern unless the state on the stack is very large

Assuming you need to optimize, you can try and achieve a Tail call (a.k.a. tail-recursive call). Before we go on, let’s define more precisely what a Tail Call is.

In computer science, a tail call is a subroutine call that happens inside another procedure and that produces a return value, which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If a subroutine performs a tail call to itself, it is called tail-recursive. This is a special case of recursion.

Tail calls are significant because they can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination, or tail call optimization.” --- Wikipedia

As explained in the definition, tail calls will prevent your recursion from producing any more than two Stack Frames. This is because the second Frame will continually be reused for each point of recursion.

Unfortunately, achieving tail calls in .NET is somewhat difficult. There are two commonly used patterns for trying to achieve this:

  1. Modify your method structure to make it eligible for tail-elimination optimizations by the C# compiler. To determine if this has already happened for your method you simply need to review the IL and see if the following IL is present near the end of your method
       
    IL_001a: tail

    If the tail IL is already present, then you’re all done… well done! If not, then making your method eligible simply involves modifying the method so that the recursive call is the last statement in the method
      
    private int ARecursiveMethod(int arg)
    {
        //TODO: Do work
        return ARecursiveMethod(arg);
    }
  2. Force a tail call. Unfortunately, the compiler’s exception list for automatically applying this optimization is very long. Consequently there are a number of reason’s this will not occur automatically. As it turns out, the list of reasons is largely a result of just-in-case scenarios where they want to avoid breaking your method. Although a more advanced set of steps is required, you can force tail calls to occur if your process requires it. Here is what you need to do:
  • Compile the parent assembly as normal
  • Extract the IL with ILDASM
  • Modify the IL to insert the tail instruction
  • Reassemble the assembly with ILASM
  • Test, test, test…

Note: This can all be automated but obviously carries some risk. In my experience, this should occur in CI between build time and Unit Test runs

Have Fun!

Tags: ,

Comments

1.
trackback DotNetKicks.com says:

Being recursive

You've been kicked (a good thing) - Trackback from DotNetKicks.com

Comments are closed