Delaying Repeatedly

Sooner or later, a Javascripter will eventually encounter a situation where they have a loop that takes so long to process that the browser becomes unresponsive. To solve this, you have some options

optimize the loop so that it always runs under 100ms - the maximum response time that doesn't affect user experience
offload the processing to the server
Use webworker, but it doesn't yet have great browser support, and they can't touch the DOM
put a wait inside the body of the loop so as to let the browser breath

If you've exhausted options #1-3, read on.

To do #4, most people would approach it this way

for (var i = 0, len = items.length; i < len; i++){
    processItem(items[i])
    sleep(10)   // sleep to yield
}

This would work in C or Python, but not Javascript. Javascript does not have a sleep or equivalent function that would just halt program execution. In fact, a function like this wouldn't work in the browser because Javascript is single threaded, and a function that blocks execution like that will freeze up the browser right away.

So, to achieve the same thing in Javascript, we have to use the setTimeout function - which using the non-blocking IO paradigm.

Easy right? So we just replace the sleep call with setTimeout.

for (var i = 0, len = items.length; i < len; i++){
    setTimeout(function(){
        processItem(items[i])
    }, 10)   // sleep to yield
}

There are two problem with this code. Let's address the first one else where. The second problem is: rather than spacing out the function calls with pauses in between them, this will schedule a bunch of jobs(one for each item) to be performed on the event queue all at once, the event queue will have to work just as hard as if we had just done the processing within the loop.

`setTimeout`

The setTimeout function

is asynchronous
uses the callback style of control flow, do you grok callbacks?

In order to cope with this non-synchronous style, we'll have to do away with the for-loop altogether. Here is how we'd do that

var queue = items.slice(0)              // 1. make a copy of the array, because
                                        //    we are going to modify it
function processNextItem(){             
    var nextItem = queue.shift()        // 2. take the next item off the array
    if (nextItem){
        processItem(nextItem)           // 3. process this item
        setTimeout(processNextItem, 10) // 4. give the browser a little time to breath
                                        //    start again in 10ms
    }
}
processNextItem()                       // 5. kick it off with the first
                                        //    call to this function

This "loop" will give you the desired result: processing all the items without locking up the browser. Great!

Improving the Running Time

However, the problem with this approach is that it would lengthen the total processing time substantially. For example, let's say you need to process 10000 items, and it takes 1ms to process each item. If you had process them all within a loop(with no breathing), it would take you 10000 x 1ms = 10000ms. But, using the above method, because of the added 10ms delay for each item, it would take you 10000 x (10ms + 1ms) = 110000ms. So, while the browser isn't totally frozen and the user can still interact with the page, it will take more than 10 times as long to finish processing, and as a result, the user could very well be watching an interminable progress bar.

We can improve this by processing the items in batches. Process 100 items at a time, for example. This would reduce the total process time to (10000 / 100) * (10ms + 100 * 1ms) = 11000ms: much better - only 10% slower than processing with no breathing.

Dynamic Batch Sizes

Now, about the batch size of 100, we chose 100 because we know the processing time for a batch will stay within the 100ms threshold of responsiveness. But what if the processing time of an item is not easily predictable? Or, what if we wanted to write a generic processing routine that would work well with different types of jobs? What if we can dynamically figure out the batch size for which the processing time will stay within 100ms? We can do all of the above with a timer

var queue = items.slice(0)                                 
function processNextBatch(){
    var nextItem,
        startTime = +new Date
    while(startTime + 100 >= +new Date){
        nextItem = queue.shift()
        if (!nextItem) return
        processItem(nextItem)
    }
    setTimeout(processNextBatch, 10)
}
processNextBatch()

Cool! We can generalize this more still by turning it into a reusable function

function processItems(items, processItem, delay){
    delay = delay || 10
    var queue = items.slice(0)                                 
    function processNextBatch(){
        var nextItem,
            startTime = +new Date
        while(startTime + 100 >= +new Date){
            nextItem = queue.shift()
            if (!nextItem) return
            processItem(nextItem)
        }
        setTimeout(processNextBatch, delay)
    }
    processNextBatch()
}

So now we can go crazy with it

processItems(locations, plotOnGoogleMap)

processItems(polygons, drawOnCanvas)

Reference

Book: High Performance Javascript (Chapter 6)
Paper: Response time in man-computer transactions - Robert Miller