Computing with JavaScript Web Workers

July 21st, 2009

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:

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:

The Client:

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:

• SHA1-Crunching Web Worker Demo
• 'Parent' Source
• Worker Source

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

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

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.

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.

Tags: workers, javascript

46 Comments on 'Computing with JavaScript Web Workers'

Easy Retweet Button

July 9th, 2009

Ever since I saw the Bit.ly JavaScript API I've been wanting to build a simple script for tracking the number of people visiting a blog post from Twitter. This past weekend I built a little script for doing just that - and in a completely unobtrusive manner.

The script itself is completely standalone (no dependencies) and can be included in any page relatively painlessly. Additionally, since it's just HTML, CSS, and JavaScript, it's completely themeable and customizable to the style of your site. Before explaining how to use it, some demos:

Demos

Simple Style

Vertical Style

How to Use / Installation

Getting the Easy Retweet Button running on your site is painfully easy (ha!).

Step 1: Include the retweet.js file in the <head> of your web site.

(Note: You should place and use a copy from your own site, in case mine ever goes down.)

(Note 2: You DO NOT need a bit.ly account in order to use this script. A working one is provided for you by default.)

Step 2: Add a class of 'retweet' to any anchor that you wish to turn into a Retweet button - or add a link with classes of 'retweet' and 'self' to add a retweet button for the current page.

Retweet link for the current page: (See example at the end of this blog post.)

Retweet link for other page:

Wordpress: If you're using Wordpress you could sculpt a custom button like so, placed in your single.php theme file (although, the above link types should be more than sufficient for most cases):

The script has been tested in Internet Explorer 6-8, Opera 9-10, Safari 3.2-4, Chrome 2, and Firefox 3-3.5. Please write a comment if you encounter any problems.

Configuration and Themeing

There are a few options for the Retweet button that you can use. If you're going to change them you can do so by changing the following properties after you've already loaded the retweet.js file. However, I highly recommend that you download a copy of the retweet.js file, make the changes in the file itself, and simply load that result instead.

RetweetJS.link_text (Default: "Retweet")

You can change this to another value and change the text in all of the Retweet buttons. (Good for handling different languages.)

RetweetJS.count_text (Default: "clicks")

Right now only "clicks" are supported but if you specify "none" it will show no count (and load much faster, as a result).

RetweetJS.prefix (Default: "")

Setting to "RT @jeresig " will add it to the front of the tweets.

RetweetJS.styling (Default: The full CSS used for styling the retweet button.)

You'll probably want to either tweak the CSS from inside the file itself or completely overwrite it and include your own styling elsewhere. The markup for the button is surprisingly simple:

And if you have a vertical-style button the markup is:

RetweetJS.bitly_user
RetweetJS.bitly_key

These default to a dummy account ('retweetjs') that can be used indefinitely. However if you wish to keep track of your own links and add them to your own Bit.ly account then please add in your Bit.ly username and API key (which can be found on your Bit.ly account page). These values should be changed within the retweet.js file itself.

Alternatives

Two alternatives that I know about are the Tweetmeme Button and the Backtype Tweetcount.

Some of the major differences between this script and those are:

• Completely Unobtrusive You can place the script in the <head> of your document instead of inline. The other scripts rely upon document.write() and write out iframes into your document.
• Speed Retweet.js works completely asynchronously, loading data and updating the rendering as it comes in. This means that the buttons won't block your page while they're loading (unlike the other buttons).
• Pure HTML/CSS The result is just pure HTML styled with CSS - you can customize it however you wish, no images are required.
• Number of clicks, not retweets. The number of retweets may be interesting to some but it's a poor indicator of actual traffic. Instead, the number of clicks coming in is shown instead (a much more useful number).
• You control the data All tracking works directly through Bit.ly, not a third party - this means that all the clicks and traffic can be stored straight in your bit.ly account, not some third parties.
• 100% Open Source This script is released under the MIT license and is completely open to modification and redistribution. The full source is available on Github.

If you have any questions regarding the script please feel free to post them her in the comments. If you have any tweaks for the script, please apply them against the source repository. Enjoy!

Tags: javascript, twitter

44 Comments on 'Easy Retweet Button'

JavaScript Function Call Profiling

February 23rd, 2009

With jQuery 1.3.2 out the door I've been looking for more ways to profile and optimize jQuery.

Previously I did a survey of jQuery-using sites to figure out which selectors they were using. This led to the construction of the new Sizzle Selector Engine which targeted those selectors for improvement.

Additionally, I constructed a deep profiling plugin for jQuery which helped to spot methods that were taking a long time to run in live jQuery sites. This helped bring about the improvements in jQuery 1.2.6, 1.3, and 1.3.2.

What do we tackle next? A good place to start would be to tackle optimizing methods that are obviously inefficient - but how do we determine that? One way would be to measure the number of function calls that occur every time a method is run. Firebug provides this information in its profiling data (along with how long it takes to run each method). Unfortunately it's very clunky to manually type out code, check the results in the console, and determine if they're bad or if they've changed. If only there was a way to progamatically get at those numbers.

FireUnit Profiling Methods

Yesterday I did some work to make getting at the profiling data possible, adding two new methods to FireUnit.

fireunit.getProfile();

Run this method after you've run console.profile(); and console.profileEnd(); to get a full dump of the profiling information. For example, given the following profile run:

You'll get the following JavaScript object returned from fireunit.getProfile():

fireunit.profile( fn );

The second method added to FireUnit provides an easy way to execute and profile a single function. Roughly, this method starts the profiler, executes the function, stops the profiler, and then returns the results from getProfile(). Additionally, it watches for any exceptions that might be thrown and makes sure that the profiler is cleanly turned off anyway (a frequent frustration of mine).

You would use it like this:

How To Use

First, you'll need to be sure to have the latest copy of FireUnit installed. I've built a copy of the latest code, into an extension, if you wish to install it:

• http://fireunit.org/fireunit-1.0a1.xpi

When running it you'll need to make sure that:

1. Both the Console and Script tabs are enabled in Firebug
2. That the 'extensions.firebug.throttleMessages' property in 'about:config' is set to 'false'.

The Results

I put up a test page so that I could quickly run through some jQuery methods to see how they stacked up.

Here are the results of running against jQuery 1.3.2 ("Method" is the jQuery method that was called, with the specified arguments, "Calls" is the number of function calls that occurred when executing the method, "Big-O" is a very rough Big-O Notation for the function calls):

We can immediately see, by looking at the big-O notation, that most jQuery methods execute at least one function for every element that they have to operate against. addClass runs about 6 functions per element, filter runs about 2, and 'is' runs only 1.

We can see the problematic functions sticking out like a massive sore thumb: .remove(), .empty(), and .html() - they all run over n² function calls, which is a huge issue. (These numbers are all large for a simple reason: .html() uses .empty(), .empty() uses .remove(), and .remove() is obviously inefficient.) While function calls do not, necessarily, indicate slow code (a lot of jQuery's internal functions are pretty lightweight) it is very likely to indicate inefficiently-written code.

I poked around the code for a little bit and realized that .remove() could be dramatically simplified. I filed a ticket and landed a patch which resulted in these much-improved numbers:

I'm really excited by this new tool. Automating the process of code profiling opens up whole avenues of exploration. Even using nothing more than the above tool I can immediately see room for improving just about every jQuery method.

It's also be very interesting to have this running in some sort of continuous integration setting, to catch any egregious regressions - but I'll leave that for another day.

Tags: fireunit, firebug, javascript, jquery

46 Comments on 'JavaScript Function Call Profiling'

FireUnit: JavaScript Unit Testing Extension

December 18th, 2008

In my work with the Firebug team over the past couple months I've been working with Jan Odvarko on a way to provide some form of unit testing that we can build off of. The result of my work is a new Firefox/Firebug extension called FireUnit.

FireUnit provides a simple JavaScript API for doing simple test logging and viewing within a new tab of Firebug.

For example, here's some of the API that you can use (we're starting with the basics and looking to expand with more methods, later).

The results will appear in a 'Test' tab in Firebug (which must be installed in order for Fireunit to work). Each of the results can be expanded to show additional information including a full stack trace of where the test ran and a comparison with a diff.

FireUnit also provides a couple methods for simulating native browser events:

And a way of running a batch of test files (each of which would contain a number of individual tests).

We've been using this test runner to run a number of Firebug tests, especially ones that are network based.

Depending on the suite it's pretty easy to adapt existing test suites to display their results in FireUnit.

Running the jQuery selector test suite that has the following snippet added:

Yields the following results (which are completely navigable):

If you want to get started using FireUnit you can head on over to the Fireunit.org site and download the latest extension.

You can also grab the source off of the repository on Github.

Jan has also written a blog post detailing a little bit more about what we're using FireUnit for in the Firebug Working Group.

This is still a very early release of our work - there's obviously a ton of room left to grow - so feedback is expected and appreciated.

Tags: extension, firefox, firebug, javascript, testing

44 Comments on 'FireUnit: JavaScript Unit Testing Extension'

Ultra-Chaining with jQuery

October 14th, 2008

We were having a discussion, the other day, on the jQuery-dev mailing list concerning style and jQuery code. There was some discussion about how it could be improved.

One of the points discussed was concerning the use of callbacks and jQuery(this). Callbacks (passing in a function as the final argument to a jQuery method, to be called later) are used all throughout jQuery code. It's a rather core aspect of jQuery (especially the use of closures to pass around information).

We began to wonder: What would jQuery look like if there were no callbacks? A couple solutions were proposed but I posited one that, I think, promotes the idioms present in jQuery.

Its use is simple (although its implementation is definitely a mind-twister). Instead of using a callback you now using jQuery chaining to execute all the methods that you need.

Where previously you would've done:

You would now write:

The end result is quite interesting. It definitely moves jQuery farther into the land of a "Domain Specific Language." I wanted to put this code out there for people to try out and play with even though I have a number of reservations:

1. I'm really not a fan of passing in a method name as a string argument, to another method. This is used a lot in Prototype.js but it just never sat right with me.
2. The .chain() method name probably isn't right. Some other name probably fits better here.
3. The fact that you lose out on the power of normal JavaScript is daunting (you can no longer do something like: jQuery(this).html( jQuery(this).attr("href") ) - you'd have to go back to using a callback).

Nevertheless I think the result holds a lot of potential even if just as a proof-of-concept.

Tags: javascript, jquery

49 Comments on 'Ultra-Chaining with jQuery'

Degrading Script Tags

August 26th, 2008

One thing has always annoyed me about the script tag. Script tags that reference external resources (via the src attribute) are no longer able to execute script embedded within the tag itself.

It doesn't make sense to me that we're forced to write:

when this is so much more elegant:

Only one tag - and the semantics would work like this: The external script would attempt to be loaded (as normal). If the load and execution was error-free then the internal script would be executed as well. If the load or execution failed then the internal script would not be executed (this being the important distinction from the first example, shown above).

We can verify these two facts with some tests:

1. Test 1: Verify that internal scripts aren't executed, even if an external src is loaded.
2. Test 2: Verify that internal scripts aren't executed, even if an external src is not loaded.

Running the tests in Firefox, Opera, Safari, and IE show them all passing (the internal scripts are unable to execute).

With this knowledge in place now, let's get to the juicy part: How do we actually implement the above style of script-tag-writing in a way that melds well with our desired style of development?

It's actually terribly simple. I took a copy of jQuery and tacked the following two lines on to the end of the script:

Taking a look at a demo shows it working, using only one script tag:

We have succeeded! but how does the above code work? The short snippet takes advantage of the way in which script tags are loaded and executed. Each script tag within a page may be downloaded in any order (for example, Internet Explorer 8 and Firefox 3.1 are starting to download many scripts in parallel). BUT their execution must come in order AND they must be executed in their exact place in the DOM.

This means that when the script finally executes that it'll be the last script in the DOM - and even the last element in the DOM (the rest of the DOM is built incrementally as it hits more script tags, or until the end of the document).

This particular behavior occurs because scripts are able to document.write, affecting the very nature of the document. The following is perfectly legal (even if you can imagine the trauma that it must cause browser vendors - preventing them from performing some perfectly good optimizations):

<script>document.write('<' + '!--');</script>
<script src='some_external_script.js'></script>
<script>document.write('-->');</script>

With the above taken in mind - let's consider a further optimization to our code. While the above code snippet is generic to any external source file, what if we were to take advantage of the nature of jQuery, simplifying its behavior?

Virtually all jQuery-using code is encased within a call to the document ready function (which delays execution of attached handlers until the DOM is full loaded).

If we were to make some adjustments to our script addition, like so:

We can now get the full advantage of having our scripts inline and not having to write out a document ready call, like so:

Pretty sexy, huh?

The only thing holding me back from blindly adding the above snippet directly in to jQuery, today, is a small possibility: The chance that someone could copy the full library and stick it in an embedded script tag (rather than calling it from an external file).

Right now if you were to stick either of the above snippets in an embedded script tag you would end up with a never-ending loop. Consider this code:

This code would look for the last script on the page, find it (it would be the script itself), and execute - causing a piece of recursion to occur. It would become necessary to flag the script to prevent it from executing again.

With a little bit of extra work, we can make it possible (demo):

I think this particular technique could serve to simplify a number of web pages, even if it's only because:

1. There's one less script tag on the page.
2. The dependency link between the script being loaded and the script being executed becomes exceedingly obvious.
3. The dependent script won't execute (and subsequently cause errors) if the external script is unable to load.
4. The need for user-authored window load, document ready, etc. functions are no longer necessary (can be hidden within the library).

It's definitely something that'll need to be mulled over as it's pretty fundamentally changing the existing behavior of the script tag (although, it is being done in a completely safe and backwards-compatible manner). But if there's sufficient interest it seems as if this is one area in which external scripts could stand to offer an obvious improvement to the developer.

Tags: javascript, html

53 Comments on 'Degrading Script Tags'

JavaScript Micro-Templating

July 16th, 2008

I've had a little utility that I've been kicking around for some time now that I've found to be quite useful in my JavaScript application-building endeavors. It's a super-simple templating function that is fast, caches quickly, and is easy to use. I have a couple tricks that I use to make it real fun to mess with.

Here's the source code to the templating function (a more-refined version of this code will be in my upcoming book Secrets of the JavaScript Ninja):

You would use it against templates written like this (it doesn't have to be in this particular manner - but it's a style that I enjoy):

You can also inline script:

Quick tip: Embedding scripts in your page that have a unknown content-type (such is the case here - the browser doesn't know how to execute a text/html script) are simply ignored by the browser - and by search engines and screenreaders. It's a perfect cloaking device for sneaking templates into your page. I like to use this technique for quick-and-dirty cases where I just need a little template or two on the page and want something light and fast.

and you would use it from script like so:

You could pre-compile the results for later use. If you call the templating function with only an ID (or a template code) then it'll return a pre-compiled function that you can execute later:

The biggest falling-down of the method, at this point, is the parsing/conversion code - it could probably use a little love. It does use one technique that I enjoy, though: If you're searching and replacing through a string with a static search and a static replace it's faster to perform the action with .split("match").join("replace") - which seems counter-intuitive but it manages to work that way in most modern browsers. (There are changes going in place to grossly improve the performance of .replace(/match/g, "replace") in the next version of Firefox - so the previous statement won't be the case for long.)

Feel free to have fun with it - I'd be very curious to see what mutations occur with the script. Since it's so simple it seems like there's a lot that can still be done with it.

Tags: javascript

95 Comments on 'JavaScript Micro-Templating'

jQuery LiveSearch

July 8th, 2008

A fun blog post popped up yesterday in which John Nunemaker ported a Quicksilver-style Live Search to jQuery. Taking a look at his code, I decided to have a little fun and re-port it to jQuery - trying to use the functional style that jQuery promotes. I think the end result is quite simple and elegant.

The final code - compare with John's port:

A couple points to note:

• .liveUpdate() no longer takes an element ID - it now accepts any jQuery selector (this is the only notable API change that I made).
• All state is stored in simple variables and accessed via closures, as opposed to as properties of an instance object.
• Only one function is used - and that's stored away within the function itself (greatly simplifying the resulting code).
• DOM queries are only done once and cached up front.
• .map() is used to simplify the creation of new arrays of information.

Tags: jquery, javascript

55 Comments on 'jQuery LiveSearch'