My musings on .Net Technology

Trampoline and Reactive Extensions

with one comment


Try executing the below code snippet and soon it will throw a stackoverflow exception

  1. private void CallMe()
  2. {
  3.     Console.WriteLine(“Hello World”);
  4.     CallMe();
  5. }

The reason you get a stackoverflow exception is because CallMe function recursively calls itself, in other words callee’s stack is never re-claimed, rather it starts piling on top of the other (see stack unwinding); as soon as the stack runs out of space  it throws stack overflow exception.

To overcome this limitation we can instead use a technique called Trampoline (this is similar to C++’s Thunk).

Trampoline – With trampoline we convert recursion into continuation/iteration i.e. instead of jumping from one call to the other, return the handle to the next call (pointer to the next function) and let trampoline jump/continue the call for you. Once function call returns, the stack frame unwinds and no more stackoverflow issues.

The above example can be written in C# as

  1. private delegate RecursiveAction RecursiveAction();
  2.         private static void Main(string[] args)
  3.         {
  4.             RecursiveAction recursiveAction = null;
  5.             recursiveAction = () =>
  6.                                   {
  7.                                       Console.WriteLine(“Hello World”);
  8.                                       return recursiveAction;
  9.                                   };
  10.             for (;;)
  11.                 recursiveAction();
  12.         }

If you execute the above code you can see there is no recursion anymore


Another way or writing the same code using Func

  1. Func<RecursiveAction, Func<RecursiveAction>> actionRec = rec =>
  2.                                                                  {
  3.                                                                      Console.WriteLine(“Hello World”);
  4.                                                                      return () => rec;
  5.                                                                  };
  6.             RecursiveAction ar = null;
  7.             ar = () => ar;
  8.             for (; ; )
  9.                 ar = actionRec(ar)();

Reactive Extension also uses a similar technique to avoid stackoverflows (and other reasons such as to avoid race condition etc), the only variation of how it is implemented is that it uses a queue (analogous to dispatcher queue), the pointer to the next function call is placed in it’s queue and later when trampoline runs it dequeue the next function call and make it continuous call with some delay if required.

Scheduler using Trampoline

Class Trampoline Implementation (Reflector De-compiled)

Reactive Extension has two different types of schedulers that executes in the same context of the executing thread – namely Immediate and CurrentThread. MSDN defines it as

Immediate Scheduler - The Immediate scheduler starts the specified action immediately on the current thread.

CurrentThread Scheduler - The CurrentThread scheduler will schedule actions to be performed on the thread that makes the original call. The action is not executed immediately, but is placed in a queue and only executed after the current action is complete. – This queue is none other than the trampoline queue we talked about before.

Thus Immediate Scheduler is more like a blocking call which does not use Trampoline, and therefore never queues the successive call, rather it invokes the next call immediately.

Below RX call never returns as Return() uses immediate scheduler i.e. Repeat() calls OnNext, Take() takes the number 1 and calls OnNext to which Subscribe’s OnNext delegate writes it on console, Take() since it has taken one input, calls OnCompleted, again Subscribe’s OnCompleted delegate prints the literal “OnCompleted” on the console.

Code Snippet
  1. Observable.Return(1).Repeat().Take(1).Subscribe(Console.WriteLine, () => Console.WriteLine(“On Completed));

When Subscribe’s OnCompleted is called, it is called on AutoDetachObserver (this is basically a wrapper such that when OnCompleted is called, it also calls source observable’s IDisposable Dispose, and this goes on up the source chain i.e. you don’t need to dispose explicitly when observable completes, AutoDetachObserver does it for you). In our case when Take’s Dispose is called, it’s source i.e. Repeat’s IDisposable is null, this is because Repeat is repeating the number generation (Immediate Scheduler is executing OnNext, churning numbers repetitively) and has not yet returned the IDisposable from it’s subscription with Take.

With Current Thread Scheduler this is not a problem as OnNext deleegate is queued (and not executed immediately), thus allowing it to return IDisposable to Take which it can dispose OnCompletion.

Code Snippet
  1. Observable.Return(1, Scheduler.CurrentThread).Repeat().Take(1).Subscribe(Console.WriteLine, () => Console.WriteLine(“OnCompleted”));

Thus moral of the story is that you should be careful of what implicit scheduler is used – you can read the rules on MSDN

References:

http://bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx
http://social.msdn.microsoft.com/Forums/en-US/rx/thread/f9c1a7a6-d6a3-44fd-ba8c-e6845b1717b2

About these ads

Written by rohits79

August 15, 2011 at 1:40 am

Posted in .Net, Reactive Extension, Rx

One Response

Subscribe to comments with RSS.

  1. That, or your compiler just knows tail call optimization….

    nrolland

    December 27, 2012 at 4:43 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 268 other followers

%d bloggers like this: