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

[next]

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

Optimize Loops

[The following is the conclusion of our series of excerpts from Chapter 10 of the New Riders title, Speed Up Your Site: Web Site Optimization.]

Most hot spots are inner loops, which are commonly used for searching and sorting. There are a number of ways to optimize the speed of loops: removing or simplifying unnecessary calculations, simplifying test conditions, loop flipping and unrolling, and loop fusion. The idea is to reduce the cost of loop overhead and to include only repeated calculations within the loop.

Combine Tests to Avoid Compound Conditions

"An efficient inner loop should contain as few tests as possible, and preferably only one."^[14] Try to simulate exit conditions of the loop by other means. One technique is to embed sentinels at the boundary of data structures to reduce the cost of testing searches. Sentinels are commonly used for arrays, linked lists, and binary search trees. In JavaScript, however, arrays have the length property built-in, at least after version 1.2, so array boundary sentinels are more useful for arrays in languages like C.

One example from Scott Porter of JavaScript-Games.org is splitting an array of numeric values into separate arrays for extracting the data for a background collision map in a game. The following example of using sentinels also demonstrates the efficiency of the switch statement:

var serialData=new
Array(-1,10,23,53,223,-1,32,98,45,32,32,25,-1,438,54,26,84,-1,487,43,11);
var splitData=new Array();
function init(){
  var ix=-1,n=0,s,l=serialData.length;
  for(;n<l;n++){
    s=serialData[n];
    switch(s){ // switch blocks are much more efficient
      case -1 : // than if... else if... else if...
        splitData[++ix]=new Array();
        break;
      default :
        splitData[ix].push(s);
    }
  }
  alert(splitData.length);
}

Scott Porter explains the preceding code using some assembly language and the advantage of using the switch statement:

"Here, -1 is the sentinel value used to split the data blocks. Switch blocks should always be used where possible, as it's so much faster than an if—else series. This is because with the if else statements, a test must be made for each "if" statement, whereas switch blocks generate vector jump tables at compile time so NO test is actually required in the underlying code! It's easier to show with a bit of assembly language code. So an if/else statement:

  if(n==12)
    someBlock();
  else if(n==26)
    someOtherBlock();

becomes something like this in assembly:

  cmp eax,12;
  jz  someBlock;
  cmp eax,26;
  jz  someOtherBlock;

Whereas a switch statement:

switch(a){
  case 12 :
    someBlock();
    break;
  case 26 :
    someOtherBlock();
    break;
}

becomes something like this in assembly:

  jmp [VECTOR_LIST+eax];

where VECTOR_LIST would be a list of pointers to the address of the start of the someBlock and someOtherBlock functions. At least this would be the method if the switch were based on a numeric value. For string values I'd imagine eax would be replaced by a pointer to the location of a string for the comparison.

As you can see, the longer the if...else if... block became, the more efficient the switch block would become in comparison."^[15]

Next, let's look at some ways to minimize loop overhead. Using the right techniques, you can speed up a for loop by two or even three times.

---

14. Bentley, Programming Pearls, 192. Back

15. Scott Porter, email to author, 16 July 2002. Back

[next]

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

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