[Mono-dev] Mono Continuations and MicroThreads

[Tomi Valkeinen]

Hello,

This small project started when I stumbled upon a presentation 
(http://www.stackless.com/Members/rmtew/code/PyCon2006-StacklessEvePresentation.zip) 
about EVE online (http://www.eve-online.com/), and read about stackless 
python. I had known about stackless before that but I never really looked 
at what's it about. Well, it looked cool but I don't like python. So the 
next step was clear.

Attached is a small patch to mono runtime that implements continuations 
for amd64 and x86 linux, two C# files that implement basic 
MicroThread-stuff, and some C# test programs. You can also get a full 
package, including patched mono, mcs, stackless python at 
http://batmud.bat.org/~tomba/monoco-20060403-rel.tar.bz2 .

----

First a brief introduction to continuations (my continuations, I guess 
they can be implemented in slightly different ways):

A continuation is an object that can be used to store the current 
execution state and it can then be used to restore the stored state later. 
"Execution state" here means the stack, which includes call stack and 
local variables, and the processor's registers. When the stored state is 
restored the program execution looks like it jumps back to the position 
where the state was saved, with all the local variables restored. A short 
example:

static void Main()
{
     Continuation c = new Continuation();
     c.Mark();
     int foo = 123;
     int val = c.Store(0);
     Console.WriteLine("{0} {1}", val, foo);
     foo = 321;
     if (val < 5)
         c.Resume(val + 1);
}

prints:

0 123
1 123
2 123
3 123
4 123
5 123

You can ignore Mark() for now (it is used to mark the topmost frame to be 
stored). Store(x) stores the current state to the continuation, and 
returns the given integer x. Resume(y) restores the stored state, and 
returns the given integer y. Note that the integer y given to Resume is 
actually returned from the Store() method, because that's where we are 
after the state has been restored.

This was a short and confusing introduction, but you can find more 
information about continuations from the Net.

----

So continuations basically store a piece of stack to its own storage. This 
piece of stack includes the LMF structure saved by the managed-to-native 
wrapper, and that is used to restore the registers. After the stack and 
registers are restored, the instruction pointer is set to just after the 
call-instruction (in the wrapper) to the store function.

I used these continuations to implement (with C#) MicroThreads and a 
scheduler for the MicroThreads, and also semaphores, channels (as in 
stackless python), and a socket class. These can be found in the test 
directory, System.MicroThreads.*.cs files. They are rather quickly put 
together, so expect them to fail if you use them in a way I haven't used 
them. Especially the sockets are very hackish, I just wanted to see if the 
concept works. Also, MicroThreads are not thread-safe =).

MicroThreads look much like normal OS threads to the coder, but they are 
ran in the same OS thread and are scheduled 
non-preemptively/cooperatively, ie. the running thread has to yield 
willingly. MicroThreads should be lighter than OS threads, and in theory 
you could have lots of them (tens of thousands?) and still run fine. This 
would be great for many applications, particularly for multi-user 
environments/games which is what I'm interested in. I've also thought 
about leaving continuations out and implementing MicroThreads directly 
with native code. I guess this would make MicroThreads more optimal, but I 
haven't used much time to study this option yet.

Included are a couple of simple benchmark tests, written for both 
stackless and mono. The mono versions were slightly slower, but not much.

About the overall implementation: IT'S A HACK! =). It works, but I know 
many ways to break it. It lacks sanity checks. It probably misses a few 
arguments every now and then. It kinda ignores GC, which probably will 
also break it. The new GC will probably break it even more. I haven't even 
thought about CAS. Not forgetting the millions of things that I don't know 
about that will also break it. But still, the tests I've included work, 
and it's been great fun playing with them.

----

My first question to the list is: is anyone else interested in this, using 
continuations and/or developing them further? Shall I keep quiet from this 
on or do you want to hear more?

My second question is: how to make the native code better? I don't know 
much about Mono internals, this was my first mono runtime project so all 
feedback is appreciated. Also I'd very much like to hear if someone can 
point out why this way of implementing continuations to Monois 
fundamentally flawed. This requires reading the code, but if some of you 
Mono-gurus have the time and can educate me...

Well that's that. Feel free to ask anything that comes to your mind about 
this.

  Tomi
-------------- next part --------------
A non-text attachment was scrubbed...
Name: monoco-20060403-patch.tar.gz
Type: application/octet-stream
Size: 10538 bytes
Desc: 
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20060404/61bb4732/attachment.obj