You are previewing High Performance JavaScript.

High Performance JavaScript

Cover of High Performance JavaScript by Nicholas C. Zakas Published by O'Reilly Media, Inc.
  1. High Performance JavaScript
    1. SPECIAL OFFER: Upgrade this ebook with O’Reilly
    2. Preface
      1. The Internet Evolves
      2. Why Optimization Is Necessary
      3. Next-Generation JavaScript Engines
      4. Performance Is Still a Concern
      5. How This Book Is Organized
      6. JavaScript Loading
      7. Coding Technique
      8. Deployment
      9. Testing
      10. Who This Book Is For
      11. Conventions Used in This Book
      12. Using Code Examples
      13. Safari® Books Online
      14. How to Contact Us
      15. Acknowledgments
    3. 1. Loading and Execution
      1. Script Positioning
      2. Grouping Scripts
      3. Nonblocking Scripts
      4. Summary
    4. 2. Data Access
      1. Managing Scope
      2. Object Members
      3. Summary
    5. 3. DOM Scripting
      1. DOM in the Browser World
      2. DOM Access and Modification
      3. Repaints and Reflows
      4. Event Delegation
      5. Summary
    6. 4. Algorithms and Flow Control
      1. Loops
      2. Conditionals
      3. Recursion
      4. Summary
    7. 5. Strings and Regular Expressions
      1. String Concatenation
      2. Regular Expression Optimization
      3. String Trimming
      4. Summary
    8. 6. Responsive Interfaces
      1. The Browser UI Thread
      2. Yielding with Timers
      3. Web Workers
      4. Summary
    9. 7. Ajax
      1. Data Transmission
      2. Data Formats
      3. Ajax Performance Guidelines
      4. Summary
    10. 8. Programming Practices
      1. Avoid Double Evaluation
      2. Use Object/Array Literals
      3. Don’t Repeat Work
      4. Use the Fast Parts
      5. Summary
    11. 9. Building and Deploying High-Performance JavaScript Applications
      1. Apache Ant
      2. Combining JavaScript Files
      3. Preprocessing JavaScript Files
      4. JavaScript Minification
      5. Buildtime Versus Runtime Build Processes
      6. JavaScript Compression
      7. Caching JavaScript Files
      8. Working Around Caching Issues
      9. Using a Content Delivery Network
      10. Deploying JavaScript Resources
      11. Agile JavaScript Build Process
      12. Summary
    12. 10. Tools
      1. JavaScript Profiling
      2. YUI Profiler
      3. Anonymous Functions
      4. Firebug
      5. Internet Explorer Developer Tools
      6. Safari Web Inspector
      7. Chrome Developer Tools
      8. Script Blocking
      9. Page Speed
      10. Fiddler
      11. YSlow
      12. dynaTrace Ajax Edition
      13. Summary
    13. Index
    14. About the Author
    15. Colophon
    16. SPECIAL OFFER: Upgrade this ebook with O’Reilly
O'Reilly logo

Chapter 4. Algorithms and Flow Control

The overall structure of your code is one of the main determinants as to how fast it will execute. Having a very small amount of code doesn’t necessarily mean that it will run quickly, and having a large amount of code doesn’t necessarily mean that it will run slowly. A lot of the performance impact is directly related to how the code has been organized and how you’re attempting to solve a given problem.

The techniques in this chapter aren’t necessarily unique to JavaScript and are often taught as performance optimizations for other languages. There are some deviations from advice given for other languages, though, as there are many more JavaScript engines to deal with and their quirks need to be considered, but all of the techniques are based on prevailing computer science knowledge.


In most programming languages, the majority of code execution time is spent within loops. Looping over a series of values is one of the most frequently used patterns in programming and as such is also one of the areas where efforts to improve performance must be focused. Understanding the performance impact of loops in JavaScript is especially important, as infinite or long-running loops severely impact the overall user experience.

Types of Loops

ECMA-262, 3rd Edition, the specification that defines JavaScript’s basic syntax and behavior, defines four types of loops. The first is the standard for loop, which shares its syntax with other C-like languages:

for (var i=0; i < 10; i++){
    //loop body

The for loop tends to be the most commonly used JavaScript looping construct. There are four parts to the for loop: initialization, pretest condition, post-execute, and the loop body. When a for loop is encountered, the initialization code is executed first, followed by the pretest condition. If the pretest condition evaluates to true, then the body of the loop is executed. After the body is executed, the post-execute code is run. The perceived encapsulation of the for loop makes it a favorite of developers.


Note that placing a var statement in the initialization part of a for loop creates a function-level variable, not a loop-level one. JavaScript has only function-level scope, and so defining a new variable inside of a for loop is the same as defining a new variable outside of the loop.

The second type of loop is the while loop. A while loop is a simple pretest loop comprised of a pretest condition and a loop body:

var i = 0;
while(i < 10){
    //loop body

Before the loop body is executed, the pretest condition is evaluated. If the condition evaluates to true, then the loop body is executed; otherwise, the loop body is skipped. Any for loop can also be written as a while loop and vice versa.

The third type of loop is the do-while loop. A do-while loop is the only post-test loop available in JavaScript and is made up of two parts, the loop body and the post-test condition:

var i = 0;
do {
    //loop body
} while (i++ < 10);

In a do-while loop, the loop body is always executed at least once, and the post-test condition determines whether the loop should be executed again.

The fourth and last loop is the for-in loop. This loop has a very special purpose: it enumerates the named properties of any object. The basic format is as follows:

for (var prop in object){
    //loop body

Each time the loop is executed, the prop variable is filled with the name of another property (a string) that exists on the object until all properties have been returned. The returned properties are both those that exist on the object instance and those inherited through its prototype chain.

Loop Performance

A constant source of debate regarding loop performance is which loop to use. Of the four loop types provided by JavaScript, only one of them is significantly slower than the others: the for-in loop.

Since each iteration through the loop results in a property lookup either on the instance or on a prototype, the for-in loop has considerably more overhead per iteration and is therefore slower than the other loops. For the same number of loop iterations, a for-in loop can end up as much as seven times slower than the other loop types. For this reason, it’s recommended to avoid the for-in loop unless your intent is to iterate over an unknown number of object properties. If you have a finite, known list of properties to iterate over, it is faster to use one of the other loop types and use a pattern such as this:

var props = ["prop1", "prop2"],
    i = 0;

while (i < props.length){

This code creates an array whose members are property names. The while loop is used to iterate over this small number of properties and process the appropriate member on object. Rather than looking up each and every property on object, the code focuses on only the properties of interest, saving loop overhead and time.


You should never use for-in to iterate over members of an array.

Aside from the for-in loop, all other loop types have equivalent performance characteristics such that it’s not useful to try to determine which is fastest. The choice of loop type should be based on your requirements rather than performance concerns.

If loop type doesn’t contribute to loop performance, then what does? There are actually just two factors:

  • Work done per iteration

  • Number of iterations

By decreasing either or both of these, you can positively impact the overall performance of the loop.

Decreasing the work per iteration

It stands to reason that if a single pass through a loop takes a long time to execute, then multiple passes through the loop will take even longer. Limiting the number of expensive operations done in the loop body is a good way to speed up the entire loop.

A typical array-processing loop can be created using any of the three faster loop types. The code is most frequently written as follows:

//original loops
for (var i=0; i < items.length; i++){

var j=0;
while (j < items.length){

var k=0;
do {
} while (k < items.length);

In each of these loops, there are several operations happening each time the loop body is executed:

  1. One property lookup (items.length) in the control condition

  2. One comparison (i < items.length) in the control condition

  3. One comparison to see whether the control condition evaluates to true (i < items.length == true)

  4. One increment operation (i++)

  5. One array lookup (items[i])

  6. One function call (process(items[i]))

There’s a lot going on per iteration of these simple loops, even though there’s not much code. The speed at which the code will execute is largely determined by what process() does to each item, but even so, reducing the total number of operations per iteration can greatly improve the overall loop performance.

The first step in optimizing the amount of work in a loop is to minimize the number of object member and array item lookups. As discussed in Chapter 2, these take significantly longer to access in most browsers versus local variables or literal values. The previous examples do a property lookup for items.length each and every time through the loop. Doing so is wasteful, as this value won’t change during the execution of the loop and is therefore an unnecessary performance hit. You can improve the loop performance easily by doing the property lookup once, storing the value in a local variable, and then using that variable in the control condition:

//minimizing property lookups
for (var i=0, len=items.length; i < len; i++){

var j=0,
    count = items.length;
while (j < count){

var k=0,
    num = items.length;
do {
} while (k < num);

Each of these rewritten loops makes a single property lookup for the array length prior to the loop executing. This allows the control condition to be comprised solely of local variables and therefore run much faster. Depending on the length of the array, you can save around 25% off the total loop execution time in most browsers (and up to 50% in Internet Explorer).

You can also increase the performance of loops by reversing their order. Frequently, the order in which array items are processed is irrelevant to the task, and so starting at the last item and processing toward the first item is an acceptable alternative. Reversing loop order is a common performance optimization in programming languages but generally isn’t very well understood. In JavaScript, reversing a loop does result in a small performance improvement for loops, provided that you eliminate extra operations as a result:

//minimizing property lookups and reversing
for (var i=items.length; i--; ){

var j = items.length;
while (j--){

var k = items.length-1;
do {
} while (k--);

The loops in this example are reversed and combine the control condition with the decrement operation. Each control condition is now simply a comparison against zero. Control conditions are compared against the value true, and any nonzero number is automatically coerced to true, making zero the equivalent of false. Effectively, the control condition has been changed from two comparisons (is the iterator less than the total and is that equal to true?) to just a single comparison (is the value true?). Cutting down from two comparisons per iteration to one speeds up the loops even further. By reversing loops and minimizing property lookups, you can see execution times that are up to 50%–60% faster than the original.

As a comparison to the originals, here are the operations being performed per iteration for these loops:

  1. One comparison (i == true) in the control condition

  2. One decrement operation (i--)

  3. One array lookup (items[i])

  4. One function call (process(items[i]))

The new loop code has two fewer operations per iteration, which can lead to increasing performance gains as the number of iterations increases.


Decreasing the work done per iteration is most effective when the loop has a complexity of O(n). When the loop is more complex than O(n), it is advisable to focus your attention on decreasing the number of iterations.

Decreasing the number of iterations

Even the fastest code in a loop body will add up when iterated thousands of times. Additionally, there is a small amount of performance overhead associated with executing a loop body, which just adds to the overall execution time. Decreasing the number of iterations throughout the loop can therefore lead to greater performance gains. The most well known approach to limiting loop iterations is a pattern called Duff’s Device.

Duff’s Device is a technique of unrolling loop bodies so that each iteration actually does the job of many iterations. Jeff Greenberg is credited with the first published port of Duff’s Device to JavaScript from its original implementation in C. A typical implementation looks like this:

//credit: Jeff Greenberg
var iterations = Math.floor(items.length / 8),
    startAt    = items.length % 8,
    i          = 0;

do {
        case 0: process(items[i++]);
        case 7: process(items[i++]);
        case 6: process(items[i++]);
        case 5: process(items[i++]);
        case 4: process(items[i++]);
        case 3: process(items[i++]);
        case 2: process(items[i++]);
        case 1: process(items[i++]);
    startAt = 0;
} while (iterations--);

The basic idea behind this Duff’s Device implementation is that each trip through the loop is allowed a maximum of eight calls to process(). The number of iterations through the loop is determined by dividing the total number of items by eight. Because not all numbers are evenly divisible by eight, the startAt variable holds the remainder and indicates how many calls to process() will occur in the first trip through the loop. If there were 12 items, then the first trip through the loop would call process() 4 times, and then the second trip would call process() 8 times, for a total of two trips through the loop instead of 12.

A slightly faster version of this algorithm removes the switch statement and separates the remainder processing from the main processing:

//credit: Jeff Greenberg
var iterations = items.length % 8;
i	= items.length -1;


iterations = Math.floor(items.length / 8);


Even though this implementation is now two loops instead of one, it runs faster than the original by removing the switch statement from the loop body.

Whether or not it’s worthwhile to use Duff’s Device, either the original or the modified version, depends largely on the number of iterations you’re already doing. In cases where the loop iterations are less than 1,000, you’re likely to see only an insignificant amount of performance improvement over using a regular loop construct. As the number of iterations increases past 1,000, however, the efficacy of Duff’s Device increases significantly. At 500,000 iterations, for instance, the execution time is up to 70% less than a regular loop.

Function-Based Iteration

The fifth edition of ECMA-262 introduced a new method on the native array object called forEach(). This method iterates over the members of an array and runs a function on each. The function to be run on each item is passed into forEach() as an argument and will receive three arguments when called, which are the array item value, the index of the array item, and the array itself. The following is an example usage:

items.forEach(function(value, index, array){

The forEach() method is implemented natively in Firefox, Chrome, and Safari. Additionally, most JavaScript libraries have the logical equivalent:

//YUI 3
Y.Array.each(items, function(value, index, array){

jQuery.each(items, function(index, value){

dojo.forEach(items, function(value, index, array){

items.each(function(value, index){

$each(items, function(value, index){

Even though function-based iteration represents a more convenient method of iteration, it is also quite a bit slower than loop-based iteration. The slowdown can be accounted for by the overhead associated with an extra method being called on each array item. In all cases, function-based iteration takes up to eight times as long as loop-based iteration and therefore isn’t a suitable approach when execution time is a significant concern.

The best content for your career. Discover unlimited learning on demand for around $1/day.