Duff’s Device

Tuesday, June 8, 2004

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.


Comments
Andy Saturday, June 12, 2004
Heh. That's just straight cool and I can actually use it believe it or not. By that I mean I have an immediate use for it. I had not ever seen it before that I can remember and it actually solves a problem I was wondering how to speed up the other day. Thanks for the link!
Comments are now closed.
by K. Scott Allen K.Scott Allen
My Pluralsight Courses
The Podcast!