11 ms·
Adding onto what the other commenter said, these sort implementations are practically all hybrids, containing multiple sort algorithms. In fact ipnsort uses opt
by Voultapher 3y ago
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/bf90e294bd84c7cfe746f1bd718ff133bcb89389/ipnsort/src/smallsort.rs#L274 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.
- mgaunard 3y agoNone of those are particularly optimized to make the most of the hardware capabilities though. The obvious thing is to use SIMD.
- janwas 3y agoVqsort is indeed using SIMD :)
- mgaunard 3y agoI 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.
- janwas 3y agoMeasurements (by the same author) for Intel's x86-simd-sort and vqsort are here: https://github.com/Voultapher/sort-research-rs/blob/main/writeup/intel_avx512/text.md#updated-vqsort-results https://github.com/Voultapher/sort-research-rs/blob/main/wri...
- Voultapher 3y agoSorry 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/writeup/intel_avx512/text.md#neon-test-machine 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.
- janwas 3y agoThat'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.
- Voultapher 3y agoYes, 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.
- mgaunard 3y agoThere are plenty of other SIMD sort libraries, some of which specifically optimized for AVX2, AVX512, NEON or SVE.