Crate voracious_radix_sort

source ·
Expand description

Voracious sort

Voracious sort is a sorting algorithm, like Rust standard sort or Rust unstable sort. However it is a radix sort, it is a non comparative sort. It is a very fast sort which compares very well against Rust standard and unstable sorts or others state of the art sorting algorithms (see runtimes below).

Voracious sort can sort a vector or a slice of:

  • bool
  • char
  • f32, f64
  • i8, i16, i32, i64, i128
  • isize
  • u8, u16, u32, u64, u128
  • usize
  • struct
    • The struct must be mapped to a key. The key must be among the aforementioned types (bool, char, f32, etc…).
    • Single thread version: the struct must implement PartialOrd, PartialEq, Copy and Radixable traits.
    • Multi thread version: the struct must implement PartialOrd, PartialEq, Copy, Send, Sync and Radixable traits.

Vocarious sort can only sort in ascending order. You can call the reverse method if desired.

Because of Rust Orphan Rule, we chose not to support tuple sorting. You can use struct instead.

Version

Last version tested/used:

  • Rustc: 1.46.0 stable
  • Rustfmt: 1.4.18 stable
  • Cargo: 1.46.0 stable
  • Clippy: 0.0.212

License

See the license file.

How to use it

Add in Cargo.toml if you want only single thread version:

[dependencies]
voracious_radix_sort = { version = "1.2.0" }

If you also want the multithread version:

[dependencies]
voracious_radix_sort = { version = "1.2.0", features = ["voracious_multithread"] }

Environment variable

To fully benefit from Voracious sort, it is better to add the environment variable:

export RUSTFLAGS="-C target-cpu=native"

Methods

When the Crate is imported, three methods are added to vectors and slices:

  • voracious_sort() (single thread).
  • voracious_stable_sort() (single thread).
  • voracious_mt_sort() (multi thread). (with the “voracious_multithread” feature)

Example

ⓘ
use voracious_radix_sort::{RadixSort};

let mut array = vec![2, 45, 8, 7, 9, 65, 8, 74, 1, 2, 56, 9, 7, 41];

array.voracious_sort();

assert_eq!(array, vec![1, 2, 2, 7, 7, 8, 8, 9, 9, 41, 45, 56, 65, 74]);

let mut array = vec![2, 45, 8, 7, 9, 65, 8, 74, 1, 2, 56, 9, 7, 41];

array.voracious_stable_sort();

assert_eq!(array, vec![1, 2, 2, 7, 7, 8, 8, 9, 9, 41, 45, 56, 65, 74]);

let mut array = vec![2, 45, 8, 7, 9, 65, 8, 74, 1, 2, 56, 9, 7, 41];

// mt: Multithread sort.
// The argument is the number of threads for the threadpool.
array.voracious_mt_sort(4);

assert_eq!(array, vec![1, 2, 2, 7, 7, 8, 8, 9, 9, 41, 45, 56, 65, 74]);

Implementing a custom struct

Let’s do it through an example.

use std::cmp::Ordering;

// We need a struct.
// We want, for example, to sort these structs by the key: "value".
// This struct must implement the Copy and Clone traits, we can just derive them.
// For the multithread version the struct must implement de `Send` and `Sync` traits
// too, which are by default for primitive types.
#[derive(Copy, Clone, Debug)]
pub struct Custom {
    value: f32,
    other: usize,
}
impl PartialOrd for Custom {
    fn partial_cmp(&self, other: &Custom) -> Option<Ordering> {
        self.value.partial_cmp(&other.value)
    }
}
impl PartialEq for Custom {
    fn eq(&self, other: &Self) -> bool {
        self.value == other.value
    }
}

And then we have to implement the Radixable traits:

use voracious_radix_sort::Radixable;

impl Radixable<f32> for Custom {
    type Key = f32;
    #[inline]
    fn key(&self) -> Self::Key {
        self.value
    }
}

See more implementation examples on our GitHub

When it is done, we can run a test:

use voracious_radix_sort::RadixSort;

let mut array = vec![
    Custom { value: 5.7, other: 29 },
    Custom { value: 2.7, other: 23 },
    Custom { value: 14.7, other: 17 },
    Custom { value: 4.7, other: 35 },
];

array.voracious_sort();

assert_eq!(array, vec![
    Custom { value: 2.7, other: 23 },
    Custom { value: 4.7, other: 35 },
    Custom { value: 5.7, other: 29 },
    Custom { value: 14.7, other: 17 },
]);

let mut array = vec![
    Custom { value: 5.7, other: 29 },
    Custom { value: 2.7, other: 23 },
    Custom { value: 14.7, other: 17 },
    Custom { value: 4.7, other: 35 },
];

let mut array = vec![
    Custom { value: 5.7, other: 29 },
    Custom { value: 2.7, other: 23 },
    Custom { value: 14.7, other: 17 },
    Custom { value: 4.7, other: 35 },
];

let mut array = vec![
    Custom { value: 5.7, other: 29 },
    Custom { value: 2.7, other: 23 },
    Custom { value: 14.7, other: 17 },
    Custom { value: 4.7, other: 35 },
];

array.voracious_stable_sort();

assert_eq!(array, vec![
    Custom { value: 2.7, other: 23 },
    Custom { value: 4.7, other: 35 },
    Custom { value: 5.7, other: 29 },
    Custom { value: 14.7, other: 17 },
]);

Panics

For f32 and f64, if there is a NaN value or an INFINITY or a NEG_INFINITY in the vector or the slice, the behavior is not guaranteed.

It might panic or not sort correctly the array.

Dependencies

  • Rayon 1.5.0 (threadpool). This dependency is optional. If you use only the single thread version, you don’t need it. If you want to use the multithread version, you will need it.

Performances

  • First, please, read: PROFILING.md.
  • These results are from the v1.0.0 version. It might vary a bit with v1.1.0.
  • Performances can vary depending on the profile you are using.
  • Please notice that dedicated sorts are faster than generic sorts.
  • Tests have been done on an AMD Ryzen 9 3950x, 32GB DDR4 RAM, MB X570 TUF Gaming.
  • For more benchmarks, please visit our GitHub.
  • Times are in micro seconde.
  • Since this crate outperforms all the other Rust sorting crates, only Rust standard sorts and Rayon sorts are used in the benchmarks. Since Rust Unstable sort is actually a PDQ sort, it can be considered as a gold standard.

For u32 (Distribution: Normal sd=2^20)

Array sizeVoraciousRust UnstableArray sizeVoracious MTRayon Par Uns
5009 us10 us1_000_0003_299 us3_250 us
1_00013 us22 us5_000_0009_819 us16_662 us
10_00075 us209 us10_000_00013_784 us34_578 us
50_000359 us1_316 us20_000_00021_277 us69_020 us
100_000717 us2_293 us50_000_00056_346 us177_085 us
500_0003_663 us12_927 us100_000_000119_500 us366_164 us
1_000_0006_596 us24_879 us200_000_000231_974 us798_497 us
10_000_00079_342 us263_105 us

For u64 (Distribution: Normal sd=2^30)

Array sizeVoraciousRust UnstableArray sizeVoracious MTRayon Par Uns
50010 us11 us1_000_0003_407 us3_375 us
1_00015 us23 us5_000_00015_090 us19_564 us
10_00091 us208 us10_000_00022_679 us40_165 us
50_000434 us1_140 us20_000_00066_907 us84_991 us
100_0001_040 us2_402 us50_000_000118_142 us241_001 us
500_0004_830 us13_067 us100_000_000234_282 us525_917 us
1_000_00010_037 us26_009 us200_000_000511_266 us1_159_379 us
10_000_000111_603 us296_762 us

For f32 (Distribution: Normal sd=2^20)

Array sizeVoraciousRust UnstableArray sizeVoracious MTRayon Par Uns
50017 us18 us1_000_0009_877 us10_271 us
1_00024 us39 us5_000_00016_135 us53_146 us
10_000117 us412 us10_000_00019_603 us110_428 us
50_000602 us3_075 us20_000_00040_954 us220_620 us
100_0001_118 us6_617 us50_000_000119_278 us547_547 us
500_0005_634 us31_434 us100_000_000192_523 us1_117_997 us
1_000_00010_668 us64_040 us200_000_000340_500 us2_208_494 us
10_000_00098_425 us772_269 us

For f64 (Distribution: Normal sd=2^30)

Array sizeVoraciousRust UnstableArray sizeVoracious MTRayon Par Uns
50017 us19 us1_000_0006_784 us10_588 us
1_00035 us40 us5_000_00022_044 us60_965 us
10_000146 us499 us10_000_00034_392 us124_281 us
50_000805 us2_603 us20_000_00058_670 us240_250 us
100_0001_750 us5_386 us50_000_000168_876 us618_027 us
500_0007_584 us30_667 us100_000_000295_038 us1_234_928 us
1_000_00014_453 us70_118 us200_000_000608_247 us2_523_838 us
10_000_000168_004 us868_874 us

For i32 (Distribution: Normal sd=2^20)

Array sizeVoraciousRust UnstableArray sizeVoracious MTRayon Par Uns
50011 us11 us1_000_0003_447 us3_443 us
1_00023 us23 us5_000_00011_331 us17_511 us
10_000134 us212 us10_000_00016_271 us34_221 us
50_000627 us1_028 us20_000_00034_267 us70_053 us
100_0001_182 us2_415 us50_000_00071_629 us178_771 us
500_0005_456 us11_992 us100_000_000147_718 us390_487 us
1_000_00011_765 us26_072 us200_000_000300_494 us796_938 us
10_000_000104_127 us287_329 us

For i64 (Distribution: Normal sd=2^30)

Array sizeVoraciousRust UnstableArray sizeVoracious MTRayon Par Uns
50012 us11 us1_000_0003_487 us3_724 us
1_00023 us23 us5_000_00019_264 us19_840 us
10_000199 us210 us10_000_00045_942 us42_359 us
50_0001_021 us1_067 us20_000_00077_951 us86_229 us
100_0001_730 us2_403 us50_000_000176_850 us241_632 us
500_0008_853 us13_072 us100_000_000381_320 us547_322 us
1_000_00016_285 us26_547 us200_000_000819_088 us1_154_061 us
10_000_000170_758 us301_531 us

For Developers

Implementation details

Using native functions

As you can see, not only traits are exposed, but also native sorting functions. That way you can do whatever you want as long as you know what you are doing.

Using another value than 8 for the radix is your responsibility.

I can ensure you that sorting with the trait methods is correct (erk I hope ^_^). But if you play with native functions, it is up to you not to do mischief.

Since profiling is not finished. You might need to work a bit more by doing your own profiling. For this purpose, I highly recommend you to clone the github project and use the provided benchmark.

Traits

Functions