想看一篇文章，有能上外网的兄弟帮忙转过来看下，给分的哦

Speed up your JavaScript, Part 1
Posted at January 13, 2009 09:00 am by Nicholas C. Zakas
Tags: Arrays, JavaScript, Long-Running Script, Performance
In my last post, I talked about the conditions under which the dreaded long-running script dialog is displayed in browsers. Browsers will stop executing script either when they’ve executed too many statements (Internet Explorer) or when the JavaScript engine has been running for a specific amount of time (others). The problem, of course, isn’t the way that the browser is detecting long-running scripts, it’s that the script is taking too long to execute.There are four main reasons why a script can take too long to execute:Too much happening in a loop.
Too much happening in a function.
Too much recursion.
Too much DOM interaction.
In this post, I’m going to focus on the first issue: too much happening in a loop. Loop iterations happen synchronously, so the amount of time it takes to fully execute the loop is directly related to the number of iterations. There are, therefore, two situations that cause loops to run too long and lock up the browser. The first is that the loop body is doing too much for each iteration and the second is that the loop is running too many times. These can cause the browser to lock up and display the long-running script warning.The secret to unraveling this problem is to evaluate the loop to answer two questions:Does the loop have to execute synchronously?
Does the order in which the loop’s data is processed matter?
If the answer to both of these questions is “no,” then you have some options for splitting up the work done in the loop. The key is to examine the code closely to answer these questions. A typical loop looks like this:for(var i=0; i < items.length; i++){
    process(items[i]);
}
This doesn’t look too bad though may take very long depending on the amount of time necessary to run the process() function. If there’s no code immediately after the loop that depends on the results of the loop executing, then the answer to the first question is “no.” You can clearly see that each iteration through the loop isn’t dependent on the previous iteration because it’s just dealing with one value at a time, so the answer to the second question is “no.” That means the loop can be split in a way that can free up the browser and avoid long-running script warnings.In Professional JavaScript, Second Edition, I introduce the following function as a way to deal with loops that may take a significant amount of time to execute:function chunk(array, process, context){
    setTimeout(function(){
        var item = array.shift();
        process.call(context, item);        if (array.length > 0){
            setTimeout(arguments.callee, 100);
        }
    }, 100);
}
The chunk() function is designed to process an array in small chunks (hence the name), and accepts three arguments: a “to do” list of items, the function to process each item, and an optional context variable for setting the value of this within the process() function. A timer is used to delay the processing of each item (100ms in this case, but feel free to alter for your specific use). Each time through, the first item in the array is removed and passed to the process() function. If there’s still items left to process, another timer is used to repeat the process. The loop described earlier can be rewritten to use this function:chunk(items, process);
Note that the array is used as a queue and so is changed each time through the loop. If you want to maintain the array’s original state, there are two options. First, you can use the concat() method to clone the array before passing it into the function:chunk(items.concat(), process);
The second option is to change the chunk() function to do this automatically:function chunk(array, process, context){
    var items = array.concat();   //clone the array
    setTimeout(function(){
        var item = items.shift();
        process.call(context, item);        if (items.length > 0){
            setTimeout(arguments.callee, 100);
        }
    }, 100);
}
Note that this approach is safer than just saving an index and moving through the exist array, since the contents of the array that was passed in may change before the next timer is run.The chunk() method presented here is just a starting point for how to deal with loop performance. You can certainly change it to provide more features, for instance, a callback method to execute when all items have been processed. Regardless of the changes you may or may not need to make to the function, it is a general pattern that can help optimize array processing to avoid long-running script warnings.
Last week, I covered the first reason why JavaScript can take too long to execute: too much happening in a loop. There’s a similar problem with functions in that sometimes they’re just doing too much. Usually this means there’s too many loops (as opposed to too much happening in a loop), too much recursion, or simply too many different operations being performed.Too many loops are often caused by having loops inside of loops, locking up the JavaScript engine until all iterations are complete. The most glaring example of this is the bubble sort algorithm. Though there’s no need to use this in JavaScript due to the native sort() method, it’s good to understand how it can be problematic so that you can identify similar patterns. A typical implementation of a bubble sort in JavaScript looks like this:function bubbleSort(items){
    for (var i=items.length-1; i >= 0; i--){
        for (var j=items.length-i; j >= 0; j--){
            if (items[j] < items[j-1]){
                var temp = items[j];
                items[j] = items[j-1];
                items[j-1] = temp;
            }
        }
    }
}
Thinking back to your computer science days, you’ll probably remember that bubble sort is one of the least efficient sorting algorithms. The problem is for every n items in the array, there must be n2 loop iterations. This processing can take forever if there’s a large amount of array items. The comparison and swap operation done during the inner loop is actually quite simple, it’s just the number of times that it’s repeated in sequence that causes the problem. This can cause the browser to grind to a halt and, potentially, result in the long-running script dialog.A couple years ago, fellow Yahoo Julien Lecomte wrote a post entitled,
Running CPU Intensive JavaScript Computations in a Web Browser, in which he described how to break up large JavaScript operations into several parts. One of his clearest examples was refactoring a bubble sort into multiple steps, each of which executes a single trip through the array. I’ve augmented his code somewhat, but the approach remains the same:function bubbleSort(array, onComplete){    var pos = 0;    (function(){
        var j, value;        for (j=array.length; j > pos; j--){
            if (array[j] < array[j-1]){
                value = data[j];
                data[j] = data[j-1];
                data[j-1] = value;
            }
        }        pos++;        if (pos < array.length){
            setTimeout(arguments.callee,10);
        } else {
            onComplete();
        }
    })();
}
This function performs a bubble sort in an asynchronous manner, stopping after each trip through the array before continuing on to the next leg. The onComplete() function is called when the array is completely sorted as notification that the data is ready. The bubbleSort() function uses the same basic technique as the chunk() function presented in my last post: use an anonymous function to wrap the behavior and then pass arguments.callee into setTimeout() to repeat the process until complete. This function is a good example of how you can split up embedded loops into a series of steps to free up the browser.A similar problem is too much recursion. Each additional recursive call takes up memory, and eventually will slow down the browser. The annoying thing is that you may reach a memory limit before the long-running script dialog pops up and leave the browser in an unusable state. Crockford had a good discussion about this in his latest talk. The example he uses is a function that generates a Fibonacci sequence:function fibonacci (n) {
    return n < 2 ? n :
            fibonacci(n - 1) +
            fibonacci(n - 2);
};
As Crockford points out, a call to fibonacci(40) results in 331,160,280 calls to itself. The solution to avoid too much recursion is to use memoization, a technique for caching previously-calculated values. Crockford introduces the following memoization function that can be used to create memoized versions of functions dealing with numbers:function memoizer(memo, fundamental) {
    var shell = function (n) {
        var result = memo[n];
        if (typeof result !== 'number') {
            result = fundamental(shell, n);
            memo[n] = result;
        }
        return result;
    };
    return shell;
};
He then applies this to the Fibonacci sequence generator:var fibonacci =
    memoizer([0, 1], function (recur, n) {
       return recur(n - 1) + recur(n - 2);
    });
Calling fibonacci(40) using this code results in only 40 calls to the function, a vast improvement over the original. The overall lesson from memoization is that you should never calculate the same result twice; if there’s a value you’ll need more than once, store it for later use rather than running the code to generate it again.The final thing that causes functions to execute slowly is, as mentioned previously, that it’s just doing too much. Usually it’s because of a pattern such as this:function doAlot(){
    doSomething();
    doSomethingElse();
    doOneMoreThing();
}
Here, there’s three clearly distinct pieces of code that are being executed. The important thing to notice is that none of the functions rely on the other functions to complete their task; they are essentially independent of one another and just need to happen in sequence at a given point in time. In situations like this, you can use a variant of the chunk() method to execute a series of functions in a row without holding up the browser:
function schedule(functions, context){
    setTimeout(function(){
        var process = functions.shift();
        process.call(context);        if (functions.length > 0){
            setTimeout(arguments.callee, 100);
        }
    }, 100);
}
The schedule function accepts two arguments, an array of functions to execute and a context object indicating the value of this inside of each function. The functions array acts as a queue, with the topmost function being removed and executed each time the timer is executed. This function can be used to execute a series of functions in a row like this:schedule([doSomething, doSomethingElse, doOneMoreThing], window);
I’m expecting that JavaScript libraries will soon start including more processing functions such as this. YUI has already added the Queue object in version 3.0 that helps to manage the running of several functions in a row using a timer.Regardless of the tools available to help split up complex processes, it’s still vital for developers to be able to understand and identify bottlenecks that will benefit from using this approach. Whether there be too many loops, too much recursion, or just plain too much going on, you now know how to deal with each. Remember, the techniques and functions presented here are just a starting point and not a golden bullet, you should (and will likely have to) modify the code presented so that it works for your specific usage.Update (1/20): Fixed copy/paste error in schedule() function.
Recursion is the enemy of fast-running scripts. Too much recursion can cause the browser to grind to a halt or quit unexpectedly, and so must be addressed a serious performance problem in JavaScript. In part 2 of this series, I wrote briefly about handling too much recursion in a function through memoization. Memoization is a technique for caching previously calculated values so that they need not be recalculated; when a recursive function is doing such a calculation, memoization is incredibly useful. The memoizer I presented was Crockford’s, and is useful primarily for recursive functions that return integers. All recursive functions, of course, don’t return integers. A more generic memoizer() function can be created to deal with any type of recursive function:function memoizer(fundamental, cache){
    cache = cache || {}
    var shell = function(arg){
        if (!cache.hasOwnProperty(arg)){
            cache[arg] = fundamental(shell, arg)
        }
        return cache[arg];
    };
    return shell;
}
This version of the function is a bit different than Crockford’s. First, the order of arguments has been reversed with the original function as the first argument and an optional cache object as the second argument. Not all recursive functions are seeded with initial information, so making that argument optional makes sense. Inside, I’ve changed the caching data type from an array to an object, which makes this version applicable to recursive functions that return non-integer results. Inside the shell function, I’m using the hasOwnProperty() method to see if the argument already has a cache entry. This is safer than testing if the type of value isn’t undefined since undefined is a valid return value. Example usage with the previous Fibonacci example:var fibonacci =
    memoizer(function (recur, n) {
       return recur(n - 1) + recur(n - 2);
    }, {"0":0, "1":1});
Once again, a call to fibonacci(40) results in only 40 calls of the original function instead of 331,160,280. Memoization works great for recursive algorithms with a strictly defined result set. There are, however, other recursive algorithms that don’t lend themselves to optimization through memoization.One of my professors in college insisted that anything written using recursion could also be written using iteration if necessary. Indeed, recursion and iteration are often considered remedies for one another when one is seen as a problem. The techniques for converting a recursive algorithm into an iterative algorithm are the same regardless of the programming language; the importance in JavaScript is greater, though, because the resources of the execution environment are so restrictive. Consider a typical recursive algorithm such as a merge sort. In JavaScript, it may be written like this: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);
}//recursive merge sort algorithm
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));
}
Calling the mergeSort() function on an array returns an array of the items sorted in correct order. Note that for each call to mergeSort() there are two recursive calls. This algorithm won’t benefit from memoization because each result is only calculated once and, therefore, caching the results doesn’t help. If you were to call mergeSort() on an array with 100 items, there would be 199 calls total; a 1,000 item array would result in 1,999 calls. The solution in this case is to convert the recursive algorithm into an iterative one, which means introducing some loops (algorithm credit: List Processing: Sort Again, Naturally)://iterative merge sort algorithm
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 = (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 the merge sort algorithm uses a series of loops instead of recursion to sort the array. Since merge sort works by first breaking down an array into several one-item arrays, this method does that explicitly instead of implicitly via recursive calls. The work array is initially an array of one-item arrays. The loops enable the merging of two arrays at a time, placing the result back into the work array. When the function has done its job, the result is stored in the first position of work and is returned. In this version of merge sort, there is no recursion. It does, however, introduce a large number of loops based on the number of items in the array, so it may be worth revisiting the techniques discussed in part 2 to handle the extra overhead.The bottom line: always be on the look out for recursion in your JavaScript. Memoization and iteration are two ways to avoid excessive recursion and the long-running script dialog.

调试易

想看一篇文章，有能上外网的兄弟帮忙转过来看下，给分的哦

解决方案 »