Duff's Device, Coroutines and Continuations

I've been doing a lot of programming recently after a bit of a hiatus. It's not that I haven't been programming, it's more the type. Instead of writing deep-down, think about it for 10 minutes and then press a key, kind of software I'm writing more bread and butter code.

The change in style has made me aware of several frustrations. When writing bread and butter code, I find that a vast majority of it is boilerplate. It doesn't change from class to class, and I even find myself performing cut-and-paste programming. I'm finding this frustrating because I feel that my productivity has dropped. I find that I have a certain number of lines of bug-free code per day in me. If I can do more by writing fewer lines, then I'm more productive. Having to write boilerplate saps my precious daily lines of code!

So, I'm on the lookout for new ideas to help me write more code faster. I look for ways to architect the code to avoid having to actually write code. This is the other side of Paul Graham's "Good Hackers Don't Use Java" argument. While I have to use C++, I'm looking for line saving ideas from other programming languages.

One of the more code sucking types of code is the state machine. State machines are everywhere. They are frequently implemented as tables of functions, with each state having a lot of boilerplate at the start and the end.

My explorations for a better state machine implementation have taken me to Duff's Device, Coroutines and Continuations. When I started, I knew what Duff's Device and Coroutines were, but I only had a vague concept (and an incorrect one at that) of what a Continuation was.

First, an introduction

Everyone out there has probably heard of loop unrolling. This is when you take a long running loop in your program and attempt to perform more transactions per iteration. The starting point looks something like this:

int j=100;
for (int i=0;i<j;i++) {
    printf("%d\n", i);
}

To speed up this type of loop, you attempt to perform more printf's per iteration. Simplistically, you will try something like this:

for (int i=0;i<j/5;i+=5) {
    printf("%d\n", i);
    printf("%d\n", i+1);
    printf("%d\n", i+2);
    printf("%d\n", i+3);
    printf("%d\n", i+4);
}

However, what happens if j = 3? The code will (now incorrectly) still output 0-4. There is a way to fix it...

Enter Duff's Device.

Essentially, Duff's Device makes use of some interesting behaviour of switch and case statements. The switch/case statements act like named goto's instead of if statements. This gives them the ability to jump into scopes!

So, let's change the code to use Duff's Device:

int i=0;
int j=3;

switch (j%5) {
case 0:
for (;i<j;i+=5) {
    printf("%d\n", i);
case 4:
    printf("%d\n", i+1);
case 3:
    printf("%d\n", i+2);
case 2:
    printf("%d\n", i+3);
case 1:
    printf("%d\n", i+4);
}

This is how loops are unrolled. In this way, we get many more operations for each iteration through the loop.

At this point, the audience yells out "But this doesn't save me any lines of code!", and they would be correct. It's Duff's Device with the next concept that can save us code. Enter Coroutines.

Coroutines

Coroutines are co-operative multitasking. At some point the task will indicate that it yields the processor, allowing another thread of control to be executed. If the task doesn't give up control, it is never interrupted. Most systems have moved on to using full blown independent threads, but there are still some classes of systems where threads aren't appropriate. Good examples are systems with several hundred thousand independent operations active at any time. It isn't possible to have a real thread for each operation, and managing a thread pool is just as hard as managing coroutines. Add to that the benefits of avoiding locking and resource sharing issues and the argument for coroutines becomes pretty compelling. On those systems, code can still be simpflified by using coroutines. State machine code can be dramatically simplified, turning it into a linear top to bottom function rather than a set of states managed by an array or switch.

For example, consider the following (note, the code only works with GCC):

class coroutine {
   public:
   coroutine() : state(0) {}
   virtual void run();
   private:
   int state;
}

#define coBEGIN() switch (state) {case 0:
#define coRETURN() state = __LINE__;return;case __LINE__:
#define coEND()   }

class coBasic : public coroutine {
    public:
    virtual void run();
}

void coBasic::run() {
    coBEGIN();

    fprintf(stderr, "Here we are in state 1\n");
    coRETURN();

    fprintf(stderr, "Here we are in state 2\n");
    coRETURN();

    fprintf(stderr, "Here we are in state 3\n");

    coEND();
}

int main(void) {
   coBasic co;

   co.run();
   co.run();
   co.run();
}

Where does this save us code? We save code in several locations. First, we don't have to write a function header for each state. Code will flow from one state to the next. Next up, we avoid all of the setup code. Frequently code will have to do at least a little bit of marshalling as it prepares to run. Using this, that code is shared among all of the states, instead of being copied, or shared as a separate function.

There are some limitations to this implementation. First, it is very difficult to specify the next state to invoke, linear is the name of the game. It is possible to change the macros to use specific state names instead of a simple return, which would allow more complex state machines to be created. If we restrict ourselves to GCC, whose preprocessor allows macro overloading, we can even combine the two with both named and unnamed states.

Also, there are some limitations imposed by the use of Duff's Device. C++ does not allow code to jump over constructors, so code like the following will resultin a compilation error:

void coBasic::run() {
    coBEGIN();

    fprintf(stderr, "Here we are in state 1\n");
    std::map<int, int> foobar; // <-- ERROR
    coRETURN();

    fprintf(stderr, "Here we are in state 2\n");

    coEND();
}

To get around this, we can do two things. We can either move to C-style declarations and do all of our declarations at the start of the function, or we can modify the macros slightly. The modified macros would look like this:

#define coBEGIN() switch (state) {case 0:{
#define coRETURN() state = __LINE__;return;}case __LINE__:{
#define coEND()   }}

As you can see, we're adding an additional scope around each state. In that way, we avoid jumping over a constructor for an object we could conceivably use, but we do end up having some strange compiler problems. Consider the following code:

void coBasic::run() {
    coBEGIN();

    fprintf(stderr, "Here we are in state 1\n");
    std::map<int, int> foobar;
    coRETURN();

    fprintf(stderr, "Here we are in state 2 map size = %d\n",
            foobar.size()); // <-- ERROR

    coEND();
}

This will generate an undefined variable error for foobar, because foobar is only defined in the previous state. So, we get slightly more confusing code because scopes aren't necessarily clearly defined. However, this does allow state-local variables to be declared and used.

Continuations

When I originally started to write this article, I misunderstood what a continuation was. I thought it was simply a coroutine by another name. I was wrong. Continuations are about continuing execution at stored location in the procedure, but they add a new wrinkle. Where the coroutine above returns, a continuation passes the execution location down the stack. Perhaps a picture will help:

Coroutine:

 A -> B (no state)
   <- B (point 1)
 A -> B (starts at point 1)
   <- B returns
...

Continuation
 A -> B (no state)
        -> C (B at point 1)
             -> D (B still at point 1)
                 -> B (starts at point 1)
   <--------------- B returns all the way back to A
A

It seems that continuations are a relatively new programming style, with few people understanding their benefits, or even being able to explain how they work. The easiest explanation I found was on c2.com (http://c2.com/cgi/wiki?ContinuationExplanation), especially the C code version (http://c2.com/cgi/wiki?ContinuationsInCee). The form of continuation presented in that code is called a "Single Use Continuation", meaning it can only be executed if it is still on the stack, and that it can only be invoked once. Some languages (Lisp/Scheme/Dylan?) fully support continuations allowing them to be executed multiple times at any point.

There is one more thing about continuations. They save the state of the stack at the point the continuation is created, allowing code to return to that location using the existing local variables. This is very useful for unraveling network and user interaction code. For this we really need a language that supports continuations, such as Scheme, Lisp and Dylan. In C/C++, we can mostly fake it with some limitations.

We can fake them using various methods. In C, we can use setjmp/longjmp or on x86, modify the stack base pointer as in the C2 example. In C++, we can do much of the same using exceptions. The use of exceptions allows us to properly clean up the parent stack frames, while returning to the previous stack frame. In C, we can use the speedier code and simply "Go There".

Using the previous example, the C/C++ continuations I'm presenting here would also invalidate any continuations in stack frames C or D when B is executed the second time.

For a basic implementation, consider the following:

class continuation<class X> {
   public:
   typedef X myContinueSignal;
   continuation() : state(0) {}
   virtual void run();
   void continue();
   private:
   int state;
}

void continuation::continue() {
    throw X();
}

struct myContinuationContinueSignal {}

class myContinuation: public continuation<class myContinuationContinueSignal> {
    public:
    void run();
}

#define coBEGIN() switch (state) {case 0:{
#define coRETURN() state = __LINE__;return;}case __LINE__:{
#define coCALL(x)  state = __LINE__;try {x;}catch (myContinuation::myContinueSignal&){}case __LINE:{
#define coEND()   }}

I hope I've got the code correct, I've never actually plugged any of this into a compiler, so you can be reasonably sure it won't work.

This allows us to take the original state machine and add some niftyness.

void get_some_more_information(continuation *continuation) {
    // Do some stuff, like send a message and then get a response
    // Do some more stuff, like put the response into the class.
    continuation->continue();
}

void myContinuation::run() {
    coBEGIN();

    fprintf(stderr, "Here we are in state 1\n");
    coRETURN();

    fprintf(stderr, "Here we are in state 2\n");
    coRETURN();

    coCALL(get_some_more_information(this));

    fprintf(stderr, "Here we are in state 3\n");

    coEND();
}

Here, if get_some_more_information decides it already has the requested information, it can continue immediately. If decides that it will have to block, it can use it's own continuation to throw back through myContinuation::run while still preserving the state for later execution.

Why is this useful? We could pass the coroutine down and execute it again later. If we did that, when get_some_more_information eventually returned the code would again execute. We could try to execute the continuation at a possibly new state, but that may not be what we want. It results in hard to manage execution paths, with the code possibly getting extra, undesired state transitions.

These continuations are still limited. Due to the try/catch blocks, we can't really interleave continuations of the same type. The destruction of the higher stack frames makes it difficult to have multiple continuations active at any one point in time. Finally, we can't return to the same continuation point more than once, meaning we can't store a state and then return to it at a future point, to, for example, re-attempt a transaction.

Coroutines and Continuations. Both are great at decreasing the amount of bug-ridden, hard to read, unmaintainable C++ state machine code you have to write. I know it's helped me get more done in a day.