Duff's Device: History and Optimization Problem

Duff's device is a famous loop-unrolling idiom in C devised by Tom Duff in 1983 to optimize serial data transfer. Developed at Lucasfilm, this technique solved a severe performance bottleneck caused by loop-control overhead when pushing graphics data to an output register. By exploiting a syntactically valid yet obscure quirk of the C language—interleaving a switch statement with a do-while loop—it allowed the program to jump directly into an unrolled loop body to handle arbitrary remainder counts without requiring separate prologue or epilogue code.

The Historical Context: Lucasfilm in 1983

In May 1983, programmer Tom Duff was working in the Computer Graphics Project at Lucasfilm (the division that would later spin off to become Pixar). The team was developing advanced computer graphics for film, which required processing and outputting massive amounts of image data.

The task involved transmitting arrays of 16-bit units from main memory to an Evans & Sutherland Picture System or a similar frame-buffer device. In this architecture, hardware communication occurred through memory-mapped I/O: sending data did not mean copying an array from one memory buffer to another (memcpy), but rather writing every consecutive element of a source buffer into a single, fixed memory-mapped register address.

The C code representing this operation was conceptually simple:

register short *to, *from;
register int count;

do {
    *to = *from++;
} while (--count > 0);

Because to did not increment, standard library copy routines could not be used.

The Optimization Problem

On the hardware of the era—primarily the DEC VAX-11/780 running Unix—memory and bus speeds were tightly constrained, and CPU cycles were precious. In the simple loop above, each iteration executed three distinct operations:

  1. Copying the data (*to = *from++)
  2. Decrementing the counter (--count)
  3. Evaluating the conditional branch (> 0) and jumping back to the top of the loop

The loop administration logic (decrementing and branching) consumed substantially more processor time than the actual payload instruction. To maximize throughput, Duff needed to minimize loop overhead using loop unrolling, a standard technique where the loop body is replicated multiple times.

If the loop was unrolled eight times, it would look like this:

do {
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
} while ((count -= 8) > 0);

This reduced branch and decrement operations by 87.5%. However, this straightforward unrolling assumes count is a strict multiple of eight. In real-world graphical data, array lengths varied unpredictably.

The conventional solution was to write two separate loops: a primary unrolled loop for blocks of eight, and a smaller cleanup loop handling the remaining elements (count % 8). Duff wanted to avoid the extra code size and branching overhead of two loops, seeking a way to enter a single unrolled loop at the exact offset required for the remainder on the very first pass.

The Invention of Duff's Device

While considering assembly-level implementations where one could simply jump into the middle of an unrolled block, Duff realized that the C grammar permitted an unusual construct. In C, a switch statement does not create an isolated scope; case labels can appear inside nested sub-blocks within the switch body. Furthermore, C supports implicit fall-through between cases unless interrupted by a break.

By wrapping the unrolled assignments in a do-while loop and placing case labels before each assignment inside the loop, the switch statement could jump directly into the loop body to execute the remainder of count % 8. Subsequent iterations would then complete the entire eight-assignment block until the counter was exhausted.

The resulting construct was:

send(to, from, count)
register short *to, *from;
register count;
{
    register 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);
    }
}

Impact and Relevance

When Duff posted this construct to the net.lang.c Usenet group in August 1983, it surprised many C programmers and language implementers. Bjarne Stroustrup and Dennis Ritchie confirmed that the code was strictly compliant with the C grammar defined in the K&R specification, even though it looked syntactically invalid to the untrained eye.

In modern computing, Duff's device is largely obsolete for its original performance purpose. Modern optimizing compilers automatically unroll loops and vectorize memory copies. Modern CPU architectures rely heavily on branch prediction, deep instruction pipelines, and instruction caches, where irregular jump targets like nested switch structures can degrade performance rather than improve it. Nevertheless, the mechanism remains widely studied in computer science as a demonstration of C's low-level flexibility and is occasionally adapted for implementing lightweight coroutines and state machines in embedded systems.