Last night we did it again.
We went for this movie (50 First Dates) and came home feeling a little giddish. I was feeling a little giddish before the movie after nearly having my head ripped off sitting on a Torra Torra, in a fair in Bangalore.
So after the movie and the drive back home, what do we decide to do, like the nice normal people we are? We decide that we need to drink coffee at 12am and discuss programming. So we head off to Leela Palace where there is a late night Barista.
Something about the way coffee affects my head, when drunk late at night, especially after a movie needs some investigation. Sidharth was my comrade is arms, or rather comrade in coffee. So what do we do? we go there and sit down and drink coffee and I start off on SICP (Structure and Interpretation of Computer Programs) which I have been postponing for several years now.
I think part of why I was so adamant about starting out on SICP in the middle of the night is that I feel life (like usual) isn’t going anywhere. It turns out that a lot of smart people at various Universities decided that I was wasn’t smart enough to warrant a formal higher education in Computer Science and the place I want to be the most, doesn’t seem to want me around because of some technicality (for the fifth time). So since life wasn’t going anywhere, I figured I’d just have teach myself the things I want to know, my own way.
A little fast-forward in time and what finally ends up happening is that Sidharth and I end up talking about a certain MSDN article.
Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API
http://msdn.microsoft.com/msdnmag/issues/03/09/CoroutinesinNET/default.aspx
We ended up in a rather (heated) philosophic discussion about how iterators could be implemented, till 4am, which is what this blog entry is about.
If you have been reading about iterators in my previous blog entries
Iterators in Ruby (Part - 1)
Warming up to using Iterators (Part 2)
Then the idea is probably growing on you already. What Sidharth and I did is put in some thinking about how iterators could be implemented. This entry is going to break the logical flow of these two articles, but I am letting it be. I will probably have a part 3 post that will bridge the gap between Parts 1 and 2 and what I am going to say here about iterators.
Also, like a lot of things on this blog, I am not an authority on the subject so I am just guessing at how these things actually work.
Iterators
The thing about iterators is that there are two functions involved that have to maintain execution state at the same time. So example when a function calls another function, the caller is frozen and the callee executes – so the caller maintains execution state during the run time of the callee.
def callee
yield 1
yield 2
yield 3
end
def caller
callee { |n|
#parameter block to the iterator
puts n
}
end
When the callee is an iterator, the control actual leaves the callee and returns to the caller, when the execution is in the parameter block of the iterator. However we don’t see this sort of behavior in a normal C stack. Why? because when a function on the C stack returns to the caller, the function’s activation record on the stack is destroyed.
How do we do this?
The approach in the MSDN article uses an API called the fiber API.
Fiber Approach
The fibers can the thought of as threads that don’t have the scheduler attached to them. So unless a fiber is explicitly passed control it will not be executed, unlike a thread which is invoked by scheduler for a time slice.
What Ajai Shankar (the author of the MSDN article) does is use fibers to represent iterators. So in the above snippet, the function callee() would actually execute on a different fiber from caller. So when control needs to shift to the parameter block, which is to be executed in the caller() function, a fiber is a switch occurs.
When the parameter has finished execution a context switch occurs again.
What further happens is that the author has wrapped up all this dirty jumping around into a managed C++ class that invokes the OS api. He then goes onto write C# code (really!) that uses yield, almost the same way Ruby would use it.
(pasted)
class CorIter {
public void Next() {
object[] array = new object[] {1, 2, 3, 4};
for(int ndx = 0; true; ++ndx)
Yield(arr[ndx]);
}
}
If you get the general idea, then lets move on.
The problems with using the fiber API, among other problems, are
· Every fiber is like a thread, which means that the more the iterators the more the number of fiber specific stack frames and such that get created – which means more the code bloat for code like this.
· Using the fiber api actually makes this a very OS specific solution – other OSes that the CLR may wish to target may not have provisions for building up such an API.
· Exceptions: exceptions in the windows world are strung to the TLS (Thread Local Storage) of the thread of execution – this may behave rather odd when fibers are mixed into the picture.
Let ignore everything and just examine the first problem, the issue of creating separate stack frames per fiber and thus bloating the system – if we could solve this one, then I think (and I might be wrong), would bring more credit to this approach.
Wrapping State in a Caller Object
One other approach to supporting iterators is to ensure that one of the two functions (the caller or the callee) maintain state using some mechanism other than the C stack.
Lets take a look at the caller:
def caller
callee { |n|
puts n
}
end
or maybe a C# equivalent.
void caller()
{
foreach(int n in callee())
{
Console.WriteLine(n);
}
}
This method can actually be though off as consisting of three parts
void caller()
{
foreach(int n in callee())
{
Console.WriteLine(n);
}
}
We could create an object to hold the state of the function that would hold these three parts. Something like this:
class caller_object
{
//declare all local variable so the class as member variables here
void do_part1()
{
}
void do_codeblock() //part 2
{
}
void do_part3()
{
}
}
The idea is that we create an object that has member variables that represent the local variable of the caller. So we execute the caller as three parts
void caller()
{
caller_object co = new caller_object()
co.do_part1();
callee(co);
co.do_part3();
}
The caller method now is simply a wrapper around the class that represents the caller function as an object. When the method do_part1() is called on the class, the object will have the same state as the original caller() function when it has just run till the point where the iterator is invoked.
Then the callee() is invoked and the object that represents the caller’s state is passed to the callee. The callee then goes on to invoke the object’s do_codeblock() every time a yield is required.
Since the callee never returns till it has completed execution it maintains state on the runtime stack, like a normal function. The do_codeblock() has the same code that the code block of the for each loop had and it can also maintain any state changes into the object. Finally when the callee() exits the object’s do_part3() is invoked.
This is similar to what the iterators accomplish. Here the state is stored in an object and not on the stack. However, here a full managed type that represents that caller has to be created. I didn’t like that too much.
Wrapping State in a Callee Object
This is similar to the above approach, except that roles are reversed. We create an object that can represent the callee. The callee then returns to the caller at every yield statement.
The callee state is maintained in the object representing it. There is an excellent write up you can read about a similar approach here:
Coroutines in C
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
The idea there is that the state of the function is retained in a state variable. The state variable is used to jump back to the point where the function had previously yielded from. Code would look a little like this:
(pasted)
int function(void) {
static int i, state = 0;
switch (state) {
case 0: /* start of function */
for (i = 0; i < 10; i++) {
state = 1; /* so we will come back to "case 1" */
return i;
case 1: /* resume control straight after the return */
}
}
}
Now this example uses static variables but it is easy to imagine this being extended such that each variable is the member of some object.
(pasted)
It's a little bit ugly, because suddenly you have to use ctx->i as a loop counter where you would previously just have used i; virtually all your serious variables become elements of the coroutine context structure. But it removes the problems with re-entrancy, and still hasn't impacted the structure of the routine.
(Kudos to Pooja, for coming up with this idea at one sitting).
When C# announced the coming of iterators in the language and a new yield keyword, I was excited. In the mood of the MSN co-routines article, I had expected a CLR level support for iterators.
It turns out that the C# teams approach is similar to that of the saving the callee state in an object. (I am not very sure about whether its the caller or the callee, in case I am wrong in assuming that it’s the callee, which seems to be the more logical choice, I will blog about it).
In the Co-routines in C article, the author talks of writing macros that wraps up the behavior. Since the compiler does the temporary object creation and hides all the mess from you, in the case of C#, it seems like a reasonable alternative.
A modified form of the Fiber API idea
The reason I don’t really like the way C# does iterators right now is because it is a hack. They did not want to change the CLR for a feature that may not catch on. So I guess, they used a less expensive approach. If I am wrong, I would like to be corrected. I would expect that more serious CLR level support will come up for iterators if the idea’s introduced in Whidbey C# become popular.
The other reason I don’t really like the approach, the real reason, is that the .Net type system is a fairly comprehensive type system designed to propagate an idea of types as a level playing field for language agnostic components to interact. Introducing a type into the system just to retain a function’s state does not seem consistent with this philosophy.
Fiber API on the other hand more naturally lend themselves to the way I would choose to think of iterators – as functions that can be frozen during execution and be continued.
Now this might seem like a weak argument, but it seems to better to use the processors abilities to do a context switch to actually freeze execution of a block of code, that write the code as code that manages members of an object (only for the purpose that the object can be used to retain the state of the code).
The Fiber API like approach seemed to do this more naturally. I would expect that the CLR in future would internally provide some API similar to that of the OS provided fibers so that it can do iterators and closures and probably even continuations.
Some basic requirements would be that implementing such features don’t slow down execution of code that don’t require any of these features. Such features should be reasonably efficient with respect time as well as space.
Let me try and discuss the space issues here. In fiber API there would be need for creating totally new independent stack frames for each fiber. This is wasteful.
Would it be possible so that we have a modified API, which will behave like fibers, share stack space with the common C stack and can use the processor context switching abilities to freeze function execution, rather than save state as a managed object.
A little bit of brainstorming last night and we had this:
In the .Net world, we have the luxury of being able to predict the stack usage of a function under execution with IL directives like “.maxstack”. Which is to say - we know how much space the function will use on the managed stack.
The stack frame for regular method calls would look like this:
This is obvious for anyone who understands how methods are laid out on the stack. The only advantage that we have here is that in the .Net world. We know exactly how much stack space a given method will use.
Now if the method calls an iterators that has a yield, we create a Fiber, but a special sort that would use the main stack itself as its stack frame. So the newly created method instance (the iterator itself) will reside on the call stack, above the caller.
Now the usual semantics of stack usage are allowed on this fiber. The fiber behaves like any other thread would behave, owning the stack. To allow methods to keep track of their callee’s we add a reference to the activation record of the callee.
The interesting part, when the iterator needs to yield a value. When it does control is switched back to the original fiber. The activation record of the iterator is still maintained on the stack. Further method calls would however place their activation records above the iterator’s activation and behave as though it was normal C stack.
Thus I think it is possible to have fiber API like constructs to implement iterators, share stack space have reasonably efficient implementations too. The only real over head introduced here is a level of indirection when activation records are torn down from the stack frame.
I feel that this is a more co-routine like approach that the one that involves creating hidden managed objects.
I would like to wish that this idea can be extended to implement proper continuations also, that is not very easy. Here the stack management is very easy because as any point a sleeping fiber will contain only one activation record on the stack. A continuation will require that activation objects live and die on the manage stack as though they were proper objects and some sort of garbage collection routine will be required on the stack.
I am extremely open to opinions about this entry, because I am treading on many areas that I am not very well versed with. I am hoping that the idea of freezing execution state via fiber like constructs is more efficient that the approach that involves creating full managed objects.