For C Programmers: Duff's Device - Loop Unrolling Optimization
retained text
This is something I had written long back on reddit - copy/pasting it with some small edits
---
I had first encountered this code in Stroustrup's book C++ PL 3e
Stroustrup had Duff's code as an unsolved exercise in one of the chapters - "What does this do?" followed by the code. Quite obviously I couldn't figure out head nor tail of what this strange block of code did & had to google to figure out the history of what was called "Duff's Device".
--------------------------------------------
Not a very useful technique in today's world but just fun to learn/know stuff
#Loop Unrolling & Duff's Device
Let's say you had to write some code which did a particular thing 100 times, this is how you would typically write it
for (int i = 0; i < 100; ++i)
{
doStuff
}
Now this code does a condition check 100 times - checks 100 times if *i < 100*. Also increments *i* 100 times. So 200 extra steps executed other than the 100 doStuff you wanted to do.
So how do you optimize this program?
One way is to do loop unrolling
for (int i = 0; i < 100; i = i + 10)
{
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
}
Now this does the same thing as the previous program, but instead of 100 *if* checks, you do only 10 *if* checks. Instead of 100 increments, you do only 10 increments.
This is a technique which **tries** to make your program run faster at the expense of a bigger executable size.
Nowadays, compilers do this optimization for you. i.e. you write regular code and the optimizer does the loop unrolling for you while producing the assembly. So you rarely have to manually do loop unrolling these days.
However, long back (when Duff was a programmer), people coding in assembly used to do their own loop unrolling to make the program run faster.
Also people writing C code also used to do their own unrolling because there were either no optimizing compilers or because the optimizers weren't mature enough.
The loop unrolling we saw above looks like it looks because you wanted to do 10 doStuff in each iteration. And you wanted the total no of doStuff to be 100. 100 is exactly divisible by 10. But what when the number is not be exactly divisible.
For eg. you want to doStuff 23 times & you unroll it to do 5 per iteration, then 3 doStuff calls are left and the code becomes
for (int i = 0; i < 20; i = i + 5)
{
doStuff
doStuff
doStuff
doStuff
doStuff
}
// Do the remaining 3 after exiting from the loop.
doStuff
doStuff
doStuff
Let's you want to write a function which unrolls a loop which does the work 8 times in each iteration, it's easy enough to code the initial part
void unroll(int count)
{
int i = count/8;
for (int i = 0; i < count; i = i + 8)
{
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
doStuff
}
// How many times to call doStuff
// after exiting the loop?
}
One way to do it was to write the remaining stuff using a 2nd loop.
However, in 1984, Thomas Duff, who was a programmer at Lucas Film wrote some clever code to do the Loop Unrolling in a way which took care of the remainder also.
C has a feature (some people would call it a bug) where code falls through case labels unless you put a break before the next case label.
Duff wrote the below code using this feature to do the Loop Unrolling without having to add more code for the remainder
/* DUFF'S DEVICE */
void unroll(int count)
{
int i = (count + 7)/8;
int remainder = count%8;
switch(remainder)
{
case 0:
do {
doStuff
case 7:
doStuff
case 6:
doStuff
case 5:
doStuff
case 4:
doStuff
case 3:
doStuff
case 2:
doStuff
case 1:
doStuff
} while (--i > 0);
}
}
Let's try to understand this code.
Let's say you call unroll with some number divisible by 8 - for e.g. 24.
i = (24+7)/8 = 3
remainder = 24%8 = 0.
switch(0) will code to case 0 ->
which will start a do while loop.
because i = 3, the loop will run 3 times
So totally doStuff will be done 24 times like we want it to.
Next, let's call it with a number not divisible by 8 - say 29.
i = (29 + 7)/8 = 4
remainder = 29%8 = 5
switch(5) will take the code directly to case 5.
Remember the do while loop hasn't started yet.
doStuff will be executed 5 times (case 5, case 4, case 3, case 2 & case 1).Then the while condition will be encountered and *--i* will give 3 and it will go to the do and execute the loop 3 times and then exit out.
So doStuff will be called 29 times (8 times each in 3 iterations) + 5 times.
So totally 29 times like we wanted it.
Clever, huh?
----------
1988, someone on comp.lang.c posted a question about how Duff's code works & Duff answered explaining it & also added a very clever remark - the remark was this
"Many people (even bwk?) have said that the worst feature of C is that switches don't break automatically before each case label. **This code forms some sort of argument in that debate, but I'm not sure whether it's for or against**."
bwk referred to above is Brian Kernighan who wrote the seminal Book on C along with C Inventor Dennis Ritchie
Here is a link to a copy of Duff's 1988 post on usenet .
https://archive.is/G0CYO
The code I gave above is a slightly changed version of Duff's code for easier understanding. But the principle is the same.document fetched 2026-11-20 00:25 · canonical https://reddit.com/r/developersIndia/comments/1y03ykg/for_c_programmers_duffs_device_loop_unrolling