CPU intensive javascript computations without blocking the single thread

September 10, 2013

[Updated post here: Part 2: CPU intensive javascript computations without blocking the single thread]

Lately I’ve been working on a javascript heavy application. When the user enters the page, a lot of calculations need to be done before the user can actually work with the data-set. Normally you’d leave these kinds of operations to the server and allow it to cache the results, but in my case, the computations have to do with the positioning of elements in the DOM-tree. These positions are relative to the browser’s size, so caching or pre-calculating is not a possibility for me.

At first, when prototyping the app, I had a single for-loop that called on a function that did the computation for a single element.

for( var i = 0; i < elements.length; i++ ) {
	doHeavyLifting( elements[i] );
}

The problem

Normally, when working with smaller data-sets this would work quite well, but in my case, this for-loop blocked the UI thread for well over 3 seconds, leaving the browsers completely unresponsive. The reason for this is because javascript runs in a single threaded environment, so if a single function does a lot of work, everything else has to wait for that function to complete (or fail) before anything else can be permitted to run. If a user with a slow computer would try to access this page, it’s quite possible that the browser would throw up the dreaded “Unresponsive page, kill script?” notice. in order to get around this problem I used the old and ancient trick with setTimeout, where I iterate through the items in a non-blocking way.

function heavyLifter() {

	this.elementsLength = 1000; // Amount of operations
	this.currentPosition = 0;   // Current position

	// Initializer to start the iterator
	this.startCalculation = function() {
		// Reset current position to zero
		this.currentPosition = 0;
		// Start looping
		setTimeout(
			this.calculate.bind(this),
			0
		);
	}

	this.calculate = function(){
		// Check that we still have iterations left, otherwise, return
		// out of function without calling a new one.
		if( this.currentPosition > this.elementsLength ) return;
		// Do computation
		doHeavyLifting( element[ this.currentPosition ] );

		// Add to counter
		this.currentPosition++;
	}
}

// Initalize the object and start iterating
var computationIterator = new heavyLifter();
computationIterator.startCalculation();

The works because, as I earlier mentioned, javascript being single threaded, every single iteration will be thrown in to the event chain as a single event instead of having one large event (the for-loop). This solution is a great way to achieve a responsive page and still get a lot of stuff done, not only does our stuff get computed, but other parts of the application and web page will also have a chance to get run by the processor. But this also has a drawback, because other parts of the application are being run, we don’t have any priority on the single iterations, leaving us waiting for all the computations to get done, which will take a lot longer than just running them in a for-loop. In my case, the for-loop took 3 seconds to complete, whilst the setTimeout approach nearly took 10 seconds to complete, and as everybody knows in the web industry, the waiting game isn’t something our users like to play.

After reworking a lot of my code, shaving off 100 ms here and there, I had gotten the loop to complete in about 9 seconds. But the base of the problem was still there, the setTimeout. After I had run a few profiling tests to find out more about my specific problem, I noticed that the CPU was idle in about 60% of the time during my processing time.

The solution

So I figured, if one approach eats all the resources, and the other approach doesn’t even touch the available resources, why not combine them?

	this.calculate = function(){
		// Check that we still have iterations left, otherwise, return
		// out of function without calling a new one.
		if( this.currentPosition > this.elementsLength ) return;

		//
		// Do computation
		//

		// save currentposition, because we'll alter it
		// in the loop
		var n = this.currentPosition;

		// Batch process 50 elements at a time
		for( var i = n; i < n+50; i++ ){
			// Check that we haven't run out of elements
			if( this.currentPosition > this.elementsLength ) break;
			// Add to counter
			this.currentPosition++;

			doHeavyLifting( element[ i ] );
		}
	}

I rebuilt the method calculate so that it batch-processed the elements instead of only doing one element at a time, in essence, I utilized the CPU resources I had available in a more efficient way. In this instance, I got the computation down to around 3.5 seconds and still allowing the single thread to handle all other computational tasks without locking up.

Proving my point

It’s easy to sit around and say something and not back it up. Sadly, I can’t show you the project that I was working on, but it didn’t feel right to just leave you guys without some kind of working example of the problem and the different kinds of solutions to it.

My example app

In my example I’ve created four different ways to calculate the same thing (or actually, three different ways, but four buttons). The first button only runs a single iteration, giving you a baseline of some sort. The three other buttons all do the same thing, they call a specific function 1 million times, and then gives you back the time it took from start to finish.

Both “async” versions give you feedback on how far it has come in the process, and the reason for the for-loop not doing it should be quite obvious at this point, that’s because it blocks the UI thread, so no other work can be done until the loop has finished (and this also includes rendering/modifications of the DOM tree).

Update — 27-10-2015

Since there’s been some requests in the comments to update the code with requestAnimationFrame, I’ve written a new post, with some new code examples. You can find it here: Part 2: CPU intensive javascript computations without blocking the single thread.

Tags