Astro - Hacker News

6 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 an hour ago

It is so simple that I had to look very slowly to understand. Nicely done.
[-]
- NuclearPM an hour ago
  
  If it wasn’t simple you could look fast and understand?
mgaunard an hour ago

Aren't there several bitonic sort network implementations that are vectorized, Intel's in particular?
Why not compare against that?
[-]
- mswphd 33 minutes ago
  
  Funny: you can cf "sorting network", and see they use them within their own design even.
- jeffbee an hour 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.