segunda-feira, 19 de maio de 2008

Lightweight Fiber/Coroutines implementation on C#

I was recently experimenting with exploiting the C# 2.0 iterators to simulate continuations, as suggested in Wesner Moise's blog and came up with what seems to be a general and reasonable way to implement fibers in .NET.

To implement a logical execution thread we basically need a stack to keep track of "subroutines" and a "program counter" to keep track of the current execution point. Basically we take on the IEnumerator interface as the basic type for program counters.

Simulating an execution is simply a matter of stepping through the current IEnumerator routine. Every time this enumerator yields a subroutine, the current routine is pushed onto the stack and the "program counter" switches to the new routine. Every time a routine terminates, the stack is tested for parent routines by popping().

Here's the lightweight fiber implementation and a small sample of how to use it:
public class Fiber
{
private readonly Stack<IEnumerator> stackFrame =
new Stack<IEnumerator>();
private IEnumerator currentRoutine;

public Fiber(IEnumerator entryPoint)
{
this.currentRoutine = entryPoint;
}

public bool Step()
{
if (currentRoutine.MoveNext())
{
var subRoutine = currentRoutine.Current
as IEnumerator;
if (subRoutine != null)
{
stackFrame.Push(currentRoutine);
currentRoutine = subRoutine;
}
}
else if (stackFrame.Count > 0)
{
currentRoutine = stackFrame.Pop();
}
else
{
OnFiberTerminated(
new
FiberTerminatedEventArgs(
currentRoutine.Current
)
);
return false;
}

return true;
}

public event EventHandler<FiberTerminatedEventArgs>
FiberTerminated;


private void OnFiberTerminated(
FiberTerminatedEventArgs
e)
{
var handler = FiberTerminated;
if (handler != null)
{
handler(this, e);
}
}
}

public class FiberTerminatedEventArgs
: EventArgs
{
private readonly object result;

public FiberTerminatedEventArgs(object result)
{
this.result = result;
}

public object Result
{
get { return this.result; }
}
}
Now to implement a small recursive test program:
class FiberTest
{
private static IEnumerator Recurse(int n)
{
Console.WriteLine(n);
yield return n;
if (n > 0)
{
yield return Recurse(n - 1);
}
}

static void Main(string[] args)
{
var fiber = new Fiber(Recurse(5));
while (fiber.Step()) ;
}
}
This will print all the numbers from 5 to 0 by using fiber recursion. By yielding an IEnumerator, the fiber recursive function pushes the current fiber execution down to the recursive call. Test it yourself on the debugger and step through the execution to understand the basic mechanism.

With such a fiber/coroutine methodology its possible to define logical execution threads controlled by your application in which all involved iterator routines can be arbitrarily interrupted and resumed while preserving context.

Cool stuff once it clicks on you. Nice going for C# 2.0 iterators.

1 comentário:

Andrei disse...

With very moderate changes, Fiber can be made well-behaving client of foreach context, as below:
public class Fiber:System.Collections.IEnumerator
{
private readonly Stack<System.Collections.IEnumerator> stackFrame =
new Stack<System.Collections.IEnumerator>();
private System.Collections.IEnumerator currentRoutine;

public System.Collections.IEnumerator GetEnumerator()
{

return this;
}
public Fiber(System.Collections.IEnumerator entryPoint)
{
this.currentRoutine = entryPoint;
}
public void Reset() { } // not implemented
public bool MoveNext()
{
Again:
if (currentRoutine.MoveNext())
{
var subRoutine = currentRoutine.Current
as System.Collections.IEnumerator;
if (subRoutine != null)
{
stackFrame.Push(currentRoutine);
currentRoutine = subRoutine;
goto Again;
}
}
else if (stackFrame.Count > 0)
{
currentRoutine = stackFrame.Pop();
goto Again;
}
else
{
return false;
}

return true;
}
public object Current
{
get { return currentRoutine.Current ; }
}


}
Now, you can test it with the following coroutine:

public static System.Collections.IEnumerator TraverseNestedArrays(object x)
{
if (x is Array)
{
// traverse all elements (perhaps arrays themselves)
Array a = x as Array;
for (int i = 0; i < a.Length; i++)
{
yield return TraverseNestedArrays(a.GetValue(i));
}
}
else
{
// just expose element as Current
yield return x;
}
}

being invoked as below, it produces sum of all elements of all arrays, including nested ones:

object[] nestedArray = new object[] { 1, 2, new object[] { 3, 4, 5 }, 6, 7 };
int sum = 0;
foreach (object x in new Fiber(TraverseNestedArrays(nestedArray)))
{
sum = sum + (int) x;
}