On Duff's Device and Coroutines

Posted on Wednesday, January 30, 2008.

At first glance, Duff's Device is one of the most mysterious pieces of C code you'll ever see:

    void
    send(short *to, short *from, int count)
    {
        int n=(count+7)/8;
        switch(count%8){
        case 0: do{ *to = *from++;
        case 7:     *to = *from++;
        case 6:     *to = *from++;
        case 5:     *to = *from++;
        case 4:     *to = *from++;
        case 3:     *to = *from++;
        case 2:     *to = *from++;
        case 1:     *to = *from++;
                }while(--n>0);
        }
    }

It's an 8x-unrolled while loop interlaced with a switch statement. The switch jumps into the middle of the while loop to handle the part of the count that isn't a multiple of 8. Once inside the while loop, the switch logic never executes again.

Tom Duff first described Duff's Device in a November 1983 email to Ron Gomes, Dennis Ritchie, and Rob Pike. It spread to a larger group when he revised the note and posted it to net.lang.c in May 1984. The 1984 message is the less frequently reproduced but is the one in which Duff gave it a name: “I think I'll name it after myself — ‘Duff's Device’ has a nice ring to it.” Bjarne Stroustroup used a variant as an example in The C++ Programming Language. Eventually Duff posted the 1983 message along with commentary to Usenet in 1988, in response to a heated debate about the merits of Duff's Device as an idiom.

Duff's Device is rarely worth reusing, but in the specific case that it was written for, it was an apt tool for the job. The more amazing thing about it is that it's valid C. Since a switch statement is just a computed goto and the case labels are just labels, switching into the middle of a while is just as legal as goto'ing there. In Duff's description, he wrote:

It amazes me that after 10 years of writing C there are still little corners that I haven't explored fully. (Actually, I have another revolting way to use switches to implement interrupt driven state machines but it's too horrid to go into.)

In 2000, Simon Tatham wrote about a C coroutine implementation based on this idea, to make callback-based event-driven programming easier. (He used it in his Windows SSH client, PuTTY.) A switch-based implementation has the advantage of being portable and relatively simple to emit using preprocessor macros, though it doesn't allow the use of other switch statements in the code.

A year ago, I asked Duff if that kind of coroutine implementation is what he had in mind, and he confirmed that it was, pointing at a blog comment and adding:

I only ever did this twice: once for a coroutinish application in an SDLC driver (for UNIX to IBM OS/360 communication) in the 1970s and once for loop unwinding in 1983. Both were desperate situations. I have never felt the need to stoop so low since then.

(Today, of course, there are few excuses not to use threads, or at the very least, coroutines with real stacks. If you are stuck with callbacks and events, something like Max Krohn's tame preprocessor is a cleaner solution than macros.)