crumsort-rs

August 18, 2022 · View on GitHub

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.

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

cargo run --release --example bench

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%

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%

This is not an officially supported Google product.