Duff’s Device pattern in JavaScript
Duff’s Device is a technique of unrolling loop bodies so that each iteration actually does
the job of many iterations. Jeff Greenberg is credited with the first published port of
Duff’s Device to JavaScript from its original implementation in C. A typical implementation
looks like this:
//credit: Jeff Greenberg
var iterations = Math.floor(items.length / 8),
startAt = items.length % 8,
i = 0;
do {
switch(startAt){
case 0: process(items[i++]);
case 7: process(items[i++]);
case 6: process(items[i++]);
case 5: process(items[i++]);
case 4: process(items[i++]);
case 3: process(items[i++]);
case 2: process(items[i++]);
case 1: process(items[i++]);
}
startAt = 0;
} while (iterations--);
The basic idea behind this Duff’s Device implementation is that each trip through the
loop is allowed a maximum of eight calls to process(). The number of iterations
through the loop is determined by dividing the total number of items by eight. Because
not all numbers are evenly divisible by eight, the startAt variable holds the remainder
and indicates how many calls to process() will occur in the first trip through the loop.
If there were 12 items, then the first trip through the loop would call process() 4 times,
and then the second trip would call process() 8 times, for a total of two trips through
the loop instead of 12.
A slightly faster version of this algorithm removes the switch statement and separates
the remainder processing from the main processing:
//credit: Jeff Greenberg
var iterations = items.length % 8;
i = items.length -1;
while(iterations){
process(items[i--]);
iterations--;
}
iterations = Math.floor(items.length / 8);
while(iterations){
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
process(items[i--]);
iterations--;
}
Even though this implementation is now two loops instead of one, it runs faster than
the original by removing the switch statement from the loop body.
It can be useful for performance improvement if the number of iteration is more than 1000.
courtesy:
High Performance JavaScript by Nicholas Sakas
