Loop Optimization--Part 3 of Chapter 10 from Speed Up Your Site (2/6)--WebReference.com

[previous] [next]

Speed Up Your Site, Chapter 10: Optimizing JavaScript for Execution Speed

Hoist Loop-Invariant Code

Move loop-invariant code out of loops (otherwise called coding motion out of loops) to speed their execution. Rather than recomputing the same value in each iteration, move it outside the loop and compute it only once. So instead of this:

for (i=0;i<iter;i++) {
  d=Math.sqrt(y);
  j+=i*d;
}

Do this:

d=Math.sqrt(y);
for (i=0;i<iter;i++) {
  j+=i*d;
}

Reverse Loops

Reversing loop conditions so that they count down instead of up can double the speed of loops. Counting down to zero with the decrement operator (i--) is faster than counting up to a number of iterations with the increment operator (i++). So instead of this (see Listing 10.9):

Listing 10.9 A Normal for Loop Counts Up

function loopNormal() {
  for (var i=0;i<iter;i++) {
    // do something here
  }
}

Do this (see Listing 10.10):

Listing 10.10 A Reversed for Loop Counts Down

function loopReverse() {
  for (var i=iter;i>0;i--) {
    // do something here
  }
}

Flip Loops

Loop flipping moves the loop conditional from the top to the bottom of the loop. The theory is that the do while construct is faster than a for loop. So a normal loop (see Listing 10.9) would look like this flipped (see Listing 10.11):

Listing 10.11 A Flipped Loop Using do while

function loopDoWhile() {
var i=0;
do 
{
  i++;
}
while (i<iter);
}

In JavaScript, however, this technique gives poor results. IE 5 Mac gives inconsistent results, while IE and Netscape for Windows are 3.7 to 4 times slower. The problem is the complexity of the conditional and the increment operator. Remember that we're measuring loop overhead here, so small changes in structure and conditional strength can make a big difference. Instead, combine the flip with a reverse count (see Listing 10.12):

Listing 10.12 Flipped Loop with Reversed Count

function loopDoWhileReverse() {
var i=iter;
do 
{
  i--;
}
while (i>0);
}

This technique is more than twice as fast as a normal loop and slightly faster than a flipped loop in IE5 Mac. Even better, simplify the conditional even more by using the decrement as a conditional like this (see Listing 10.13):

Listing 10.13 Flipped Loop with Improved Reverse Count

function loopDoWhileReverse2() {
var i=iter-1;
do 
{
  // do something here
}
while (i--);
}

This technique is over three times faster than a normal for loop. Note the decrement operator doubles as a conditional; when it gets to zero, it evaluates as false. One final optimization is to substitute the pre-decrement operator for the post-decrement operator for the conditional (see Listing 10.14).

Listing 10.14 Flipped Loop with Optimized Reverse Count

function loopDoWhileReverse3() {
var i=iter;
do 
{
  // do something here
}
while (--i);
}

This technique is over four times faster than a normal for loop. This last condition assumes that i is greater than zero. Table 10.2 shows the results for each loop type listed previously for IE5 on my Mac PowerBook.

Table 10.2 Loop Optimizations Compared

	Normal	Do While	Reverse	Do While Reverse	Do While Reverse2	Do While Reverse3
Total time (ms)	2022	1958	1018	932	609	504
Cycle time (ms)	0.0040	0.0039	0.0020	0.0018	0.0012	0.0010

[previous] [next]

Created: January 27, 2003
Revised: January 27, 2003

URL: https://webreference.com/programming/optimize/speedup/chap10/3/2.html