Faster JavaScript Sorting Using Typed Arrays

JavaScript has two kinds of arrays: standard ones and typed ones. These two kinds of arrays have different capabilities. Standard arrays can grow, but typed arrays can not. Standard arrays can hold numbers, strings, objects, etc.. Typed arrays can only hold specific numeric data types: 8-bit, 16-bit, 32-bit and 64 bit unsigned and signed integers, as well as 32-bit and 64-bit floating-point.

Both kinds of arrays can be sorted, with substantial performance differences. Below is a graph of sorting performance of array of 32-bit unsigned integers versus Uint32 typed array:

JavaScriptSortArrayVsTyped

From array size of 1K up to 16M, sorting typed arrays is 4X to 6X faster than standard arrays. Above 62K typed arrays are consistently 6X faster to sort. About 8 Million Uint32’s per second is the performance level when sorting typed arrays of Uint32’s.

Sorting Faster

JavaScript uses a QuickSort/InsertionSort hybrid approach for its general purpose sorting. These algorithms are bound by O(NlgN) performance because comparisons are used. It’s possible to reach even higher level of performance by using non-comparison based sorting, such as Radix Sort, which is a linear time O(N) sorting algorithm.

Below is a graph of JavaScript sort of typed arrays versus LSD Radix Sort of Uint32 typed array.

JavaScriptSortTypedVsRadix

LSD Radix Sort consistently outperforms JavaScript sort by 4X for array sizes of 1K to 16 Million of Uint32’s. Sorting at about 32 Million Uint32’s per second. This level of performance is comparable to performance of LSD Radix Sort in C# (see HPCsharp nuget package)

LSD Radix Sort performs at the same level for standard arrays and for typed arrays.

Sorting Faster in Special Cases

For Uint8 and Uint16 typed arrays, Radix Sort simplifies into Counting Sort. In these cases, it’s possible to sort even faster and in-place. For typed arrays of Uint8’s, Counting Sort performs between 700 – 800 Mega Uint8’s per second. This is about 40X faster than JavaScript built-in sort. For typed arrays of Uint16’s, Counting Sort performs about 150 Mega Uint16’s per second, which is about 15X faster than JavaScript built-in sort.

Both of these Counting Sort algorithms have just been added to version 1.1.0 of hpc-algorithms npm package.

NPM and Source Code

The above LSD Radix Sort and Counting Sort algorithms are available in hpc-algorithms npm. This package is open source and free. The algorithms were ported from C++ and C# HPCsharp nuget package, which is also open source and free.

JavaScript source code is available on GitHub.

Datatypes Supported

So far, in JavaScript only arrays of Uint32’s, Uint8’s and Uint16’s have been ported from C#. Only LSD Radix Sort and Counting Sort have been ported. LSD Radix Sort is not an in-place algorithm and allocates additional memory of the same size as the input array to be sorted. Counting Sort is in-place.

In C# support for most of the data types has been implemented, such as floating-point and signed integer. Also, MSD Radix Sort has been implemented, which is in-place.

Let me know which data types you’d like to see ported to JavaScript, or other sorting capabilities.

Advertisements

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