For More Information

Refactoring is a discipline unto itself. In fact, entire books have been written on the subject. See Martin Fowler's book, Refactoring: Improving the Design of Existing Code (Addison-Wesley, 1999). See also his catalog of refactorings at http://www.refactoring.com/.

Minimize DOM Interaction and I/O

Interacting with the DOM is significantly more complicated than arithmetic computations, which makes it slower. When the JavaScript interpreter encounters a scoped object, the engine resolves the reference by looking up the first object in the chain and working its way through the next object until it finds the referenced property. To maximize object resolution speed, minimize the scope chain of objects. Each node reference within an element's scope chain means more lookups for the browser. Keep in mind that there are exceptions, like the window object, which is faster to fully reference. So instead of this:

var link = location.href;

Do this:

var link = window.location.href;

Minimize Object and Property Lookups

Object-oriented techniques encourage encapsulation by tacking sub-nodes and methods onto objects. However, object-property lookups are slow, especially if there is an evaluation. So instead of this:

for(var i = 0; i < 1000; i++)
  a.b.c.d(i);

Do this:

var e = a.b.c.d;
for(var i = 0; i < 1000; i++)
  e(i);

Reduce the number of dots (object.property) and brackets (object["property"]) in your program by caching frequently used objects and properties. Nested properties are the worst offenders (object.property.property.property).

Here is an example of minimizing lookups in a loop. Instead of this:

for (i=0; i<someArrayOrObject.length; i++)

Do this:

for (i=0, var n=someArrayOrObject.length; i<n; i++)

Also, accessing a named property or object requires a lookup. When possible, refer to the object or property directly by using an index into an object array. So instead of this:

var form = document.f2; // refer to form by name

Do this:

var form = document.forms[1]; // refer to form by position

Shorten Scope Chains

Every time a function executes, JavaScript creates an execution context that defines its own little world for local variables. Each execution context has an associated scope chain object that defines the object's place in the document's hierarchy. The scope chain lists the objects within the global namespace that are searched when evaluating an object or property. Each time a JavaScript program begins executing, certain built-in objects are created.

The global object lists the properties (global variables) and predefined values and functions (Math, parseInt(), etc.) that are available to all JavaScript programs.

Each time a function executes, a temporary call object is created. The function's arguments and variables are stored as properties of its call object. Local variables are properties of the call object.

Within each call object is the calling scope. Each set of brackets recursively defines a new child of that scope. When JavaScript looks up a variable (called variable name resolution), the JavaScript interpreter looks first in the local scope, then in its parent, then in the parent of that scope, and so on until it hits the global scope. In other words, JavaScript looks at the first item in the scope chain, and if it doesn't find the variable, it bubbles up the chain until it hits the global object.

That's why global scopes are slow. They are worst-case scenarios for object lookups.

During execution, only with statements and catch clauses affect the scope chain.

with (document.formname) {
field1.value = "one";
field2.value = "two";...
}

Do this:

var form = document.formname;
form.field1.value = "one";
form.field2.value = "two;

Cache the object or property reference instead of using with, and use this variable for repeated references. with also has been deprecated, so it is best avoided.

Add Complex Subtrees Offline

When you are adding complex content to your page (like a table), you will find it is faster to build your DOM node and all its sub-nodes offline before adding it to the document. So instead of this (see Listing 10.1):

Listing 10.1 Adding Complex Subtrees Online

var tableEl, rowEl, cellEl;
var numRows = 10;
var numCells = 5;
tableEl = document.createElement("TABLE");
tableEl = document.body.appendChild(tableEl);
for (i = 0; i < numRows; i++) {
  rowEl = document.createElement("TR"); 
  for (j = 0; j < numCells;j++) {
    cellEl = document.createElement("TD");
    cellEl.appendChild(document.createTextNode("[row "+i+" cell "+j+ "]"));
    rowEl.appendChild(cellEl);
  }
  tableEl.appendChild(rowEl);
}

Do this (see Listing 10.2):

Listing 10.2 Adding Complex Subtrees Offline

var tableEl, rowEl, cellEl;
var numRows = 10;
var numCells = 5;
tableEl = document.createElement("TABLE");
for (i = 0; i < numRows; i++) {
  rowEl = document.createElement("TR"); 
  for (j = 0; j < numCells;j++) {
    cellEl = document.createElement("TD");
    cellEl.appendChild(document.createTextNode("[row " +i+ " cell "+j+"]"));
    rowEl.appendChild(cellEl);
  }
  tableEl.appendChild(rowEl);
 }
document.body.appendChild(tableEl);

Listing 10.1 adds the table object to the page immediately after it is created and adds the rows afterward. This runs much slower because the browser must update the page display every time a new row is added. Listing 10.2 runs faster because it adds the resulting table object last, via document.body.appendChild().

Edit Subtrees Offline

In a similar fashion, when you are manipulating subtrees of a document, first remove the subtree, modify it, and then re-add it. DOM manipulation causes large parts of the tree to recalculate the display, slowing things down. Also, createElement() is slow compared to cloneNode(). When possible, create a template subtree, and then clone it to create others, only changing what is necessary. Let's combine these two optimizations into one example. So instead of this (see Listing 10.3):

Listing 10.3 Editing Subtrees Online

var ul = document.getElementById("myUL");
for (var i = 0; i < 200; i++) {
  ul.appendChild(document.createElement("LI"));
}

Do this (see Listing 10.4):

Listing 10.4 Editing Subtrees Offline

var ul = document.getElementById("myUL");
var li = document.createElement("LI");
var parent = ul.parentNode;
parent.removeChild(ul);
for (var i = 0; i < 200; i++) {
  ul.appendChild(li.cloneNode(true));
}
parent.appendChild(ul);

By editing your subtrees offline, you'll realize significant performance gains. The more complex the source document, the better the gain. Substituting cloneNode instead of createElement adds an extra boost.

Concatenate Long Strings

By the same token, avoid multiple document.writes in favor of one document.write of a concatenated string. So instead of this:

document.write(' string 1');
document.write(' string 2');
document.write(' string 3');
document.write(' string 4');

Do this:

var txt = ' string 1'+
' string 2'+
' string 3'+
' string 4';
document.write(txt);

Access NodeLists Directly

NodeLists are lists of elements from object properties like .childNodes and methods like getElementsByTagName(). Because these objects are live (updated immediately when the underlying document changes), they are memory intensive and can take up many CPU cycles. If you need a NodeList for only a moment, it is faster to index directly into the list. Browsers are optimized to access node lists this way. So instead of this:

nl = document.getElementsByTagName("P");
for (var i = 0; i < nl.length; i++) {
  p = nl[i];
}

Do this:

for (var i = 0; (p = document.getElementsByTagName("P")[i]); i++)

In most cases, this is faster than caching the NodeList. In the second example, the browser doesn't need to create the node list object. It needs only to find the element at index i at that exact moment.

Use Object Literals

Object literals work like array literals by assigning entire complex data types to objects with just one command. So instead of this:

car = new Object();
car.make = "Honda";
car.model = "Civic";
car.transmission = "manual";
car.miles = 1000000;
car.condition = "needs work";

Do this:

car = {
  make: "Honda",
  model: "Civic",
  transmission: "manual",
  miles: 1000000,
  condition: "needs work"
}

This saves space and unnecessary DOM references.

Local Optimizations

Okay, you've switched to a better algorithm and revamped your data structure. You've refactored your code and minimized DOM interaction, but speed is still an issue. It is time to tune your code by tweaking loops and expressions to speed up hot spots. In his classic book, Writing Efficient Programs (Prentice Hall, 1982), Jon Bentley revealed 27 optimization guidelines for writing efficient programs. These code-tuning rules are actually low-level refactorings that fall into five categories: space for time and vice versa, loops, logic, expressions, and procedures. In this section, I touch on some highlights.

Trade Space for Time

Many of the optimization techniques you can read about in Bentley's book and elsewhere trade space (more code) for time (more speed). You can add more code to your scripts to achieve higher speed by "defactoring" hot spots to run faster. By augmenting objects to store additional data or making it more easily accessible, you can reduce the time required for common operations.

In JavaScript, however, any additional speed should be balanced against any additional program size. Optimize hot spots, not your entire program. You can compensate for this tradeoff by packing and compressing your scripts.

Augment Data Structures

Douglas Bagnall employed data structure augmentation in the miniscule 5K chess game that he created for the 2002 5K contest (http://www.the5k.org/). Bagnall used augmented data structures and binary arithmetic to make his game fast and small. The board consists of a 120-element array, containing numbers representing either pieces, empty squares, or "off-the-board" squares. The off-the-board squares speed up the testing of the sides—preventing bishops, etc., from wrapping from one edge to the other while they're moving, without expensive positional tests.

Each element in his 120-item linear array contains a single number that represents the status of each square. So instead of this:

board=[16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,2,3,4,5,6,2,3,4,5,16,....]

He did this:

bstring="ggggggggggggggggggggg23456432gg11111111gg0000 ... g";
for (z=0;z<120;z++){
   board[z]=parseInt(bstring.charAt(z),35);
}

This base-35 value represents the squares on the board (parseInt using a radix of 35). As alpha "g" corresponds to 16 (the 5th bit; that is, bit 4), Bagnall says he actually could have used base-17 instead of 35. Perhaps this will leave room for future enhancements.

Each position on the board is encoded like this:

bit 4 (16):	0 = on board, 1 = off board.
bit 3  (8):	0 = white, 1 = black.
bits 0-2(7):	0 = empty, non-zero = the piece type:
1 - pawn
2 - rook
3 - knight
4 - bishop
5 - queen
6 - king

So to test the color of a piece, movingPiece, you'd use the following:

ourCol=movingPiece & 8;	// what color is it? 8=black, 0=white
    movingPiece &= 7;	// now we have the color info, dump it.
   if(movingPiece > 1){	// If it is not a pawn.

Bagnall also checks that the piece exists (because the preceding code will return white for an empty square), so he checks that movingPiece is non-empty. To see his code and the game in action, visit the following sites:

• http://halo.gen.nz/chess/

• http://halo.gen.nz/chess/main-branch/ (the actual code)

Cache Frequently Used Values

One of the most effective techniques you can use to speed up your JavaScripts is to cache frequently used values. When you cache frequently used expressions and objects, you do not need to recompute them. So instead of this (see Listing 10.5):

Listing 10.5 A Loop That Needs Caching and Fewer Evaluations

var d=35;
for (var i=0; i<1000; i++) {
  y += Math.sin(d)*10;
}

Do this (see Listing 10.6):

Listing 10.6 Caching Complex Calculations Out of a Loop

var d=35;
var math_sind = Math.sin(d)*10;
for (var i=0; i<1000; i++) {
  y += math_sind;
}

Because Math is a global object, declaring the math_sind variable also avoids resolving to a global object for each iteration. You can combine this technique with minimizing DOM interaction by caching frequently used object or property references. Simplify the calculations within your loops and their conditionals.

Store Precomputed Results

For expensive functions (like sin()), you can precompute values and store the results. You can use a lookup table (O(1)) to handle any subsequent function calls instead of recomputing the function (which is expensive). So instead of this:

function foo(i) {
  if (i < 10) {return i * i - i;}
}

Do this:

values = [0*0-0, 1*1-1, 2*2-2, ..., 9*9-9];
function foo(i) {
  if (i < 10) {return values[i];}
}

This technique is often used with trigonometric functions for animation purposes. A sine wave makes an excellent approximation of the acceleration and deceleration of a body in motion:

for (var i=1; i<=360; i++) {
  sin[i] = Math.sin(i);
}

In JavaScript, this technique is less effective than it is in a compiled language like C. Unchanging values are computed at compile time in C, while in an interpreted language like JavaScript, they are computed at runtime.

Use Local versus Global Variables

Reducing the scope of your variables is not only good programming practice, it is faster. So instead of this (see Listing 10.7):

Listing 10.7 Loop with Global Variable

function MyInnerLoop(){
  for(i=0;i<1000;i++);
}

Do this (see Listing 10.8):

Listing 10.8 Loop with Local Variable

function MyInnerLoop(){
  for(var i=0;i<1000;i++);
}

Local variables are 60 percent to 26 times faster than global variables for tight inner loops. This is due in part to the fact that global variables require more time to search up the function's scope chain. Local variables are properties of the function's call object and are searched first. Netscape 6 in particular is slow in using global variables. Mozilla 1.1 has improved speed, but this technique is relevant to all browsers. See Scott Porter's local versus global test at http://javascript-games.org/articles/local_global_bench.html.

Trade Time for Space

Conversely, you can trade time for space complexity by densely packing your data and code into a more compact form. By recomputing information, you can decrease the space requirements of a program at the cost of increased execution time.

Packing

Packing decreases storage and transmission costs by increasing the time to compact and retrieve the data. Sparse arrays and overlaying data into the same space at different times are two examples of packing. Removing spaces and comments are two more examples of packing. Substituting shorter strings for longer ones can also help pack data into a more compact form.

Interpreters

Interpreters reduce program space requirements by replacing common sequences with more compact representations.

Some 5K competitors (http://www.the5k.org/) combine these two techniques to create self-extracting archives of their JavaScript pages, trading startup speed for smaller file sizes (http://www.dithered.com/experiments/compression/). See Chapter 9, "Optimizing JavaScript for Download Speed," for more details.

Optimize Loops

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."¹⁴ 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:

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

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

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

  jmp [VECTOR_LIST+eax];

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.

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

Unroll or Eliminate Loops

Unrolling a loop reduces the cost of loop overhead by decreasing the number of times you check the loop condition. Essentially, loop unrolling increases the number of computations per iteration. To unroll a loop, you perform two or more of the same statements for each iteration, and increment the counter accordingly. So instead of this:

var iter = number_of_iterations;
for (var i=0;i<iter;i++) {
  foo();
}

Do this:

var iter = multiple_of_number_of_unroll_statements;
for (var i=0;i<iter;) {
  foo();i++;
  foo();i++;
  foo();i++;
  foo();i++;
  foo();i++;
  foo();i++;
}

I've unrolled this loop six times, so the number of iterations must be a multiple of six. The effectiveness of loop unrolling depends on the number of operations per iteration. Again, the simpler, the better. For simple statements, loop unrolling in JavaScript can speed inner loops by as much as 50 to 65 percent. But what if the number of iterations is not known beforehand? That's where techniques like Duff's Device come in handy.

Duff's Device

Invented by programmer Tom Duff while he was at Lucasfilm Ltd. in 1983,¹⁶ Duff's Device generalizes the loop unrolling process. Using this technique, you can unroll loops to your heart's content without knowing the number of iterations beforehand. The original algorithm combined a do-while and a switch statement. The technique combines loop unrolling, loop reversal, and loop flipping. So instead of this (see Listing 10.15):

Listing 10.15 Normal for Loop

testVal=0;
iterations=500125;
for (var i=0;i<iterations;i++) {
  // modify testVal here
}

16. Tom Duff, "Tom Duff on Duff's Device" [electronic mailing list], (Linköping, Sweden: Lysator Academic Computer Society, 10 November 1983 [archived reproduction]), available from the Internet at http://www.lysator.liu.se/c/duffs-device.html. Duff describes the loop unrolling technique he developed while at Lucasfilm Ltd.

Do this (see Listing 10.16):

Listing 10.16 Duff's Device

function duffLoop(iterations) {
  var testVal=0;
  // Begin actual Duff's Device
  // Original JS Implementation by Jeff Greenberg 2/2001
  var n = iterations / 8;
  var caseTest = iterations % 8;  
  do {
    switch (caseTest)
    {
    case 0: [modify testVal here];
    case 7: [ditto];
    case 6: [ditto];
    case 5: [ditto];
    case 4: [ditto];
    case 3: [ditto];
    case 2: [ditto];
    case 1: [ditto];
    }
    caseTest=0;
  }
  while (--n > 0);
}

Like a normal unrolled loop, the number of loop iterations (n = iterations/8) is a multiple of the degree of unrolling (8, in this example). Unlike a normal unrolled loop, the modulus (caseTest = iterations % 8) handles the remainder of any leftover iterations through the switch/case logic. This technique is 8 to 44 percent faster in IE5+, and it is 94 percent faster in NS 4.7.

Fast Duff's Device

You can avoid the complex do/switch logic by unrolling Duff's Device into two loops. So instead of the original, do this (see Listing 10.17):

Listing 10.17 Fast Duff's Device

function duffFastLoop8(iterations) {
// from an anonymous donor to Jeff Greenberg's site
  var testVal=0;	
  var n = iterations % 8;
  while (n--)
  {
    testVal++;
  }
  
  n = parseInt(iterations / 8);
  while (n--)
  {
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
    testVal++;
  }
}

This technique is about 36 percent faster than the original Duff's Device on IE5 Mac. Even better, optimize the loop constructs by converting the while decrement to a do while pre-decrement like this (see Listing 10.18):

Listing 10.18 Faster Duff's Device

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);
}

This optimized Duff's Device is 39 percent faster than the original and 67 percent faster than a normal for loop (see Table 10.3).

Table 10.3 Duff's Device Improved

How Much to Unroll?

To test the effect of different degrees of loop unrolling, I tested large iteration loops with between 1 and 15 identical statements for the Faster Duff's Device. Table 10.4 shows the results.

Table 10.4 Faster Duff's Device Unrolled

As you can see in Table 10.4, the effect diminishes as the degree of loop unrolling increases. Even after two statements, the time to loop through many iterations is less than 50 percent of a normal for loop. Around seven statements, the time is cut by two-thirds. Anything over eight reaches a point of diminishing returns. Depending on your requirements, I recommend that you choose to unroll critical loops by between four and eight statements for Duff's Device.

Fuse Loops

If you have two loops in close proximity that use the same number of iterations (and don't affect each other), you can combine them into one loop. So instead of this:

for (i=0; i<j; i++) {
  sumserv += serv(i);
}
for (i=0; i<j; i++) {
  prodfoo *= foo(i);
}

Do this:

for (i=0; i<j; i++) {
  sumserv += serv(i);
  prodfoo *= foo(i);
}

Expression Tuning

If the evaluation of an expression is costly, replace it with a less-expensive operation. Assuming that a is greater than 0, instead of this:

a > Math.sqrt(b);

Do this:

a*a > b;

Or even better:

var c = a*a;
c>b; 

for (var i=iter;i>0;i--)

Do this:

var i=iter-1;
do {} while (i--);

Miscellaneous Tuning Tips

Summary

• Avoid optimization if at all possible.
• Optimize globally to locally until the code is fast enough.
• Measure your changes.
• Keep Pareto in mind.
• Cool hot spots one at a time.
• Minimize DOM and I/O interaction (object and property lookups, create and edit subtrees offline).
• Shorten scope chains to maximize lookup speed. Avoid with statements because they extend scope chains.
• Cache frequently used values.

• Simplify loop conditions, hoist loop-invariant code, flip and reverse, and unroll loops with an optimized Duff's Device.

• Use local optimizations last.

• Tune expressions for speed.

• Jon Bentley's Programming Pearls, 2nd ed. (Addison-Wesley, 1999) and More Programming Pearls: Confessions of a Coder (Addison-Wesley, 1988). These books include many examples of code tuning and recap the 27 code-tuning rules in his out-of-print classic, Writing Efficient Programs.
• Brian Kernighan and Rob Pike's The Practice of Programming (Addison-Wesley, 1999) describes best programming practices, including Chapter 7 on performance.
• Donald Knuth's The Art of Computer Programming series (Addison-Wesley, 1998).
• Steve C. McConnell's Code Complete: A Practical Handbook of Software Construction (Microsoft Press, 1993), especially Chapters 28 and 29.