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

Recursion

Complex algorithms are typically made easier by using recursion. In fact, there are some traditional algorithms that presume recursion as the implementation, such as a function to return factorials:

function factorial(n){
    if (n == 0){
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

The problem with recursive functions is that an ill-defined or missing terminal condition can lead to long execution times that freeze the user interface. Further, recursive functions are more likely to run into browser call stack size limits.

Call Stack Limits

The amount of recursion supported by JavaScript engines varies and is directly related to the size of the JavaScript call stack. With the exception of Internet Explorer, for which the call stack is related to available system memory, all other browsers have static call stack limits. The call stack size for the most recent browser versions is relatively high compared to older browsers (Safari 2, for instance, had a call stack size of 100). Figure 4-2 shows call stack sizes over the major browsers.

JavaScript call stack size in browsers

Figure 4-2. JavaScript call stack size in browsers

When you exceed the maximum call stack size by introducing too much recursion, the browser will error out with one of the following messages:

  • Internet Explorer: “Stack overflow at line x”

  • Firefox: “Too much recursion”

  • Safari: “Maximum call stack size exceeded”

  • Opera: “Abort (control stack overflow)”

Chrome is the only browser that doesn’t display a message to the user when the call stack size has been exceeded.

Perhaps the most interesting part of stack overflow errors is that they are actual JavaScript errors in some browsers, and can therefore be trapped using a try-catch statement. The exception type varies based on the browser being used. In Firefox, it’s an InternalError; in Safari and Chrome, it’s a RangeError; and Internet Explorer throws a generic Error type. (Opera doesn’t throw an error; it just stops the JavaScript engine.) This makes it possible to handle such errors right from JavaScript:

try {
    recurse();
} catch (ex){
    alert("Too much recursion!");
}

If left unhandled, these errors bubble up as any other error would (in Firefox, it ends up in the Firebug and error consoles; in Safari/Chrome it shows up in the JavaScript console), except in Internet Explorer. IE will not only display a JavaScript error, but will also display a dialog box that looks just like an alert with the stack overflow message.

Note

Even though it is possible to trap these errors in JavaScript, it is not recommended. No script should ever be deployed that has the potential to exceed the maximum call stack size.

Recursion Patterns

When you run into a call stack size limit, your first step should be to identify any instances of recursion in the code. To that end, there are two recursive patterns to be aware of. The first is the straightforward recursive pattern represented in the factorial() function shown earlier, when a function calls itself. The general pattern is as follows:

function recurse(){
    recurse();
}

recurse();

This pattern is typically easy to identify when errors occur. A second, subtler pattern involves two functions:

function first(){
    second();
}

function second(){
    first();
}

first();

In this recursion pattern, two functions each call the other, such that an infinite loop is formed. This is the more troubling pattern and a far more difficult one to identify in large code bases.

Most call stack errors are related to one of these two recursion patterns. A frequent cause of stack overflow is an incorrect terminal condition, so the first step after identifying the pattern is to validate the terminal condition. If the terminal condition is correct, then the algorithm contains too much recursion to safely be run in the browser and should be changed to use iteration, memoization, or both.

Iteration

Any algorithm that can be implemented using recursion can also be implemented using iteration. Iterative algorithms typically consist of several different loops performing different aspects of the process, and thus introduce their own performance issues. However, using optimized loops in place of long-running recursive functions can result in performance improvements due to the lower overhead of loops versus that of executing a function.

As an example, the merge sort algorithm is most frequently implemented using recursion. A simple JavaScript implementation of merge sort is as follows:

function merge(left, right){
    var result = [];

    while (left.length > 0 && right.length > 0){
        if (left[0] < right[0]){
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    return result.concat(left).concat(right);
}

function mergeSort(items){

    if (items.length == 1) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left    = items.slice(0, middle),
        right   = items.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}

The code for this merge sort is fairly simple and straightforward, but the mergeSort() function itself ends up getting called very frequently. Recursive functions are a very common cause of stack overflow errors in the browser.

Running into the stack overflow error doesn’t necessarily mean the entire algorithm has to change; it simply means that recursion isn’t the best implementation. The merge sort algorithm can also be implemented using iteration, such as:

//uses the same merge() function from previous example

function mergeSort(items){

    if (items.length == 1) {
        return items;
    }

    var work = [];
    for (var i=0, len=items.length; i < len; i++){
        work.push([items[i]]);
    }
    work.push([]);  //in case of odd number of items

    for (var lim=len; lim > 1; lim = Math.floor((lim+1)/2)){
        for (var j=0,k=0; k < lim; j++, k+=2){
            work[j] = merge(work[k], work[k+1]);
        }
        work[j] = [];  //in case of odd number of items
    }

    return work[0];
}

This implementation of mergeSort() does the same work as the previous one without using recursion. Although the iterative version of merge sort may be somewhat slower than the recursive option, it doesn’t have the same call stack impact as the recursive version. Switching recursive algorithms to iterative ones is just one of the options for avoiding stack overflow errors.

Memoization

Work avoidance is the best performance optimization technique. The less work your code has to do, the faster it executes. Along those lines, it also makes sense to avoid work repetition. Performing the same task multiple times is a waste of execution time. Memoization is an approach to avoid work repetition by caching previous calculations for later reuse, which makes memoization a useful technique for recursive algorithms.

When recursive functions are called multiple times during code execution, there tends to be a lot of work duplication. The factorial() function, introduced earlier in Recursion, is a great example of how work can be repeated multiple times by recursive functions. Consider the following code:

var fact6 = factorial(6);
var fact5 = factorial(5);
var fact4 = factorial(4);

This code produces three factorials and results in the factorial() function being called a total of 18 times. The worst part of this code is that all of the necessary work is completed on the first line. Since the factorial of 6 is equal to 6 multiplied by the factorial of 5, the factorial of 5 is being calculated twice. Even worse, the factorial of 4 is being calculated three times. It makes far more sense to save those calculations and reuse them instead of starting over anew with each function call.

You can rewrite the factorial() function to make use of memoization in the following way:

function memfactorial(n){

    if (!memfactorial.cache){
        memfactorial.cache = {
            "0": 1,
            "1": 1
        };
    }

    if (!memfactorial.cache.hasOwnProperty(n)){
        memfactorial.cache[n] = n * memfactorial(n-1);
    }

    return memfactorial.cache[n];
}

The key to this memoized version of the factorial function is the creation of a cache object. This object is stored on the function itself and is prepopulated with the two simplest factorials: 0 and 1. Before calculating a factorial, this cache is checked to see whether the calculation has already been performed. No cache value means the calculation must be done for the first time and the result stored in the cache for later usage. This function is used in the same manner as the original factorial() function:

var fact6 = memfactorial(6);
var fact5 = memfactorial(5);
var fact4 = memfactorial(4);

This code returns three different factorials but makes a total of eight calls to memfactorial(). Since all of the necessary calculations are completed on the first line, the next two lines need not perform any recursion because cached values are returned.

The memoization process may be slightly different for each recursive function, but generally the same pattern applies. To make memoizing a function easier, you can define a memoize() function that encapsulates the basic functionality. For example:

function memoize(fundamental, cache){
    cache = cache || {};

    var shell = function(arg){
        if (!cache.hasOwnProperty(arg)){
            cache[arg] = fundamental(arg);
        }
        return cache[arg];
    };

    return shell;
}

This memoize() function accepts two arguments: a function to memoize and an optional cache object. The cache object can be passed in if you’d like to prefill some values; otherwise a new cache object is created. A shell function is then created that wraps the original (fundamental) and ensures that a new result is calculated only if it has never previously been calculated. This shell function is returned so that you can call it directly, such as:

//memoize the factorial function
var memfactorial = memoize(factorial, { "0": 1, "1": 1 });

//call the new function
var fact6 = memfactorial(6);
var fact5 = memfactorial(5);
var fact4 = memfactorial(4);

Generic memoization of this type is less optimal than manually updating the algorithm for a given function because the memoize() function caches the result of a function call with specific arguments. Recursive calls, therefore, are saved only when the shell function is called multiple times with the same arguments. For this reason, it’s better to manually implement memoization in those functions that have significant performance issues rather than apply a generic memoization solution.

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