crumsort-rs

A parallelized Rust port of crumsort.

The goal of this port is to excel at sorting well-distributed data which is why it is not an exact 1:1 replica.

Temporary caveats

There are a few limitations given some of the constraints when this was originally written:

• sorts uniform data faster than crumsort, but severly skewed distributions slower (missing crumsort_analyze function)
• intended as a solution for sorting large (u64 or u128) integers
• only sorts Copy + Default data as a way to limit the use of unsafe
• missing un-parallelized version (data needs to implement Send)
• missing *_by and *_by_key sorting alternatives (data needs to implement Ord)

Please feel free to submit improvements in any of these area by submitting a pull request.

Benchmarks against parallel pdqsort (Rayon)

All banchmarks run with the bench example on an M1 Pro:

bash cargo run --release --example bench

Uniformly distributed random u32s

| Length | Algorithm | Throughput | Improvement | |:--------------:|:---------:|--------------:|------------:| | 2¹² | pdqsort | 32.15Mkeys/s | 0.00% | | 2¹² | crumsort | 38.70Mkeys/s | 20.39% | | 2¹⁶ | pdqsort | 129.96Mkeys/s | 0.00% | | 2¹⁶ | crumsort | 176.95Mkeys/s | 36.16% | | 2²⁰ | pdqsort | 226.31Mkeys/s | 0.00% | | 2²⁰ | crumsort | 368.09Mkeys/s | 62.65% | | 2²⁴ | pdqsort | 227.80Mkeys/s | 0.00% | | 2²⁴ | crumsort | 399.89Mkeys/s | 75.54% |

Uniformly distributed random u64s

| Length | Algorithm | Throughput | Improvement | |:--------------:|:---------:|--------------:|------------:| | 2¹² | pdqsort | 33.18Mkeys/s | 0.00% | | 2¹² | crumsort | 40.79Mkeys/s | 22.91% | | 2¹⁶ | pdqsort | 151.24Mkeys/s | 0.00% | | 2¹⁶ | crumsort | 237.48Mkeys/s | 57.02% | | 2²⁰ | pdqsort | 218.64Mkeys/s | 0.00% | | 2²⁰ | crumsort | 364.79Mkeys/s | 66.85% | | 2²⁴ | pdqsort | 226.83Mkeys/s | 0.00% | | 2²⁴ | crumsort | 385.42Mkeys/s | 69.92% |

Note

This is not an officially supported Google product.