Computing with JavaScript Web Workers


Web Workers are, undoubtedly, the coolest new feature to arrive in the latest version of web browsers. Web Workers allow you to run JavaScript in parallel on a web page, without blocking the user interface.

Normally in order to achieve any sort of computation using JavaScript you would need to break your jobs up into tiny chunks and split their execution apart using timers. This is both slow and unimpressive (since you can’t actually run anything in parallel – more information on this in How JavaScript Timers Work).

With our current situation in mind, let’s dig in to Web Workers.

Web Workers

The Web Worker recommendation is partially based off of the prior work done by the Gears team on their WorkerPool Module. The idea has since grown and been tweaked to become a full recommendation.

A ‘worker’ is a script that will be loaded and executed in the background. Web Workers provide a way to do this seamlessly, for example:

  1. new Worker("worker.js");

The above will load the script, located at ‘worker.js’, and execute it in the background.

There are some HUGE stipulations, though:

  1. Workers don’t have access to the DOM. No document, getElementById, etc. (The notable exceptions are setTimeout, setInterval, and XMLHttpRequest.)
  2. Workers don’t have direct access to the ‘parent’ page.

With these points in mind the big question should be: How do you actually use a worker and what is it useful for?

You use a worker by communicating with it using messages. All browsers support passing in a string message (Firefox 3.5 also supports passing in JSON-compatible objects). This message will be communicated to the worker (the worker can also communicate messages back to the parent page). This is the extent to which communication can occur.

The message passing is done using the postMessage API, working like this:

  1. var worker = new Worker("worker.js");
  2.  
  3. // Watch for messages from the worker
  4. worker.onmessage = function(e){
  5.   // The message from the client:
  6.   e.data
  7. };
  8.  
  9. worker.postMessage("start");

The Client:

  1. onmessage = function(e){
  2.   if ( e.data === "start" ) {
  3.     // Do some computation
  4.     done()
  5.   }
  6. };
  7.  
  8. function done(){
  9.   // Send back the results to the parent page
  10.   postMessage("done");
  11. }

This particular message-passing limitation is in place for a number of reasons: It keeps the child worker running securely (since it can’t, blatantly, affect a parent script) and it keeps the parent page thread-safe (having the DOM be thread safe would be a logistical nightmare for browser developers).

Right now Web Workers are implemented by Firefox 3.5 and Safari 4. They’ve also landed in the latest Chromium nightlies. Most people would balk when hearing this (only two released browsers!) but this shouldn’t be a concern. Workers allow you to take a normal piece of computation and highly parallelize it. In this way you can easily have two versions of a script (one that runs in older browsers and one that runs in a worker, if it’s available). Newer browsers will just run that much faster.

Some interesting demos have already been created that utilize this new API.

RayTracing

This demo makes use of Canvas to draw out a rendered scene. You’ll note that when you turn on the workers the scene is drawn in pieces. This is working by telling a worker to compute a slice of pixels. The worker responds with an array of colors to draw on the Canvas and the parent page changes the canvas. (Note that the worker itself doesn’t manipulate the canvas.)

Movement Tracking

(Requires Firefox 3.5. About the demo.) This one uses a number of technologies: The video element, the canvas element, and drawing video frames to a canvas. All of the motion detection it taking place in the background worker (so that the video rendering isn’t blocked).

Simulated Annealing

This demo attempts to draw outlines around a series of randomly-placed points using simulated annealing (More information). It also includes an animated PNG (works in Firefox 3.5) that continues to spin even while all the processing is occurring in the background.

Computing with JavaScript Web Workers

The other day Engine Yard started an interesting contest (which is probably over, by the time that you’re reading this).

The premise is that they would give you a phrase, which you would take the SHA1 of, and try to find another SHA1-ed string that has the smallest possible hamming distance from the original.

The phrase was posted the other day and developers have been furiously working to find a string that yields a low value.

The current leader is using a series of dedicated GPUs crunching out results at a pace of a couple hundred million per second. Considering the rate at which they’re progressing any other implementation will have a hard time catching up.

Of greater interest to me were two pure-JavaScript (1, 2) entrants into the competition – they both run completely in the browser and utilize the user’s JavaScript engine to find results. While neither of them have a prayer of overcoming the GPU-powered monsters dominating the pack, they do serve as an interesting realm for exploration.

Reading through the source to both implementations they both utilize nearly-identical tactics for computing results: They execute a batch of results broken up by a timer. I’ve played around with them in different browsers and have been able to get around 1000-1500 matches/second. Unfortunately they both peg the CPU pretty hard and even with the timer splitting they manage to bog down the user interface.

This sounds like a perfect opportunity to use Web Workers!

I took the Ray C Morgan implementation, stripped out all the UI components and timers, and pushed it in to worker (through which 4 of them are run in parallel). (I submit results back to the original implementation, just in case a good result is found.)

Check out the demo and source:

I ran the old implementation against the new one in the browsers that support Web Workers to arrive at the following results:

Browser Old Runs/s New Runs/s
Firefox 3.5 2700 4600
Safari 4 2500 8400
Chrome Nightly 4500 9600

How does this implementation work? Digging in to the source of the parent launcher we can see:

  1. // Build a worker
  2. var worker = new Worker("worker.js");
  3.  
  4. // Listen for incoming messages
  5. worker.onmessage = function(e){
  6.   var parts = e.data.split(" ");
  7.  
  8.   // We're getting the rate at which computations are done
  9.   if ( parts[0] === "rate" ) {
  10.     rates[i] = parseInt(parts[1]);
  11.  
  12.     // Total the rates from all the workers
  13.     var total = 0;    
  14.     for ( var j = 0; j < rates.length; j++ ) {
  15.       total += rates[j];      
  16.     }                
  17.     num.innerHTML = total;
  18.  
  19.   // We've found a new best score, send it to the server
  20.   } else if ( parts[0] === "found" ) {
  21.     var img = document.createElement("img");
  22.     img.src = "http://www.raycmorgan.com/new-best?phrase=" +
  23.       escape(parts.slice(1).join(" "));      
  24.     document.body.appendChild( img );
  25.  
  26.   // A new personal best score was found
  27.   } else if ( parts[0] === "mybest" ) {
  28.     var tmp = parseInt(parts[1]);
  29.     if ( tmp < mybest ) {
  30.       mybest = tmp;          
  31.       best.innerHTML = mybest;
  32.     }                
  33.   }          
  34. };    
  35.  
  36. // Start the worker
  37. worker.postMessage( data.sha + " " +
  38.   data.words.join(",") + " " + data.best );

To start, we’re constructing the worker and listening for any incoming messages. There are three types of messages that can come from the worker: “rate” (a ‘ping’ from the worker notifying the parent how quickly it’s running), “found” (sent back when a new high scoring phrase has been found by the client), and “mybest” (sent when the worker gets a new personal-best high score).

Additionally we can see the initialization data sent to the client in worker.postMessage. Unfortunately we have to pass the data in using a string in order to have it work in all browsers (only Firefox 3.5 supports the ability to pass in a raw JavaScript object).

Looking at the contents of the worker we can see some more, interesting, logic.

  1. // ... snip ...
  2.  
  3. // New Personal Best Found
  4. if (distance < myBest) {
  5.   myBest = distance;
  6.   postMessage("mybest " + myBest);
  7. }
  8.  
  9. // New All-time Best Found
  10. if (distance < best) {
  11.   best = distance;
  12.   postMessage("found " + phrase);
  13. }
  14.  
  15. // ... snip ...
  16.  
  17. // Report Rate Back to Parent
  18. function stats() {
  19.   var nowDiff = (new Date()).getTime() - startTime;
  20.   var perSec = Math.floor(processed/nowDiff*1000);
  21.   postMessage( "rate " + perSec );
  22. }
  23.  
  24. // ... snip ...
  25.  
  26. // Get the incoming information from the parent
  27. onmessage = function(e){
  28.   var parts = e.data.split(" ");
  29.   data = { sha: parts[0], words: parts[1].split(","), best: parts[2] };
  30.   start();
  31. };

The two ‘distance’ checks take place deep in the computation logic. After a new match has been found it is compared against the existing high scores. If this a sufficiently good-enough the result is sent back to the parent page using postMessage.

The ‘stats’ function is called periodically, which then reports back the current rate of processing to the parent page.

The ‘onmessage’ callback listens for the initialization data to come from the parent page – and once it’s been received begins processing.

In all I found this project to be a lot of fun – a relatively minor amount of code yielded 2-3x faster computation power. If you’re doing any computation with JavaScript you should definitely opt to use Web Workers if they’re available – the result is both faster and a better experience for the end user.

Posted: July 21st, 2009


If you particularly enjoy my work, I appreciate donations given with Gittip.

46 Comments (Show Comments)



Comments are closed.
Comments are automatically turned off two weeks after the original post. If you have a question concerning the content of this post, please feel free to contact me.


Secrets of the JavaScript Ninja

Secrets of the JS Ninja

Secret techniques of top JavaScript programmers. Published by Manning.

Ukiyo-e Database and Search

Ukiyo-e.org

Japanese woodblock print database and search engine.


John Resig Twitter Updates

@jeresig

Infrequent, short, updates and links.


via Ad Packs