Duff’s Device

I don’t recall when I first heard of Tom Duff’s amazing device, but I’m sure it was from a USENET posting. Tom Duff invented his device while optimizing a program with loop unrolling. Loop unrolling takes the block of code inside of a loop and duplicates the code to avoid conditional jumps and the testing and incrementing of a variable. If this sounds like a lot of work for little payoff, well, most of us leave it to the compilers these days.

When I first saw the code for Duff’s device, I did a triple-take. I’m not sure if I then laughed, or cried, or just curled up into a little ball. The code was naughty in such a breathtaking way. Here is a version that compiles and works with the C++ compiler in the May CTP of VS 2005:

void send(short *to, short *from, int count)
{
    int n=(count+7)/8;
    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);
    }
}

At first glance, the code appears to be a car wreck involving a switch statement and a do while loop, as they seem smashed together in a way that makes you slow down to look. The code does work and copies an array of shorts to a memory location (in Duff’s case, a memory mapped IO register). Perhaps the code is fodder for the daily WTF blog, except it has appeared in a Bjarne Stroustrup book.

If you are interested in seeing the original unveiling of the device, you can read the original posting here.