Continuations in Mono: Embrace and Extending.NET, Part 3

Update: I accidentally published an incomplete version of this blog entry the other day before the actual content and samples were ready.

As part of our ongoing Embrace and Extend.NET series (SIMD, supercomputing), today I wanted to talk about the Mono.Tasklets library that has just landed on Mono's repository.

This library will become part of the Mono 2.6 release.

Mono.Tasklets is the Mono-team supported mechanism for doing continuations, microthreading and coroutines in the ISO CLI. It is based on Tomi Valkeinen's excellent work on co-routines for Mono.

Unlike the work that we typically do in Mono which is pure C# and will work out of the box in .NET (even our Mono.SIMD code will work on .NET, it will just run a lot slower) Mono.Tasklets requires changes to the VM that are not portable to other ISO CLI implementations.

History

Unity Early Experiments

Back in 2004 when Unity first started to explore Mono, Joachim Ante brought up the topic of coroutines in Mono. On an email posted to the mono-devel-list he stated:

I want to be able to write scripts like this:

	void Update ()
	{
	    Console.WriteLine ("Starting up");
	    //Yields for 20 seconds, then continues
	    WaitFor (20.F);
	    Console.WriteLine ("20 seconds later");
	}
	

The WaitFor function would yield back to unmanaged code. The unmanaged code would then simply go on, possibly calling other C# methods in the same class/instance. After 20 seconds, the engine would resume the Update method.

The idea here is to have multiple execution paths running on a single thread using a sort of cooperative multitasking. GUI programmers are already used to this sort of work by using callbacks: event callbacks, timer callbacks and idle callbacks. In Gnome using C or C# 1.0 you use something like:

	void do_work ()
	{
		printf ("Starting up\n");
		g_timeout_add (20 * msec, do_work_2, NULL);
	}

	void do_work_2 ()
	{
		printf ("20 seconds later\n");
	}
	

Although lambdas help a little bit in C# 2.0 if the core of your application needs to chain many of these operations the style becomes annoying:

	DoWork ()
	{
		Console.WriteLine ("starting up");
		Timeout.Add (20 * msesc, delegate {
			Console.WriteLine ("20 seconds later");
		});
	}
	

In event-based programming everything becomes a callback that is invoked by the main loop. The developer registers functions to be called back later in response to a timeout or an event.

Another alternative is to build a state machine into the callbacks to put all of the code in a single method. The resulting code looks like this:

	void do_work (void *state)
	{
		MyState *ms = (MyState *) state;
	
		switch (ms->state){
		case 0:
			printf ("starting up\n");
			ms->state = 1;
			g_timeout_add (20 * msec, do_work, state);
			break;
		case 1:
			printf ("20 seconds later");
		}
	}
	

It is worth pointing out that Joachim and in general the gaming world were ahead of our time when they requested these features. This style of threading is commonly referred as microthreading or coroutines.

At the time, without runtime support, Rodrigo suggested that a framework based on a compiler-supported generator-based system using the yield instruction would satisfy Joe's needs for coroutines in the gaming space.

This is what Unity uses to this day.

C# Yield Statement in Mono

The yield statement in C# works by building a state machine into your method. When you write code like this:

	IEnumerable DoWork ()
	{
		Console.WriteLine ("Starting up");
		yield return new WaitFor (20 * msec);
		Console.WriteLine ("After resuming execution");
	}
	

The compiler generates a state machine for you. In the above example there are two states: the initial state that starts execution at the beginning of the function and the second state that resumes execution after the yield statement.

A year later we used a variation of the above by employing nested yield statements in C# to implement Mono's HttpRuntime pipeline stack.

Cute screenshot from my blog at the time:

Yield statements can be used to solve this class of problems, but they become annoying to use when every method participating in suspending execution needs to become an iterator. If any part of the pipeline is not built with explicit support for yield, the system stops working. Consider this:

void Attack()
{
	 DoTenThings ();
}

void DoTenThings()
{
	  for (int i=0; i < 10; i++){
	      C();
	  }
}

IEnumerable C()
{
	   yield WaitForIncomingMessageFromNetwork();
}
	

Here, even if the WaitForIncomingMessageFromNetwork uses yield the callers (DoTenThings and Attack) are not participating, they merely discard the return from yield, so the execution does not return to the main loop.

Using a yield-based framework is not much of a problem if you only need to use this every once in a while. For example we use this in our ASP.NET engine but it is only used in a handful of places.

Unity used an approach built on top of the yield framework to suspend and resume execution. For example this is invoked by the Update() function on an enemy script:

function Patrol() {
	while(true) {
		if (LowHealth ())
			RunAway();
		else if (EnemyNear ())
			Attack();
		else
			MoveSomewhere();
		yield; // done for this update loop!
	}
}

function Attack () {
	while (!LowHealth () && EnemyNear ()) {
		DoTheAttack ();
		// done with this update, and wait a bit
		yield WaitForSeconds (attackRate);
	}
	// return to whatever invoked us
}
	

The same can be done in Unity with C#, but your functions should be declared as returning an IEnumerable.

Microthreading in SecondLife

In 2006, Jim from LindenLabs introduced the work that they had done in SecondLife to support microthreading.

Jim's work was a lot more ambitious than what both Joe had requested. SecondLife required that code be suspended at any point in time and that its entire state be serializable into a format suitable for storage into a database. Serialized state could then be restored at a different point in time or on a different computer (for example while moving from node to node).

For this to work, they needed a system that would track precisely the entire call stack chain, local variables and parameters as well as being able to suspend the code at any point.

Jim did this by using a CIL rewriting engine that injected the state serialization and reincarnation into an existing CIL instructions stream. He covered the technology in detail in his Lang.NET talk in 2006.

The technology went in production in 2008 and today this continuation framework powers 10 million Mono scripts on SecondLife.

Tomi's Microthreading Library

That same year Tomi posted a prototype of coroutines for Mono called MonoCo, inspired by the use of Stackless Python for EVE Online.

The Stackless Python on EVE presentation goes through the concepts that Tomi adopted for his Mono.Microthread library.

Tomi's approach was to modify the Mono runtime to support a basic construct called a Continuation. The continuation is able to capture the current stack contents (call stack, local variables and paramters) and later restore this state.

This extension to the runtime allowed athe entire range of operations described in the Stackless Python on Eve presentation to be implemented. It also addresses the needs of developers like Joachim, but is not able to support the SecondLife scenarios.

Mono.Tasklet.Continuation

The Mono.Tasklet.Continuation is based on Tomi's Microthreading library, but it only provides the core primitive: the continuation. None of the high-level features from Tomi's library are included.

This is the API:

	public class Continuation {
		public Continuation ();
		public void Mark ();
		public int Store (int state);
		public void Restore (int state);
	}
	

When you call Store the current state of execution is recorded and it is possible to go back to this state by invoking Restore. The caller to Store tells whether it is the initial store or a restore point based on the result from Store:

	var c = new Continuation ();
	...

	switch (c.Store (0)){
	case 0:
		// First invocation
	case 1:
		// Restored from the point ahead.
	}
	...
	// Jump back to the switch statement.
	c.Restore (1); 
	

Tomi implemented a Microthreading library on top of this abstraction. I ported Tomi's Microthreading library to Mono.Tasklet framework to test things out and I am happy to report that it works very nicely.

Tomi's patch and library were adopted by various people, in particular in the gaming space and we have heard from many people that they were happy with it. Not only they were happy with it but also Paolo, Mono's VM curator, liked the approach.

Frameworks

Speaking with Lucas, one of the advocates of Tomi's VM extensions, at the Unite conference it became clear that although the Mono.Microthreads work from Tomi was very useful, it was designed with the EVE scenario in mind.

Lucas was actually not using Mono.Tasklets on the client code but on the server side. And when used in his game the Stackless-like primitives were getting on his way. So he used the basic Continuation framework to create a model that suited his game. He uses this on his server-side software to have his server micro-threads wait for network events from multiple players. The Tomi framework was getting in Lucas' way so he created a framework on top of the Continuations framework that suited his needs. He says:

I found however, that what system you build on top of the core continuations tech, really depends on what kind of application you're building. For instance, I have a system where I send serialized "class ProtocolMessage" 's over the network. they have a questionID and an answerID, which are guids.

in my code I can say:

	// automatically gets questionID guid set.
	var msg = new RequestLevelDescriptionMessage();         
	someConnection.SendMessageAndWaitForAnswer (msg);
	

the last call will block, and return once a message with the expected type, and matching answerID has been received. This is made to work because the SendMessageAndWaitForAnswer<T>() call adds itself to a dictionary<GUID,MicroThread> that keeps track of what microthreads are waiting for which answer. A separate microthread reads messages of the socket, and reads their answerID. it then looks to see if we have any "microthreads in the fridge" that are waiting for this message, by comparing the guid of the message, to the guid that the microthread said it was waiting for. If this is it, it reschedules the microthreads, and provides the message as the return type for when the microthread wakes up.

This is very specific to my use case, others will have things specific to their use cases.

Going back to the Joachim sample from 2004, using Tomi's code ported to Mono.Tasklets, the code then becomes:

	void Update ()
	{
	    Console.WriteLine ("Starting up");
	    //Yields for 20 seconds, then continues
	    Microthread.WaitFor (20.F);
	    Console.WriteLine ("20 seconds later");
	}
	

The MicroThread.WaitFor will suspend execution, save the current stack state --which could be arbitrarily nested-- and transfer control to the scheduler which will pick something else to do, run some other routine or sleep until some event happens. Then, when the scheduler is ready to restart this routine, it will restore the execution just after the WaitFor call.

A sample from the game world could go like this:

	prince.WaitForObjectVisible (princess);
	prince.WalkTo (princess);
	prince.Kiss (princess);
	

The code is written in a linear style, not in a callback or state machine style. Each one of those methods WaitForObjectVisible, WalkTo and Kiss might take an arbitrary amount of time to execute. For example the prince character might not kick into gear until the princess is visible and that can take forever. In the meantime, other parts of the game will continue execution on the same thread.

The Continuation framework will allow folks to try out different models. From the Microthread/coroutine approach from Tomi, to Lucas' setup to other systems that we have not envisioned.

Hopefully we will see different scheduling systems for different workloads and we will see libraries that work well with this style of programming, from socket libraries to web libraries to file IO libraries. This is one of the features that Lucas would like to see: Networking, File and other IO classes that take advantage of a Microthreading platform in Mono.