Duffs device
lastmod 2019-11-25created 2019-11-251 edits
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. Duff implemented this technique in C by using C's case label fall-through feature to jump into the unrolled body.
Example
A faster copy routine presented by Duff.
void copy_duff( char* dst, char* src, int cnt )
{
int repeat = ( cnt + 7 ) / 8;
switch ( cnt % 8 )
{
case 0: do { *dst++ = *src++;
case 7: *dst++ = *src++;
case 6: *dst++ = *src++;
case 5: *dst++ = *src++;
case 4: *dst++ = *src++;
case 3: *dst++ = *src++;
case 2: *dst++ = *src++;
case 1: *dst++ = *src++;
} while ( --repeat > 0 );
}
}
Of course, it works fine even when the target memory is not a multiple of 8 bytes.
The code above works correctly because of the following two characteristics of the C language.
- The loose specification of the switch statement: a case label is syntactically valid as a prefix in front of any other statement.
- The ability in C to jump into the middle of a loop.