Duff's device
In computer science, Duff's device is an optimized implementation of a serial copy, called loop unrolling.
It is perhaps the most dramatic use yet seen of fall through in the C programming language, and was invented by Tom Duff while he was at Lucasfilm Games (which later became known as LucasArts). Whilst optimising an inner loop that copied data serially onto an output port, he decided to unroll it. He then realised that the unrolled version could be implemented by interlacing the structures of a switch and a loop:
int n = (count + 7) / 8; /* count > 0 assumed */
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);
}
Based on a widely-used assembly language algorithm for minimizing the number of tests and branches during a copy, it appears out of place when implemented in C. The device is indeed perfectly valid, legal C, and many compilers will optimize the switch into a jump table just as would be done in an assembler implementation. C's default fall through in case statements has long been its most controversial single feature; Duff observed that "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against."
This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.
Additional note: The original Device was made for copying to a register. To actually copy memory from one location to another, you must add an auto-increment to every reference to to, like so:
*to++ = *from++;
This modified form of the Device appears as a "what does this code do?" exercise in Bjarne Stroustrup's book The C++ Programming Language, presumably because novice programmers cannot be expected to know about memory-mapped output registers. However, it is not particularly useful in this form since the standard C library already supplies a memory-copying function which is likely to be even better optimized.
Books
- Bjarne Stroustrup: The C++ Programming Language, Third Edition, Addison-Wesley, ISBN 0-201-88954-4