6 ms·
Tangent: I see that the author focused on improving sorting algorithms, and also at some point switches to a Uint8Array (although not in the sorting part). I r
by vanderZwan 9y ago
Tangent: I see that the author focused on improving sorting algorithms, and also at some point switches to a Uint8Array (although not in the sorting part).
I recently discovered that a JavaScript implementation of radix sort up to four times faster than the the built-in sorting algorithms for TypedArrays[0][1][2]. Imagine how much faster a good WASM implementation could be!
It also makes me wonder why browsers don't make use of the guaranteed memory layout of typed arrays to use faster native algorithms. Sure, Typed Arrays have to support the sorting API, which is comparison based and works with closures. But why not detect when someone calls sort() without any further arguments, and make that very common case use faster native code?
Because for me, this difference in performance made a difference: I am animating plots where I need to sort more than 100k elements each frame, and sort eating up 5ms or 20ms is the difference between choppy and smooth animations.
[0] https://run.perf.zone/view/radix-sort-uint32-1000-items-typed-and-plain-array-1510082514775 https://run.perf.zone/view/radix-sort-uint32-1000-items-type...
[1] https://run.perf.zone/view/radix-sort-uint32-1000000-items-typed-and-plain-array-1510082642142 https://run.perf.zone/view/radix-sort-uint32-1000000-items-t...
[2] https://run.perf.zone/view/Radix-sort-Uint8Array-loop-vs-fill-in-place-1510007933053 https://run.perf.zone/view/Radix-sort-Uint8Array-loop-vs-fil...
- spiralx 9y agoOn my OnePlus 5T the standard sort() was twice as fast as the radix sort for the UInt8 array, but it was only 30% slower for the Float64 and regular arrays, whereas sort() was hundreds of times slower - strange...