C Language Iteration Statements/Loops: for, while, do-while Loop Unrolling and Duff's Device


Example

Sometimes, the straight forward loop cannot be entirely contained within the loop body. This is because, the loop needs to be primed by some statements B. Then, the iteration begins with some statements A, which are then followed by B again before looping.

do_B();
while (condition) {
    do_A();
    do_B();
}

To avoid potential cut/paste problems with repeating B twice in the code, Duff's Device could be applied to start the loop from the middle of the while body, using a switch statement and fall through behavior.

switch (true) while (condition) {
case false: do_A(); /* FALL THROUGH */
default:    do_B(); /* FALL THROUGH */
}

Duff's Device was actually invented to implement loop unrolling. Imagine applying a mask to a block of memory, where n is a signed integral type with a positive value.

do {
    *ptr++ ^= mask;
} while (--n > 0);

If n were always divisible by 4, you could unroll this easily as:

do {
    *ptr++ ^= mask;
    *ptr++ ^= mask;
    *ptr++ ^= mask;
    *ptr++ ^= mask;
} while ((n -= 4) > 0);

But, with Duff's Device, the code can follow this unrolling idiom that jumps into the right place in the middle of the loop if n is not divisible by 4.

switch (n % 4) do {
case 0: *ptr++ ^= mask; /* FALL THROUGH */
case 3: *ptr++ ^= mask; /* FALL THROUGH */
case 2: *ptr++ ^= mask; /* FALL THROUGH */
case 1: *ptr++ ^= mask; /* FALL THROUGH */
} while ((n -= 4) > 0);

This kind of manual unrolling is rarely required with modern compilers, since the compiler's optimization engine can unroll loops on the programmer's behalf.