The Loophole That Rewrote the Rules of C
In 1983, Lucasfilm programmer Tom Duff was looking for a way to optimize real-time graphics rendering. He discovered a bizarre loophole in the C programming language. By combining a loop with a switch-case statement, he created a technique that could jump directly into the middle of a loop to speed up execution. Now known as "Duff's Device," this syntactically legal but highly unusual construct surprised even Dennis Ritchie, the creator of C.
The Lucasfilm Rendering Bottleneck
In May 1983, computer scientist Tom Duff was working at Lucasfilm on image processing and animation pipelines. Part of his work involved pushing graphical data to a real-time frame buffer. The operation required copying a continuous sequence of 16-bit short integers from an array in memory to a single, fixed memory-mapped output register. Because the destination address remained identical for every write, standard bulk-memory copy routines could not be used; the program had to explicitly write values one by one in a tight loop.
In naive C code, this transfer was expressed as a simple loop that iterated once for every word transferred. On the hardware of the era, the instructions required to maintain the loop itself—decrementing a counter, checking whether it had reached zero, and executing a conditional branch back to the top—consumed a substantial fraction of the total execution time relative to the single assignment instruction. For time-critical graphical rendering, this loop overhead represented an unacceptable drag on throughput.
The Mechanics of Loop Unrolling
The standard software engineering remedy for loop overhead is loop unrolling. By replicating the loop body several times, the program performs multiple operations per iteration, reducing the frequency of counter checks and branch instructions by a corresponding factor. For example, unrolling a loop eight times allows the program to process eight data items for every single loop evaluation, slashing the branching cost per item by nearly seven-eighths.
The complication with loop unrolling arises when the total number of items to process is not an exact multiple of the unroll factor. If a programmer wants to process twenty items using an eight-step unrolled loop, two full passes of eight items will handle sixteen values, leaving a remainder of four. Traditionally, developers handled this mismatch by calculating the remainder via the modulo operator and executing a separate, standard loop or a switch statement to process the leftover elements before or after running the primary unrolled loop. While straightforward, this dual-structure approach introduces code duplication and additional branching logic.