Duff's device

In the C programming language, Duff's device is a way of manually implementing loop unrolling by interleaving two syntactic constructs of C, the do-while loop construct, and a switch statement. Its discovery is credited to Tom Duff in November 1983, who at the time was working for Lucasfilm and used it to speed up a real-time animation program.

Loop unrolling attempts to reduce the overhead of conditional branching needed to check whether a loop is done, by executing a batch of loops bodies per iteration. To handle cases where the number of iterations is not divisible by the unrolled-loop increments, a common technique among assembly language programmers is to jump directly into the middle of the unrolled loop body to handle the remainder. Duff was looking to implement this technique in C, and succeeded in doing so by using C's case label fall-through feature to jump into the unrolled body.

When used with modern optimizing compilers, Duff's device may no longer provide any performance improvements.

Duff's problem was to copy 16-bit units ("shorts" in most C implementations) from an array into a memory-mapped output register, denoted in C by a pointer. His original code, in K&R C, looked as follows:

This code assumes that initial count > 0. The pointer to is not incremented as it would be required for a memory-to-memory copy. If count were always divisible by eight, unrolling this loop eight-fold would produce the following:

Duff realized that to handle cases where count is not divisible by eight, the assembly programmer's technique of jumping into the loop body could be implemented by interlacing the structures of a switch statement and a loop, putting the switch's case labels at the points of the loop body that correspond to the remainder of count / 8:

...
Wikipedia