I’ve recently had some fun writing a browser quicksort.
As part of a recent project, I had to implement a Knockout table component that could sort and filter its entries in realtime. This would normally have been straightforward, except for a handful of use-cases where the table would contain upwards of three thousand entries – possibly more. Calling a native array
sort() on such a large set with a particularly complex comparator would force IE8 to freeze for several seconds and throw a long running script error.
Investigating the long running script exception
Stopping it from appearing
My immediate thought was to write a quicksort.
Quicksort is particularly suitable for non-blocking code, because it can be implemented recursively, and recursion calls are a great opportunity to yield the thread. It’s fast, fairly well-understood and relatively easy to understand.
The idea is simple: we perform a ‘partition’ operation on an array, taking its last member as a ‘pivot’ and iterating through the others left to right, comparing each to the pivot as we go. If the member is larger or equal to the pivot, we put it to the right hand side. If not, we leave it on the left and try the next member. What we’re left with is an array where all the items lower than the pivot are to its left and all the items larger are to the right. We can then partition the left and right sets recursively until our set is completely sorted.
(A handy animation straight from Wikipedia)
Technically, this isn’t the only way to perform a partition – it’s the Lomuto Partition, and you can find others documented online, but the basic algorithm doesn’t differ: partition the array, then partition the sub-partitions in turn until there’s no more partitioning to be done.
We can write our partition as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
Forgive me for the C-like variable prefixes; it simply seemed the easiest way to associate the variables with the ‘diagram’ in my comments.
Once we had the partition operation, it was just a matter of finding a way to yield the UI thread between the operation calls.
process.nextTick in the browser
1 2 3
This works well enough for ocassionally yielding a thread in the middle of a long operation, but it fails when we pass a high volume of callbacks, because the timeout value doesn’t really end up being zero. In prctice, most browsers don’t run the callback in less than 10 milliseconds.
This restriction is partly down to the HTML5 specification throttling the timeout to no less than 4ms , but also partly down to the way the browser relies on the OS’ default system timer, as explained at length by Nicholas Zakas. Windows’ timer has a granularity of 15ms – that is, the timer is only updated every 15ms – so it’s possible for a setTimeout to wait the full length of that period.
When each operation takes a millisecond and then waits 14 milliseconds to spawn its child operations, that’s grossly inefficient. Profiling the sort confirmed these suspicions – Chrome would make excellent headway whilst processing the larger partitions, but then slow to a crawl as it processed the long tail of small subpartitions.
setImmediate to the rescue
But not to fear! setTimeout is not the only option we have. A new API,
window.setImmediate, was introduced by Microsoft through Internet Explorer 10 and 11. It works much like
process.nextTick – we pass a callback, yield the thread, run any queued events and pick the callback up again as soon as possible. There’s no 15ms throttling.
setImmediate isn’t a standardized API yet, though, and isn’t implemented in Gecko or Webkit . Fortunately, a Katochimoto’s setImmediate shim is available that provides the same functionality in other browsers, and even fixes certain bugs in IE10/11’s native setImmediate .
It now becomes possible to recursively partition our array in a non-blocking way:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
There’s just one problem – now we’ve made the function asynchronous, how do we know when it has finished?
Whenever we complete a partition, we know that we’ve finalized the position of the pivot. We only further process its neighbours. So we can trigger a finalization callback that increments a counter, and when the counter reaches the length of the array, we know that the array is stable.
We could perhaps implement this like so:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Now all we need is a function to kick off the first operation and maintain a count of finalizations:
1 2 3 4 5 6 7 8 9 10 11 12 13
Prioritizing native sort
Our approach was simply to prefer the native implementation unless working in IE8 or with arrays over a thousand items.
If nothing else, writing a non-blocking quicksort was a great educational exercise. The key points being:
- If you’re going to have to do it, be mindful of UI responsiveness and see if you can write your procedure in a non-blocking manner, using setImmediate and its shims where necessary
- Sorting algorithms aren’t black magic and don’t have to be scary if you don’t have a CS background (like me)
- setTimeout and browser timing are deceptive and shouldn’t be wholly trusted
At some point, I’ll probably rewrite an open source version of the code above, with a few performance tweaks and optimizations. I’ll probably post about it when I do so.
 Apparently, this is because running a timer with high resolution means the CPU can’t enter low power modes. This was determined to be a problem for battery life in mobile devices, so the 4ms was agreed as a compromise between efficiency and accuracy.
 Currently it faces some opposition from Google and Apple. It’s possible that the API might be deprecated in future, so using the setImmediate shim is probably a good insurance policy in case MS ever withdraws the API.
 You can find out how it actually performs the shim in the project’s README. It’s quite interesting.