Duff's Device

14 Oct 2008

I previously wrote about Generators and Coroutines (which I'm still not sure how useful it is yet). The technique was originally based on "Duff's Device" which involves interlacing switch and a loop. Here's a modernized version of the original:

void send(register short *to,
          register short *from,
          register count)
{
 register 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);
 }
}

Here *to is a magic hardware device, so it doesn't need incrementing. Stare at that for a while, then read the Wikipedia article and the entertaining posts by Duff himself.

While it's very compact, I'm not sure if it's any better than:

 int buckets = count / 8
 for (int i = buckets; i > 0; --i) {
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
    *to = *from++;
}

switch ( count % 8 ) {
  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++;
  case 0: ;
 }
}

Which is a more flexible technique I've used successfully in my stringencoders project. No weird switch statements, but you the main benefit of 8x less comparisons in the loop body.

fun stuff regardless