The pattern discussed below is a well known pattern that has been used for 10 years. The goal of this article is to present this pattern under a new light, and most importantly to discuss ways of reducing its overhead.
The biggest deterrent for running CPU intensive computations in a web browser is the fact that the entire browser user interface is frozen while a JavaScript thread is running. This means that under no circumstance should a script ever take more than 300 msec (at most) to complete. Breaking this rule inevitably leads to bad user experience.
Furthermore, in web browsers, JavaScript threads have a limited amount of time to complete (there can be either a static time limit — that’s the case of Mozilla based browsers — or some other limit such as a maximum number of elementary operations — that’s the case of Internet Explorer) If a script takes too long to complete, the user is presented with a dialog asking whether that script should be terminated.
Google Gears provides the ability to run CPU intensive JavaScript code without the two aforementioned limitations. However, you cannot usually rely on the presence of Gears (in the future, I would like to see a solution like the Gears WorkerPool API as part of the standard browser API)
Fortunately, the setTimeout method of the global object allows us to execute code on a delay, giving the browser a chance to handle events and update the user interface, even if the timeout value passed to setTimeout is 0. This allows us to cut a long running process into smaller units of work, and chain them according to the following pattern:
function doSomething (callbackFn [, additional arguments]) {
// Initialize a few things here...
(function () {
// Do a little bit of work here...
if (termination condition) {
// We are done
callbackFn();
} else {
// Process next chunk
setTimeout(arguments.callee, 0);
}
})();
}
This pattern can also be slightly modified to accept a progress callback instead of a completion callback. This is especially useful when using a progress bar:
function doSomething (progressFn [, additional arguments]) {
// Initialize a few things here...
(function () {
// Do a little bit of work here...
if (continuation condition) {
// Inform the application of the progress
progressFn(value, total);
// Process next chunk
setTimeout(arguments.callee, 0);
}
})();
}
This example demonstrates the sorting of a fairly large array using this pattern.
Notes:
- This pattern has a lot of overhead i.e. the total amount of time required to complete a task can be far greater than the time it would take to run the same task uninterrupted.
- The shorter each cycle, the greater the overhead, the more reactive the user interface, the greater the overall time required to complete the task.
- If you can be sure that each iteration of your algorithm is of very short duration — say 10 msec, you may want to group several iterations within a single cycle to reduce the overhead. The decision whether to start the next cycle or continue with more iterations can be made based on how long the current cycle has been running. This example demonstrates this technique. Although it uses the same sorting algorithm as the example above, notice how much faster it is, while still keeping the user interface perfectly reactive.
- Never pass a string to
setTimeout! If you do, the browser needs to do an implicitevalevery time the code is executed, which adds an incredible amount of completely unnecessary overhead. - If you manipulate global data, make sure that access to that data is synchronized since it could also be modified by another JavaScript thread running between two cycles of your task.
Finally, consider running this kind of task on the server (though you’ll have to deal with serialization / deserialization and network latency, especially if the data set is large) Having to run CPU intensive computations on the client might be a sign of a deeper, more serious architectural problem with your application.
