In 1983, Tom Duff invented a really strange way to use the C language’s switch and case statements for the in code “unrolling” optimization of large loops. As an example, he described a simple loop that copies an array to an output register:
send(to, from, count)
register short *to, *from;
register count;
{
do
*to = *from++;
while(--count>0);
}
On every iteration of the loop, in addition to the copy that is being performed, the count variable is decremented and a comparison is done against 0. Duff’s Device allows you to achieve the same result, but with only an 8th of the overhead:
send(to, from, count)
register short *to, *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);
}
}
What happens is that the loop is unrolled 8 times, so each iteration of the loop runs the internal code 8 times over without the comparison. The genius of Duff’s Device is that it takes advantage of the way the C switch/case structure works. The first time through, if the iterations don’t divide evenly by 8, the loop code is executed enough times to equal the remainder of iterations/8. It’s a little bizarre, because the “do” statement occurs within the switch, but there are “case” statements within the “do”. Nevertheless, it’s valid C.
Before someone cries foul, remember that this is only really suitable for speeding up the performance of inner loops when no suitable, better algorithm is available. If you code C, most modern compilers are smart enough to automatically optimize your code and unroll loops for you.
For interpreted languages like PHP or Javascript, however, you sometimes need to do a little optimization on your own if you want to squeeze out some extra performance. Luckily, both languages have a c-style switch statement.
Andy King wrote about a slightly altered version of this loop unrolling algorithm which ditches the switch statement and breaks the normal Duff’s Device into two separate loops, one for the remainder and one for the unrolling. In Javascript, it performs a simple addition loop in only a third of the time of a normal for loop (testVal++ is the normal loop’s interior):
function duffFasterLoop8(iterations) {
var testVal=0;
var n = iterations % 8;
if (n>0) {
do
{
testVal++;
}
while (--n); // n must be greater than 0 here
}
n = parseInt(iterations / 8);
do
{
testVal++;
testVal++;
testVal++;
testVal++;
testVal++;
testVal++;
testVal++;
testVal++;
}
while (--n);
}
It’s not as syntactically clever as Duff’s Device, but it’s a good way to manually unroll an inner loop and get the best performance for your extra effort.
Duff’s Device
Andy King’s Optimizing JavaScript For Execution Speed
12 thoughts on “Duff’s Device: loop unrolling for interpreted languages”
Comments are closed.
ADVERTISEMENT
Join Make: Community Today
Thanks! I was searching for this trick for a while! Anyway, if you want the incognito window to be maximized, replace the line:
oSh.Run(“chrome.exe”); //start chrome
with:
oSh.Run(“chrome.exe -start-maximized”); //start chrome
nJoy!
simply append –incognito to the file path, and Chrome will start in incognito mode. you can make this adjustment in the file properties very easily.
SXaving the script to the desktop got me a script error (WSH error). However, when I moved the script file to the Chrome application folder, created a shortcut and put the shortcut on the desktop, it worked.
Agree that the command line entry in properties is easier, but some people don’t always want to run incognito.
Does anyone know how to tell from within Chrome that it is in fact running incognito?
SXaving the script to the desktop got me a script error (WSH error). However, when I moved the script file to the Chrome application folder, created a shortcut and put the shortcut on the desktop, it worked.
Agree that the command line entry in properties is easier, but some people don’t always want to run incognito.
Does anyone know how to tell from within Chrome that it is in fact running incognito?
SXaving the script to the desktop got me a script error (WSH error). However, when I moved the script file to the Chrome application folder, created a shortcut and put the shortcut on the desktop, it worked.
Agree that the command line entry in properties is easier, but some people don’t always want to run incognito.
Does anyone know how to tell from within Chrome that it is in fact running incognito?
howiem, wouldn’t it be easier to just put a shortcut on the desktop with the “–incognito” switch enabled, instead of linking to the script which just does the same thing?
You can tell that a Chrome window is in incognito mode from the incognito symbol in the upper left corner. You know, the one with the hat and the trenchcoat.
Doesn’t work.
right click on nothing, choose new->shortcut. When it asks you what to link to, browse for chrome.exe. after it has filled in “c:/blahblahblah/chrome.exe”, add ” -incognito” to the END. when its done, it should look like:
“C:/blah-blah-blah-directory-of-chrome/chrome.exe” -incognito
test it, it should automatically open an incognito window.