PLS Lab

Duff's device

Duff's device is a programming style that reduces the number of jumps through loop unrolling.

Description

Suppose we have a loop of the form

  do {
    easy instruction; i := i - 1;
  } while (i >= 0);

This generates a jump for every iteration of the loop.

If we knew that i is always divisible by, say, 4, we could reduce the number of jumps by producing the following equivalent code instead, where / is integer division:

  i := i / 4;
  do {
    easy instruction; 
    easy instruction;
    easy instruction;
    easy instruction;
  } while (i >= 0);

This reduces the number of jumps by a factor of 4.

But if we don't know that divisibility, we can abuse a fall-through switch statement to cover for the remainder upon division by 4:

  n := (i + 3) / 4;
  switch (i mod 8) {
    case 0: do { easy instruction;
    case 1:      easy instruction;
    case 2:      easy instruction;
                 n := n - 1;
            } while (n >= 0);

This is not legal in most modern imperative programming languages, but was legal in original C.

References