Whilst writing a jQuery spell-checking plug-in, I came across an interesting problem with long running JavaScript code – the browser would timeout and display a message box to the user with the text “A script on this page is causing Internet Explorer to run slowly.” Even worse, the dialog gives the user the option to cancel the script, potentially breaking your page.

The solution was to use a timer to simulate a background thread, but the solution wasn’t generic and felt far from elegant. This week, with the approval of Google’s Distributed MapReduce patent, I realised that a simpler non-distributed map reduce algorithm would enable the running of code both asynchronously and over long periods of time in JavaScript.

Map reduce works by taking key/value pairs and running them through a function to create intermediate key/value pairs until all the data has been processed (map). The data is then filtered (reduced) to obtain a result. Joel Spolsky (Joel on Software) has a nice article that explains the fundamentals behind map reduce.

### Sieve of Eratosthenes Example

The Sieve of Eratosthenes is an algorithm for finding prime numbers, this Wikipedia article has a visual explanation of how it works. Its a great example of something that is processor intensive but can be broken up into smaller steps.

A standard JavaScript implementation (using Euler’s optimisation) would look something like this:

```
function eratosthenesSieve(upperBound) {
var upperBoundSquareRoot = Math.floor(Math.sqrt(upperBound), 0);
var isComposite = [];
for (var m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite[m]) {
_primes.push(m);
for(var k = m * m; k <= upperBound; k += m) {
isComposite[k] = true;
}
}
}
for(m = upperBoundSquareRoot; m <= upperBound; m++) {
if (!isComposite[m]) primes.push(m);
}
}
```

The *isComposite* array contains boolean values indicating whether the interger is prime (false) or not (true). The *primes* array also contains the prime numbers that have been found.

### Redefining the problem as a set of Map / Reduce functions

The great thing about map/reduce is that once the problem is defined as a set of functions, it doesn’t matter how the map/reduce is implemented, you should always get the same results. Usually, each for loop will result in a matching *map* or *reduce*function. Reorganising the *eratosthenesSieve* function to use map reduce requires the following steps :

an array containing the initial values – in this case the index of the array is the number we are testing, and a boolean will indicate whether it is a prime or composite number.*Map*each prime up to the square root of the upper bound. For each*Map*that is a prime, strike out it’s square multiplied by the remaining numbers until the upper bound is reached.*Map*the array by totalling the number of primes (false values) left.*Reduce*- Execute the functions to return the result.

The refactored code now looks like this, using the fn.map and fn.reduce functions from the Leaf Javascript Framework:

```
//Updated function using theoretical
```*fn.map* and *fn.reduce* functions
function eratosthenesSieve2(upperBound) {
//Create an array of booleans representing prime = false
var composites = new Array(upperBound);
//Set all to prime (false) to start
fn.map(composites, function(index, value) {
return false;
});
//Calculate the sqr root of the upper bound
var upperBoundSquareRoot = Math.floor(Math.sqrt(upperBound), 0);
//For each item, calculate the non primes
fn.map(composites, function(index, value) {
if (index upperBoundSquareRoot) return value;
//If the array item is a prime then map all non primes
if (value == false) {
var k = index * index;
fn.map(composites, function(index2, value2) {
if (index2 == k) {
k += index;
return true;
}
return value2;
});
}
return value;
});
//Count only the primes
fn.reduce(composites, 0, function(index, value, result) {
if (index >= 2 && value == false) result++;
return result;
});
return fn.execute();
}

```
```

The first *fn.map* function initialises the composites array. The second and third map *fn.map* strikes out multiples of primes. The *fn.reduce* function counts the remaining primes by accumulating the result variable. Note the extra work we have to do to simulate the functionality of the for loop and when we haven’t performed any processing we return the same value that was passed into the function.

Finally, we *fn.execute* the functions. If you attach a debugger to the script, you’ll notice the functions only start executing once this method is called. A map or reduce functions is executed on each tick of the timer, and in this way any arbitrary code formulated in this way can run in the background of a browser without causing the script timeout message to appear.

You can get an actual implementation of these functions in the Superset JavaScript framework on GitHub.