Branchless Quicksort faster than std:sort and pdqsort with C and C++ API

3 comments

• orlp 27 minutes ago
  Since pdqsort (an older project of mine) was mentioned, I felt it wouldn't be entirely inappropriate to mention that I've since then collaborated with Lukas Bergdoll to provide two high-quality sort implementations for the Rust standard library, ipnsort (unstable) and driftsort (stable).

  So if you use Rust, you get these by simply calling [T]::sort(_unstable). Great performance out of the box :)

  On my machine (Apple M2), using the benchmarks from the repository on Apple clang 17 and Rust 1.98 nightly:

      Sorting 50 million doubles:
      ipnsort             0.79s
      blqs                0.90s
      driftsort           1.13s   (stable)
      std::sort           1.22s
      std::stable_sort    4.64s   (stable)
  
      Sorting 50 million (i32, i32) structs:
      ipnsort             0.82s
      blqs                0.89s
      driftsort           1.07s   (stable)
      std::sort           3.09s
      std::stable_sort    3.15s   (stable)
  
  

  And now for a cool party trick, let's repeat the 50 million doubles experiment again, but have the first 90% already sorted, last 10% random:

      driftsort           0.29s   (stable)
      ipnsort             0.81s
      std::sort           1.15s
      std::stable_sort    1.63s   (stable)
      blqs                1.89s
• davidkwast 1 hour ago
  It is so simple that I had to look very slowly to understand. Nicely done.
  [-]
  • NuclearPM 58 minutes ago
    If it wasn’t simple you could look fast and understand?
• mgaunard 1 hour ago
  Aren't there several bitonic sort network implementations that are vectorized, Intel's in particular?

  Why not compare against that?

  [-]
  • mswphd 32 minutes ago
    Funny: you can cf "sorting network", and see they use them within their own design even.
  • jeffbee 50 minutes ago
    Great question. It would also be fair to ask how this behaves with non-random inputs. The benchmarks in the repo only use random values.