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.
Over the weekend a couple of interesting post were made:
Last year we did some work in Mono together with
Luis Ortiz to support 64-bit arrays in the VM.
This means that you can continue to use your existing tools
to build applications, but when running under Mono you will
get to use those arrays without that pesky 2,147,483,648 upper
boundary.
