Timed array processing in JavaScript

Posted at August 11, 2009 09:00 am by Nicholas C. Zakas

Tags: JavaScript, Performance

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.

Disclaimer: Any viewpoints and opinions expressed in this article are those of Nicholas C. Zakas and do not, in any way, reflect those of my employer, my colleagues, Wrox Publishing, O'Reilly Publishing, or anyone else. I speak only for myself, not for them.

Both comments and pings are currently closed.

Related Posts

• The performance of localStorage revisited
• In defense of localStorage
• Timer resolution in browsers
• Script yielding with setImmediate
• Introduction to the Page Visibility API

Further reading

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

V1 on August 11th, 2009 at 9:20 am

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

james on August 11th, 2009 at 10:42 am

@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.

Nicholas C. Zakas on August 11th, 2009 at 12:39 pm

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!

Kyle Simpson on August 11th, 2009 at 12:49 pm

@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).

Nicholas C. Zakas on August 11th, 2009 at 6:29 pm

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.

Marcel Duran on August 12th, 2009 at 12:05 pm

@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.

Nicholas C. Zakas on August 12th, 2009 at 12:57 pm

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?

Marcel Duran on August 12th, 2009 at 1:45 pm

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.

Nicholas C. Zakas on August 13th, 2009 at 4:35 pm

[...] Posted on August 15th, 2009 in 前端开发 by lifesinger 灵感来自 Nicholas C. Zakas 的 Timed array processing in JavaScript. [...]

大数组的分时优化处理 - 岁月如歌 on August 15th, 2009 at 11:43 am

[...] “…”, acho que vale a pena tentar juntar esse código com a solução de “execução de Javascript com pausas“, proposta pelo Nicholas [...]

text-overflow para múltiplas linhas - Klaus Paiva on October 26th, 2009 at 2:04 pm

[...] www.nczonline.net/blog/2009/08/11/timed-array-processing-in-javascript/ [...]

浅析数组分时处理 - 漫步中的Tcer… on November 29th, 2009 at 5:45 am