(Solved: How to avoid the "A script on this page is causing Internet Explorer to run slowly." message)

When writing the spellayt 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 without complex state management and stack issues.

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

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* variable contains an array of boolean indicating whether is element is prime (false) or not (true). The *_primes* array also contains the prime numbers.

#### 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 code now looks like this:

function eratosthenesSieve2(upperBound) { //Create an array of booleans representing prime = false var composites = new Array(upperBound); //Set all to prime (false) to start $.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 $.map(composites, function(index, value) { if (index < 2 || index > upperBoundSquareRoot) return value; //If the array item is a prime then map all non primes if (value == false) { var k = index * index; $.map(composites, function(index2, value2) { if (index2 == k) { k += index; return true; } return value2; }); } return value; }); //Count only the primes $.reduce(composites, 0, function(index, value, result) { if (index >= 2 && value == false) result++; return result; }); return $.execute(); }

The first *$.map* function initialises the *composites* array. The second and third map *$.map *strikes out multiples of primes. The *$.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 *$.execute* the functions. If you attach a debugger to the script, you’ll notice the functions only start executing once this method is called.

Download the plug-in code from the Map Reduce plug-in page.

Next time, I’ll dive into the details of implementing the Map Reduce plug-in and the pitfalls encountered along the way.

## No comments:

Post a Comment