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 (http://www.stackless.com/). 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: implement continuations and microthreads to Mono!
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.Restore(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. Restore(y) restores the stored state, and returns the given integer y. Note that the integer y given to Restore is actually returned from the Store() method, because that's where we are after the state has been restored.
Continuations can be used to implements microthreads. Microthreads are in many ways similar to conventional OS threads, except that microthreads actually run inside one OS thread and only willingly let other threads so their work. This allows us to forget the concurrency problems that one has to be carefull about with OS threads. A short example:
static void Main()
{
MicroThread t1 = new MicroThread(Run1);
MicroThread t2 = new MicroThread(Run2);
t1.Start();
t2.Start();
Scheduler.Run();
}
static void Run1()
{
for(int y = 0; y < 4; y++)
{
Console.WriteLine("y = {0}", y);
MicroThread.CurrentThread.Yield();
}
}
static void Run2()
{
for(int x = 0; x < 6; x++)
{
Console.WriteLine("x = {0}", x);
if(x % 2 == 0)
MicroThread.CurrentThread.Yield();
}
}
prints:
y = 0
x = 0
y = 1
x = 1
x = 2
y = 2
x = 3
x = 4
y = 3
x = 5
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 (inside the wrapper function) 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 Mono.MicroThreads/*.cs files.
Microthreads look much like normal OS threads to the coder, but they all run in the same OS thread and are scheduled non-preemptively/cooperatively, ie. the running thread has to yield willingly. Microthreads should (or should they? =) 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. Note that currently microthreads are not thread-safe.
Continuations can easily be used in a wrong way, leading to stack corruption, so they are unsafe. Microthreads use the continuations in the right way, and there should not be an easy way to corrupt the runtime by using them. However, there are cases that the current implementation does not handle, for example a managed-native-managed transition in the call chain. I haven't tried to fix these as they are quite rare.
Classes currently implemented:
Here are some little, not so precise, benchmarks I've made. The machine is a dual opteron 2.4GHz, in 64-bit mode. Mem is a rough estimation from "ps -o size="
Yieldtest makes n threads that do m loops, yielding in each loop. Ran with default optimizations.
100 threads * 1000000 loops = 100000000 yields in 23.67s, 4224336 yields/s (Mem 5M) 1000 threads * 100000 loops = 100000000 yields in 28.66s, 3489732 yields/s (Mem 6M) 10000 threads * 10000 loops = 100000000 yields in 64.72s, 1545102 yields/s (Mem 15M) 100000 threads * 1000 loops = 100000000 yields in 56.74s, 1762304 yields/s (Mem 95M) 500000 threads * 100 loops = 50000000 yields in 30.27s, 1652018 yields/s (Mem 448M)
100 threads * 1000000 loops = 100000000 yields in 0:00:51.984451 (Mem 2M) 1000 threads * 100000 loops = 100000000 yields in 0:00:54.499802 (Mem 2.5M) 10000 threads * 10000 loops = 100000000 yields in 0:01:23.937899 (Mem 9M) 100000 threads * 1000 loops = 100000000 yields in 0:01:30.003930 (Mem 72M) 500000 threads * 100 loops = 50000000 yields in 0:00:47.153561 (Mem 352M)
You need to get Mono from the subversion repository (http://www.mono-project.com/AnonSVN) to be able to compile continuations, because of the new files that require you to run autogen.sh. The sources are divided to two parts: the native code inside Mono runtime and the managed code. Native part is not very big and implements only the few functions needed to implement continuations. The managed code implements microthreads, scheduler and support classes like sockets, semaphores, critical sections etc.
To patch and compile mono:
svn co svn://svn.myrealbox.com/source/trunk/mcs svn co svn://svn.myrealbox.com/source/trunk/mono cd mono patch -p1 < /path/to/monoco-yyyymmdd.patch ./autogen.sh --prefix=/mono/install/path make make install
To compile tests:
export PATH=/mono/install/path:$PATH cd test make
Most recent
http://www.bat.org/~tomba/monoco-20090429.tar.gz
Older versions
http://www.bat.org/~tomba/monoco-20081122.tar.gz
http://www.bat.org/~tomba/monoco-20070502.tar.gz http://www.bat.org/~tomba/monoco-20060420.tar.gz http://www.bat.org/~tomba/monoco-20060419.tar.gzI'm very interested to hear feedback about Mono continuations. My email address is below.