Duff's Device is an optimization technique for
loop unrolling that allows faster execution of loops by minimizing the number of tests.
Tom Duff was credited for this unique
C implementation:
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 (( count -= 8 ) > 0);
}
I couldn't believe my eyes when my friend
Mark showed me this piece of code some years ago. I couldn't imagine that this thing would even compile. If you feel the same, just try it and see for yourself that this is perfectly valid C code.
What confused me was the combined use of the
switch statement and the
do-while loop and how those two interfere to each other. I asked myself,
what a do-while loop really is? In fact, it's nothing more than one label, one if-statement and one goto statement. If you rewrite the code above in terms of labels and gotos you will end up with something like this:
switch ( count % 8 )
{
case 0:
start:
*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++;
if (( count -= 8 ) > 0) goto start;
}
This is equivalent to the original code, but it looks way too familiar. At this point you may wonder "Why interference between switch and loop statement is allowed in C?" The short answer is "Why not?" The long answer could be that the purpose of the C programming language was to make programmers' lives easier, but by no means to deprive the unlimited power and control that
assembly so generously offered. If something could be implemented in assembly, it should also be implementable in C, only look prettier...
Because
C# does not allow
fall through, the closer you can get to Duff's Device is this ugly implementation:
if (count % 8 == 7) goto case_7;
if (count % 8 == 6) goto case_6;
if (count % 8 == 5) goto case_5;
if (count % 8 == 4) goto case_4;
if (count % 8 == 3) goto case_3;
if (count % 8 == 2) goto case_2;
if (count % 8 == 1) goto case_1;
case_0:
toBuffer[i++] = fromBuffer[i++];
case_7:
toBuffer[i++] = fromBuffer[i++];
case_6:
toBuffer[i++] = fromBuffer[i++];
case_5:
toBuffer[i++] = fromBuffer[i++];
case_4:
toBuffer[i++] = fromBuffer[i++];
case_3:
toBuffer[i++] = fromBuffer[i++];
case_2:
toBuffer[i++] = fromBuffer[i++];
case_1:
toBuffer[i++] = fromBuffer[i++];
if (( count -= 8 ) > 0) goto case_0;
In
Java things are even worse. Java allows fall through, but will not allow interference between the switch statement and the do-while loop. Also Java's lack of a goto statement makes impossible to follow the other two approaches.