Home

Awesome

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:

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:

cargo run --release --example bench

Uniformly distributed random u32s

LengthAlgorithmThroughputImprovement
2<sup>12</sup>pdqsort32.15Mkeys/s0.00%
2<sup>12</sup>crumsort38.70Mkeys/s20.39%
2<sup>16</sup>pdqsort129.96Mkeys/s0.00%
2<sup>16</sup>crumsort176.95Mkeys/s36.16%
2<sup>20</sup>pdqsort226.31Mkeys/s0.00%
2<sup>20</sup>crumsort368.09Mkeys/s62.65%
2<sup>24</sup>pdqsort227.80Mkeys/s0.00%
2<sup>24</sup>crumsort399.89Mkeys/s75.54%

Uniformly distributed random u64s

LengthAlgorithmThroughputImprovement
2<sup>12</sup>pdqsort33.18Mkeys/s0.00%
2<sup>12</sup>crumsort40.79Mkeys/s22.91%
2<sup>16</sup>pdqsort151.24Mkeys/s0.00%
2<sup>16</sup>crumsort237.48Mkeys/s57.02%
2<sup>20</sup>pdqsort218.64Mkeys/s0.00%
2<sup>20</sup>crumsort364.79Mkeys/s66.85%
2<sup>24</sup>pdqsort226.83Mkeys/s0.00%
2<sup>24</sup>crumsort385.42Mkeys/s69.92%

Note

This is not an officially supported Google product.