Hacker News Reader

Comment by mgaunard | Hacker News Reader

Why didn't you consider bitonic sort? It's also a comparison sort, and it's typically the fastest one.

Bitonic sort has a couple of properties that make it poor fit for a generic sorting algorithm:

* The number of items being sorted must be a power of 2 (2^n).

* The number of comparisons it makes is larger than other sorting algorithms like merge sort, which will make it slower in non-parallel environments in many cases.

Bitonic sort has the advantage that it can be implemented to run in highly parallel environments (hardware, FPGAs, etc.), where the cost of comparisons is offset by them operating in parallel, so the sort completes faster even though more comparisons are occurring.

bitonic sort is O(n log(n)^2), which hardly makes a difference in normal sizes (benchmarks are on 10k, which is small).

The power of 2 requirement only applies to the core kernel.

All CPUs in usage today are parallel (in 3 to 4 different ways), and bitonic sort is the best performing sort on both amd64 and aarch64.

Adding onto what the other commenter said, these sort implementations are practically all hybrids, containing multiple sort algorithms. In fact ipnsort uses optimal sorting networks as part of its small-sort https://github.com/Voultapher/sort-research-rs/blob/bf90e294.... And for example vqsort benchmarked in another one of my writeups uses a bitonic merge network to combine smaller blocks created from optimal sorting networks.

None of those are particularly optimized to make the most of the hardware capabilities though.

The obvious thing is to use SIMD.

Sorry but what exactly do you base that on? They are very much so designed to exploit the out-of-order, speculative, super-scalar nature of modern CPUs. vqsort is pure, well done SIMD and yet how do you explain that graph https://github.com/Voultapher/sort-research-rs/blob/main/wri... if your claims are true? Also there are reasons why SIMD is not a good fit for every situation.

That's before the performance bugfix we talked about, right? (We re-initialized the RNG on every sort.)

Vqsort performance on M1 is indeed about half that of AVX-512. The NEON instruction set is missing some important operations for Quicksort, including Compress and popcount of vector masks.

Yes, like everything before the addendum the results are for the the same tested vqsort version without the bug-fix, as I motivate in the section "Author's conclusion and opinion" at the end. I suspect thought that even the new version will not outperform crumsort or ipnsort on this machine.

There are plenty of other SIMD sort libraries, some of which specifically optimized for AVX2, AVX512, NEON or SVE.

Vqsort is indeed using SIMD :)

I just looked at the link he gave and it wasn't.

Intel publishes its own fast library for this, which isn't even in the benchmark list.

Measurements (by the same author) for Intel's x86-simd-sort and vqsort are here: https://github.com/Voultapher/sort-research-rs/blob/main/wri...

Pretty impressive results on the new version of vqsort.

Thanks :) We fixed a performance bug (re-seeding an RNG on each sort).

Reply on news.ycombinator.com