By: James Edwards

October 24th, 2008

Reader Rating: 9

Okay, before we begin, let me come clean and admit that the title of this article is a little sensationalist! JavaScript doesn’t really have multi-threading capabilities, and there’s nothing a JavaScript programmer can do to change that. In all browsers—apart from Google Chrome—JavaScript runs in a single execution thread, and that’s just how it is.

However, what we can do is simulate multi-threading, insofar that it gives rise to one of the benefits of a multi-threaded environment: it allows us to run extremely intensive code. This is code which would otherwise freeze-up the browser and generate one of those “unresponsive script” warnings in Firefox.

Time Waits for No One

It all hinges on the use of asynchronous timers. When we run repetitive code inside an asynchronous timer, we’re giving the browser’s script interpreter time to process each iteration.

Effectively, a piece of code inside a for iterator is asking the interpreter to do everything straight away: “run this code n times as fast as possible.” However the same code inside an asynchronous timer is breaking the code up into small, discreet chunks; that is, “run this code once as fast possible,”—then wait—then “run this code once as fast as possible”, and so on, n times.

The trick is that the code inside each iteration is small and simple enough for the interpreter to process it completely within the speed of the timer, be it 100 or 5,000 milliseconds. If that requirement is met, then it doesn’t matter how intense the overall code is, because we’re not asking for it to be run all at once.

How Intense is “Too Intense”?

Normally, if I were writing a script that proved to be too intensive, I would look at re-engineering it; such a significant slowdown usually indicates a problem with the code, or a deeper problem with the design of an application.

But sometimes it doesn’t. Sometimes there’s simply no way to avoid the intensity of a particular operation, short of not doing it in JavaScript at all.

That might be the best solution in a given case; perhaps some processing in an application needs to be moved to the server-side, where it has more processing power to work with, generally, and a genuinely threaded execution environment (a web server).

But eventually you may find a situation where that’s just not an option—where JavaScript simply must be able to do something, or be damned. That’s the situation I found myself in when developing my Firefox extension, Dust-Me Selectors [1].

The core of that extension is the ability to test CSS selectors that apply to a page, to see if they’re actually being used. The essence of this is a set of evaluations using the matchAll() method from Dean Edwards [2]’ base2 [3]:

for(var i=0; i<selectors.length; i++)
{
 if(base2.DOM.Document.matchAll
   (contentdoc, selectors[i]).length > 0)
 {
   used ++;
 }
 else
 {
   unused ++;
 }
}

Straightforward enough, for sure. But matchAll() itself is pretty intense, having—as it does—to parse and evaluate any CSS1 or CSS2 selector, then walk the entire DOM tree looking for matches; and the extension does that for each individual selector, of which there may be several thousand. That process, on the surface so simple, could be so intensive that the whole browser freezes while it’s happening. And this is what we find.

Locking up the browser is obviously not an option, so if this is to work at all, we must find a way of making it run without error.

A Simple Test Case

Let’s demonstrate the problem with a simple test case involving two levels of iteration; the inner level is deliberately too intensive so we can create the race conditions, while the outer level is fairly short so that it simulates the main code. This is what we have:

function process()
{
 var above = 0, below = 0;
 for(var i=0; i<200000; i++)
 {
   if(Math.random() * 2 > 1)
   {
     above ++;      
   }
   else
   {
     below ++;
   }
 }
}


function test1()
{
 var result1 = document.getElementById('result1');
 
 var start = new Date().getTime();
   
 for(var i=0; i<200; i++)
 {
   result1.value =  'time=' +  
     (new Date().getTime() - start) + ' [i=' + i + ']';
   
   process();
 }
 
 result1.value = 'time=' +  
   (new Date().getTime() - start) + ' [done]';
}

We kick off our test, and get our output, from a simple form (this is test code, not production, so forgive me for resorting to using inline event handlers):

<form action="">
 <fieldset>
   <input type="button" value="test1" onclick="test1()" />
   <input type="text" id="result1" />
 </fieldset>
</form>


Now let’s run that code in Firefox (in this case, Firefox 3 on a 2GHz MacBook) … and as expected, the browser UI freezes while it’s running (making it impossible, for example, to press refresh and abandon the process). After about 90 iterations, Firefox produces an “unresponsive script” warning dialog.

If we allow it to continue, after another 90 iterations Firefox produces the same dialog again.

Safari 3 and Internet Explorer 6 behave similarly in this respect, with a frozen UI and a threshold at which a warning dialog is produced. In Opera there is no such dialog—it just continues to run the code until it’s done—but the browser UI is similarly frozen until the task is complete.

Clearly we can’t run code like that in practice. So let’s re-factor it and use an asynchronous timer for the outer loop:

function test2()
{
 var result2 = document.getElementById('result2');
 
 var start = new Date().getTime();
 
 var i = 0, limit = 200, busy = false;
 var processor = setInterval(function()
 {
   if(!busy)
   {
     busy = true;
     
     result2.value =  'time=' +  
       (new Date().getTime() - start) + ' [i=' + i + ']';
     
     process();
     
     if(++i == limit)
     {
       clearInterval(processor);

       result2.value = 'time=' +  
         (new Date().getTime() - start) + ' [done]';
     }
     
     busy = false;
   }
   
 }, 100);
 
}

Now let’s run it in again … and this time we receive completely different results. The code takes a while to complete, sure, but it runs successfully all the way to the end, without the UI freezing and without warnings about excessively slow scripting.

(The busy flag is used to prevent timer instances from colliding. If we’re already in the middle of a sub-process when the next iteration comes around, we simply just wait for the following iteration, thereby ensuring that only one sub-process is running at a time.)

So you see, although the work we can do on the inner process is still minimal, the number of times we can run that process is now unlimited: we can run the outer loop basically forever, and the browser will never freeze.

That’s much more like it—we can use this in the wild.

You’re Crazy!

I can hear the objectors already. In fact, I could be one myself: why would you do this—what kind of crazy person insists on pushing JavaScript to all these places it was never designed to go? Your code is just too intense. This is the wrong tool for the job. If you have to jump through these kinds of hoops then the design of your application is fundamentally wrong.

I’ve already mentioned one example where I had to find a way for heavy scripting to work; it was either that, or the whole idea had to be abandoned. If you’re not convinced by that answer, then the rest of the article may not appeal to you either.

But if you are—or at least, if you’re open to being convinced, here’s another example that really nails it home: using JavaScript to write games where you can play against the computer.

Game on

What I’m talking about here is the code required to understand the rules of a game, which can then evaluate situations and tactics in order to try to beat you at that game. Complicated stuff.

To illustrate, I’m going to look at a project I’ve been developing on the side for a little while. By “little while” I mean three years, the majority of which was spent at a plateau where the game theoretically worked, but was too intense to use … until I thought of this approach. The game is a competitive puzzle based around color- and shape-matching.

To summarize: you make your way across the board by adjacent shape- and color-matching. For example, if you start on, say, a green triangle—then you can move to any other triangle, or any other green shape. Your objective is to reach the crystal in the middle, then take it to the other side of the board, while your opponent tries to do the same. You can also steal the crystal from your opponent.

So, we have logical rules determining movement and we can also see tactics emerging. For example, to avoid having your opponent reach the crystal, or stealing it from you—you might select a move that blocks them, or try to finish at a place they can’t reach.

The work of the computer is to find the best move for any given situation, so let’s have a look at that process in summary pseudo-code:

function compute()  
{  
 var move = null;  
   
 move = tactic1();  
 if(!move) { move = tactic2(); }  
 if(!move) { move = tactic3(); }  
   
 if(move)  
 {  
   doit();  
 }  
 else  
 {  
   pass();  
 }  
}

We evaluate a tactic, and if that gives us a good move then we’re done; otherwise we evaluate another tactic, and so on, until we either have a move, or conclude that there isn’t one and we have to pass.

Each of those tactic functions runs an expensive process, as it has to evaluate every position on the board, as well as potential future positions, possibly many times each in light of various factors. The example only has three tactics, but in the real game there are dozens of different possibilities, each one expensive to evaluate.

Any one of those evaluations individually is fine, but all of them together, run consecutively, make for an overly intense process that freezes the browser.

So what I did was split the main code into discreet tasks, each of which is selected with a switch statement, and iterated over using an asynchronous timer. The logic of this is not a million miles away from those Choose Your Own Adventure [5] books I used to have as a kid, where each task concludes with a choice of further tasks, all in real time, until we reach the end:

function compute()  
{  
 var move = null;  
   
 var busy = false, task = 'init';  
 var processor = setInterval(function()  
 {  
   if(!busy)  
   {  
     switch(task)  
     {  
       case 'init' :  
         
         move = tactic1();  
         if(move) { task = 'doit'; }  
         else { task = 'tactic2'; }  
         
         busy = false;  
         break;  
           
       case 'tactic2' :  
         
         move = tactic2();  
         if(move) { task = 'doit'; }  
         else { task = 'tactic3'; }  
         
         busy = false;  
         break;  
           
       case 'tactic3' :  
         
         move = tactic3();  
         if(move) { task = 'doit'; }  
         else { task = 'pass'; }  
         
         busy = false;  
         break;  
           
       case 'doit' :  
         
         doit();  
         task = 'final';  
           
         busy = false;  
         break;  
 
       case 'pass' :  
         
         pass();  
         task = 'final';  
           
         busy = false;  
         break;  
 
       case 'final' :  
         
         clearInterval(processor);  
         
         busy = false;  
         break;  
     }  
   }  
     
 }, 100);  
}

This code is significantly more verbose than the original, so if reducing code size were the only imperative, this would clearly not be the way to go.

But what we’re trying to do here is create an execution environment with no ceiling, that is, a process that doesn’t have an upper limit in terms of complexity and length; and that’s what we’ve done.

This pattern can be extended indefinitely, with hundreds or even thousands of tasks. It might take a long time to run, but run it will, and as long as each individual task is not too intense, it will run without killing the browser.

A Path of No Return

The strength of this approach is also its major weakness: since the inner function is asynchronous, we cannot return a value from the outer function. So, for example, we cannot do this (or rather, we can, but there would be no point):

function checksomething()  
{  
 var okay = false;    
   
 var i = 0, limit = 100, busy = false;  
 var processor = setInterval(function()  
 {  
   if(!busy)  
   {  
     busy = true;  
       
     if(condition)  
     {  
       okay = true;  
     }  
 
     if(++i == limit)  
     {  
       clearInterval(processor);  
     }  
       
     busy = false;  
   }  
     
 }, 100);  
   
 return okay;    
}

That checksomething() function will always return false because the inner function is asynchronous. The outer function will return before the first iteration of the inner function has even happened!

This next example is similarly pointless:

if(++i == limit)  
{  
 clearInterval(processor);  
   
 return okay;  
}

We’re out of the scope of the outer function, therefore we’re unable to return from it; that return value disappears uselessly into the ether.

What we can do here is take a leaf out of Ajax coding techniques, and use a callback function (which in this example I’m calling “oncomplete”):

function checksomething(oncomplete)  
{  
 var okay = false;  
   
 var i = 0, limit = 100, busy = false;  
 var processor = setInterval(function()  
 {  
   if(!busy)  
   {  
     busy = true;  
       
     if(condition)  
     {  
       okay = true;  
     }  
 
     if(++i == limit)  
     {  
       clearInterval(processor);  
         
       if(typeof oncomplete == 'function')  
       {  
         oncomplete(okay);  
       }  
     }  
       
     busy = false;  
   }  
     
 }, 100);  
}

So when we call checksomething(), we pass an anonymous function as its argument, and that function is called with the final value when the job is complete:

checksomething(function(result)  
{  
 alert(result);  
});

Elegant? No. But robustly functional? Yes. And that’s the point. Using this technique, we can write scripts that would otherwise be impossible.

Do Androids Dream of Silicon Sheep?

With this technique in our kit, we now have a means for tackling JavaScript projects that were previously way out of the realm of possibility. The game I developed this pattern for has fairly simple logic, and hence a fairly simple brain, but it was still too much for conventional iteration; and there are plenty of other games out there that need a good deal more clout!

My next plan is to use this technique to implement a JavaScript Chess engine. Chess has a huge range of possible scenarios and tactics, leading to decisions that could take an extremely long time to calculate, far longer than would have been feasible without this technique. Intense computation is required to create even the most basic thinking machine, and I confess to being quite excited about the possibilities.

If we can pull off tricks like this, who’s to say what’s possible? Natural language processing, heuristics … perhaps we have the building blocks to develop Artificial Intelligence in JavaScript!

Image credit: Randen L Peterson [6]

[1] http://www.sitepoint.com/dustmeselectors/
[2] http://dean.edwards.name/
[3] http://code.google.com/p/base2/
[4] http://sitepointstatic.com/examples/jsmultithreading/test.html
[5] http://en.wikipedia.org/wiki/Choose_Your_Own_Adventure
[6] http://www.flickr.com/photos/chefranden/310767408/