Faster Sorting in JavaScript

JavaScript is taking over the world as the language of the web. When it comes to sorting, JavaScript is about 9 times slower than C++ and C#, but is slightly faster than Python 3.6, as I’ve shown in the previous post Sorting Speed of Several Languages. In this post, let’s explore the possibility of sorting faster in JavaScript.

By default, JavaScript sorts arrays of strings. If you try to sort an array of integers, the result will be sorted wrong. JavaScript’s built-in sorting algorithm is nicely general purpose. It uses a comparison function provided by the user to sort any data type that can be compared. For sorting an array of integers correctly, a common approach is to provide a comparison function that works properly for integers instead of using the default comparison for strings. One such comparison function is provided on How to sort an array of integers correctly StackOverflow topic. This leads to a correct sorting algorithm for arrays of integers.

Using comparisons for sorting puts a well known performance bound on the algorithm of O(nlogn). It may be possible to increase performance by using a sorting algorithm that does not use comparisons, such as the Radix Sort. I’ve implemented the least-significant-digit (LSD) version of the Radix Sort in JavaScript, and verified it’s correctness by comparing results to JavaScript built-in sort. Below is a graph comparing performance of LSD Radix Sort for arrays of random unsigned integers:

JavaScriptSortComparison

X-axis is the size of array, and Y-axis is time in seconds to sort that array. Smaller values on the Y-axis mean the algorithm took less time to sort. LSD Radix sort is much faster for sorting, compared to JavaScript built-in sort. I used the same array size filled with the same random unsigned integer values for both sorting algorithms. Above 20 million element array size, performance becomes much more variable for JavaScript sort, and Radix Sort slows down as well. This is most likely due to memory allocation cutting into performance for both algorithms.

The graph below shows how much faster LSD Radix Sort is:

JavaScriptSortToLSDRadixSort

LSD Radix Sort is 5 to 50 times faster than JavaScript built-in sort for all array sizes tested. Above 50 million elements the Chrome browser (64-bit) ran out of memory. Chrome was the only browser I have tested so far.

LSD Radix Sort Implementation

I put together hpc-algorithms npm, which is open source and free, containing the implementation of this algorithm. The source code is in the GitHub/hpc-algorithms repository.

If you look in the implementation, notice that all memory allocations are performed before the main while loop. This is most likely the reason the Radix Sort LSD implementation suffers less performance loss than the JavaScript sort as array size grows above 20 million elements and memory allocation influences performance. Radix Sort LSD continues to perform well for arrays up to 33 million elements, and then starts slowing down as well.

Usage Example

function simpleUsageExampleOfRadixSortLSD() {
    var arrayToBeSorted = [ 99, 1999999999, 51, 23, 102];
    var sortedArray = HpcAlgorithms.Sorting.RadixSortLsdUInt32(arrayToBeSorted);
    for ( var _current = 0; _current < sortedArray.length; _current++ ) {
        console.log(sortedArray[_current]);
    }
}

Performance for Presorted Array

The graph below shows performance of JavaScript built-in sort versus LSD Radix Sort for presorted arrays:

JavaScriptSortVsRadixSortPresorted

LSD Radix Sort is consistently and substantially faster than JavaScript’s built-in sort, especially for presorted arrays smaller than 30 Million integers. LSD Radix Sort is 5 to 34 times faster for arrays up to 50 Million elements. For arrays smaller than 30 Million integers, LSD Radix Sort is 16 to 34 times faster.

Constant Array

The graph below shows performance of JavaScript built-in sort versus LSD Radix Sort for arrays smaller than 20 Million integer arrays filled with a constant value, such as all values of 255:

JavaScriptVsLsdRadixSortConstant

LSD Radix Sort shows more consistent performance than JavaScript sort for constant value filled arrays under 20 Million elements. For arrays larger than 20 Million performance becomes more erratic for both algorithms, most likely due to memory allocation performance variations.

Conclusion

It’s hard to see from the graphs that the LSD Radix Sort runs between 24 and 42 MegaIntegers per second, when sorting arrays smaller than 30 MegaIntegers. This level of performance beats built-in algorithms of all languages that were measured in Sorting Speed of Several Languages (C++, C#, and Python). It is also within 2X of LSD Radix Sort implementation in C++, which was the starting point for the above JavaScript code.

Further Ideas

LSD Radix Sort is also a stable sort as is described in Stable Sorting in JavaScript

When you want to sort JavaScript Objects based on an unsigned integer key check out JavaScript Sorting of Array of Objects

When you want to go even faster, take a look at using typed arrays as discussed in Faster JavaScript Sorting Using Typed Arrays

 

Advertisements

7 thoughts on “Faster Sorting in JavaScript

    1. Hey Eric. I recently released hpc-algorithms npm that implements even a faster version of LSD Radix Sort in JavaScript, plus a version that lets you sort objects based on a numeric key within that object. I would love to parallelize this library, but am cautious if this library will queue tasks and not over subscibe.

      Like

  1. That is a very fast sort, it runs about 3x as fast as barsort.js which is a “counting” based algorithm (float64). I don’t see a way to get it to return an ordering index though, which I find is often what is needed rather than having the source itself reordered.

    Here is a little article on barsort :

    View at Medium.com

    Like

    1. Recently, in my C# nuget package/library (HPCsharp) I implemented an LSD Radix Sort version that returned indexes instead of re-ordered array elements. This particular application was for a college student working on an image processing application where 8-bit depth information per pixel needed to be sorted quickly, providing information about which pixels were closest or furthest. What do you run into as the need to provide sorted indexes?

      Like

    1. Sorry about such a huge delay, as I somehow missed your comment. 20K of items in an array should definitely be large enough of an array to show a speedup of this Radix Sort implementation over the built-in .sort(), especially 3X slower. I’ve never seen this behavior. Could you send me your benchmark? Also, try the new npm I’ve put together, it has an even faster implementation of LSD Radix Sort.

      Like

      1. I ran a benchmark today and there is a strange behavior where the first two times the code is run after the page has been refreshed, LSD Radix Sort is slower by 2-3X, but then after that it is 20X faster. This was for an array of 10K elements. This seems like a JIT behavior, or array paging behavior. Something that we need to figure out.
        I looked into this further (https://blog.sessionstack.com/how-javascript-works-inside-the-v8-engine-5-tips-on-how-to-write-optimized-code-ac089e62b12e) and it looks like Chrome at first compiles using a basic compiler to get the code running quickly, followed by a separate thread that fully optimizes the code after it’s been profiled. I’ve also seen some talks by Intel saying they have worked for many years on the JavaScript highly optimized compiler to make sure it runs well on Intel CPUs. This is most likely the affect we are seeing – the basic JIT at first, followed by a fully optimized compile later to get the full performance. It looks like the LSD Radix Sort benefits significantly from this full optimization and gets a significant performance boost.

        It may be possible to run the LSD Radix Sort a couple of times when your script first loads, so that when you really use the algorithm, it runs at full performance level.

        Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s