4 ms·

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

kelthan 3y ago
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.
- mgaunard 3y ago
  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.
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 ago
  None of those are particularly optimized to make the most of the hardware capabilities though. The obvious thing is to use SIMD.
  - janwas 3y ago
    Vqsort is indeed using SIMD :)
    - mgaunard 3y ago
      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.
      - janwas 3y ago
        Measurements (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...
        mgaunard 3y ago
        Pretty impressive results on the new version of vqsort.
        janwas 3y ago
        Thanks :) We fixed a performance bug (re-seeding an RNG on each sort).
  - Voultapher 3y ago
    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/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.
    - 3y ago

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.

mgaunard 3y ago
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.

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 ago
None of those are particularly optimized to make the most of the hardware capabilities though. The obvious thing is to use SIMD.
- janwas 3y ago
  Vqsort is indeed using SIMD :)
  - mgaunard 3y ago
    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.
    - janwas 3y ago
      Measurements (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...
      - mgaunard 3y ago
        Pretty impressive results on the new version of vqsort.
        janwas 3y ago
        Thanks :) We fixed a performance bug (re-seeding an RNG on each sort).
- Voultapher 3y ago
  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/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.
  - 3y ago