↑
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

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++];

}

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,

http://home.earthlink.net/

~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