Duff's device - Wikipedia

Jump to content

Search

Search

Donate

Create account

Log in

Personal tools

Donate

Create account

Log in

Duff's device

10 languages

Català<br>Deutsch<br>Español<br>فارسی<br>日本語<br>Polski<br>Русский<br>Türkçe<br>Українська<br>中文

Edit links

From Wikipedia, the free encyclopedia

Implementation of loop unrolling in C

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 and a switch statement. Its discovery is credited to Tom Duff in November 1983, when Duff 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 loop 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.[1]<br>Duff implemented this technique in C by using C's case label fall-through feature to jump into the unrolled body.[2]

Duff's technique<br>[edit]

Duff was copying 16-bit unsigned integers ("shorts" in most C implementations) from an array into a memory-mapped output register, denoted in C by a pointer. He wanted to optimize the following K&R C code:[3][4]

0 assumed */\n *to = *from++;\n } while (--count > 0);\n}\n"}}'>send(to, from, count)<br>register short *to, *from;<br>register count;<br>do { /* count > 0 assumed */<br>*to = *from++;<br>} while (--count > 0);

In K&R C, any unspecified type defaults to int, including variables such as count and the return type of send(). The register keyword is used to suggest that a variable ought to be kept in a CPU register, avoiding memory. Functions could not return void as it was not yet a reserved keyword, but many functions effectively did so by omitting the return statement, which was optional. This signature could idiomatically, but not equivalently, be expressed in a modern C prototype as void send(short* to, short* from, int count);.

This code assumes that the argument passed in count is greater than zero. Since the output location is a memory-mapped register, the pointer to is not incremented, as it would be in copying from memory to memory.

If count were always divisible by eight, unrolling this loop eight-fold would produce the following:

0);\n}\n"}}'>send(to, from, count)<br>register short *to, *from;<br>register count;<br>register n = count / 8;<br>do {<br>*to = *from++;<br>*to = *from++;<br>*to = *from++;<br>*to = *from++;<br>*to = *from++;<br>*to = *from++;<br>*to = *from++;<br>*to = *from++;<br>} while (--n > 0);

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:[1]

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

Duff's device can be applied with any size for the unrolled loop, not just eight as in the example above.

Mechanism<br>[edit]

Based on an algorithm used widely by programmers coding in assembly for minimizing the number of tests and branches during a copy, Duff's device appears out of place when implemented in C. The device is valid C by virtue of two attributes in C:

Relaxed specification of the switch statement in the language's definition. At the time of the device's invention this was the first edition of The C Programming Language which requires only that the body of the switch be a syntactically valid (compound) statement within which case labels can appear prefixing any sub-statement. In conjunction with the fact that, in the absence of a break statement, the flow of control will fall through from a statement controlled by one case label to that controlled by the next, this means that the code specifies a succession of count copies from sequential source addresses to the memory-mapped output port.

The ability to jump into the middle of a loop in C.

This leads to what the Jargon File calls "the most dramatic use yet seen of fall through in C".[5] C's default fall-through in case statements has long been one of its most controversial features; Duff himself said that "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against."[5]

Although valid in C, Duff's device goes against common C guidelines, such as the MISRA guidelines. Some compilers (e.g. CompCert) are restricted to such guidelines and thus reject Duff's device unless...