﻿ optimize this loop ﻿

Main Page

# optimize this loop

iSum += aValues[i];
i++;
iSum += aValues[i];
i++;
}
In this example, the addition is done five times within the body of the loop. After each addition, the vari-
able
i
is incremented, so it moves along the array in the same way as the original
for
loop did. This
way, the control statement is executed only four times; therefore the entire execution time decreases.
Of course, combining the variable increment with the additions can optimize this loop even further:
var aValues = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
var iSum = 0;
for (var i=0; i < aValues.length; i++) {
iSum += aValues[i++];
iSum += aValues[i++];
iSum += aValues[i++];
iSum += aValues[i++];
iSum += aValues[i++];
}
This code eliminates five more statements, once again decreasing execution time. Is there a generic way
to unroll loops? The answer is yes. Using a technique called Duff’s Device (named after Tom Duff, the
inventor), it’s possible to unroll loops without knowing how much iteration is necessary beforehand.
The loop in the previous example executed 20 times, once for each item in an array. Because of this, the
unrolled loop had to contain either ten, five, four, or two statements (all factors of 20) in order to work
properly. Duff’s Device uses the modulus operator to properly execute an unrolled loop containing eight
identical statements. This technique allows any number of iterations to work properly.
Duff’s Device was originally written in C, but has since been ported to JavaScript by Jeff Greenburg,
who has done exhaustive tests on JavaScript optimization at his site,
~kendrasg/info/js_opt/
. His algorithm is as follows:
var iLoopCount = Math.ceil(iIterations / 8);
var iTestValue = iIterations % 8;
do {
switch (iTestValue) {
case 0: [execute statement];
case 7: [execute statement];
case 6: [execute statement];
case 5: [execute statement];
case 4: [execute statement];
case 3: [execute statement];
case 2: [execute statement];
case 1: [execute statement];
}
586
Chapter 19
22_579088 ch19.qxd 3/28/05 11:43 AM Page 586

Free JavaScript Editor     Ajax Editor