Timed array processing in JavaScript

Not too long ago, I blogged about a way to asynchronously process JavaScript arrays to avoid locking up the browser (and further, to avoid displaying the long-running script dialog). The chunk() function referenced in that original blog post is as follows:

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

This method was an example implementation and has a couple of performance issues. First, the size of the delay is too long for large arrays. Using a 100 millisecond delay on an array of 100 items means that processing takes at least 10,000 milliseconds or 10 seconds. The delay should really be decreased to 25 milliseconds. This is the minimum delay that I recommend to avoid browser timer resolution issues. Internet Explorer’s timer resolution is 15 milliseconds, so specifying 15 milliseconds will be either 0 or 15, depending on when the system time was set last. You really don’t want 0 because this doesn’t given enough time for UI updates before the next batch of JavaScript code begins processing. Specifying a delay of 25 milliseconds gives you a guarantee of at least a 15 millisecond delay and a maximum of 30.

Still, with a delay of 25 milliseconds, processing of an array with 100 items will take at least 2,500 milliseconds or 2.5 seconds, still pretty long. In reality, the whole point of chunk() is to ensure that you don’t hit the long-running script limit. The problem is that the long-running script limit kicks in well after the point at which the user has experienced the UI as frozen.

Room for improvement

Jakob Nielsen stated in his paper, Response Times: The Three Important Limits, that 0.1 seconds (100 milliseconds) is “is about the limit for having the user feel that the system is reacting instantaneously, meaning that no special feedback is necessary except to display the result.” Since the UI cannot be updated while JavaScript is executing, that means your JavaScript code should never take more than 100 milliseconds to execute continuously. This limit is much smaller than the long-running script limit in web browsers.

I’d actually take this one step further and say that no script should run continuously for more than 50 milliseconds. Above that, you’re trending close to the limit and could inadvertently affect the user experience. I’ve found 50 milliseconds to be enough time for most JavaScript operations and a good cut-off point when code is taking too long to execute.

Using this knowledge, you can create a better version of the chunk() function:

//Copyright 2009 Nicholas C. Zakas. All rights reserved.
//MIT Licensed
function timedChunk(items, process, context, callback){
    var todo = items.concat();   //create a clone of the original

    setTimeout(function(){

        var start = +new Date();

        do {
             process.call(context, todo.shift());
        } while (todo.length > 0 && (+new Date() - start < 50));

        if (todo.length > 0){
            setTimeout(arguments.callee, 25);
        } else {
            callback(items);
        }
    }, 25);
}

This new version of the function inserts a do-while loop that will continuously process items until there are no further items to process or until the code has been executing for 50 milliseconds. Once that loop is complete, the logic is exactly the same: create a new timer if there’s more items to process. The addition of a callback function allows notification when all items have been processed.

I set up a test to compare these two methods as they processed an array with 500 items and the results are overwhelming: timedChunk() frequently takes less than 10% of the time of chunk() to completely process all of the items. Try it for yourself. Note that neither process causes the browser to appear frozen or locked up.

Conclusion

Even though the original chunk() method was useful for processing small arrays, it has a performance impact when dealing with large arrays due to the extraordinary amount of time it takes to completely process the array. The new timedChunk() method is better suited for processing large arrays in the smallest amount of time without affecting the user experience.

Comments

  1. V1

    Interesting, I see good use of that script for filtering arrays (datasets)

  2. james

    Do you think it's worth detecting support of Web Workers and using them if they're available? Just a thought...

  3. Nicholas C. Zakas

    @James - You could fork if Web Workers were available, but since they're not terribly ubiquitous at this point, my preference is to have a single solution that works in all browsers.

  4. Kyle Simpson

    I wonder (and suppose) that this technique can be used for more effective sorting of client-side data sets.... for instance, if you used some sort of heap-sort type approach, and could quickly come up with the top "chunk" (10-20 items) that are sorted... and display that nearly immediately, and then async let the rest of the list sort itself in the background and update as it finishes.

    Cool technique, thanks for sharing!

  5. Nicholas C. Zakas

    @Kyle - You can definitely use this to help with client-side sorting of large data sets. You really just need an algorithm where the intermediate state is easily tracked, such as heap sort or even the lowly bubble sort (check the time after each pass through).

  6. Marcel Duran

    Concerning this arbitrary 25ms for setTimeout delay, what about the 10ms you presented in your chapter on Even Faster Web Sites in the adaptation of Julien Lecomte's bubble-sort example? In his original post, he's using 0ms for the setTimeout delay and even though it works properly.

  7. Nicholas C. Zakas

    @Marcel - I don't believe "arbitrary" is the correct word, I explained the reasoning for this in the second paragraph of this post. Since writing the chapter for Even Faster Web Sites, I've done further testing that shows values in the range of 0-15 have the ability to freeze Internet Explorer when done in succession, that is why I now recommend 25ms as the delay when there will be multiple timers created.

  8. Marcel Duran

    I see. Does it mean that even a simple code like:

    var begin, end, delay = 10,
    func = function () {
    end = new Date();
    alert(end - begin);
    };
    begin = new Date();
    setTimeout(func, delay);

    will always take at least 15ms to execute on Internet Explorer? Or only in successive calls? What about other browsers? Could they handle delays < 15ms?

  9. Nicholas C. Zakas

    It's a crapshoot, you'll either get 0 or 15. Most browsers are accurate down to 10ms but start to get weird after that. Chrome is accurate to much smaller delays.

Understanding JavaScript Promises E-book Cover

Demystify JavaScript promises with the e-book that explains not just concepts, but also real-world uses of promises.

Download the Free E-book!

The community edition of Understanding JavaScript Promises is a free download that arrives in minutes.