Crate voracious_radix_sort

Voracious sort

Voracious sort is a sort 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 (Counting sort),
• char (Behave like u32),
• f32, f64 (See link),
• i8, i16, i32, i64, i128 (First bit is flipped),
• u8, u16, u32, u64, u128 (Native implementation),
• Custom struct if a the struct implements PartialOrd, PartialEq and Copy (and thus, Clone trait too) traits and Radixable trait (see below) (Mapped to a key).

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.41.1 stable
• Rustfmt: 1.4.11 stable
• Cargo: 1.41.0 stable
• Clippy: 0.0.212

License

See the license file.

How to use it

Add in Cargo.toml:

[dependencies]
voracious_radix_sort = "0.1.0"

Environment variable

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

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

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

• voracious_sort() (single thread).
• voracious_stable_sort() (single thread).

Example

use voracious_radix_sort::*;

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]);

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.
#[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 trait:

use voracious_radix_sort::*;

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::*;

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 },
];

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

There is no dependency.

Performances

• All tests have been done on a i5 7500 3.4GHz 6MB cache L3 with 40GB DDR4 RAM (November 2019) with RUSTFLAGS="-C target-cpu=native".

• Only one run has been done by test.

• For more runtimes, please visit our GitHub.

• Times are in micro seconde.

• In order to have a very user friendly crate, sorts might be a little less faster than dedicated sort by type.

• CAUTION: Performance tests have been done on a previous version of the code.

• *RdxSort version 0.3.0

• *AfSort version 0.3.1

For u64 100_000_000 integers

Distribution	Voracious	DLSD	Rust Std	Rust Unstable	RdxSort*	AFSort*
Uniform	1_969_984	1_393_206	10_124_103	3_372_091	2_842_670	4_060_710
Zipf	352_684	1_315_713	5_584_313	331_330	5_587_266	2_155_202
Normal (SD 10^6)	1_863_536	3_008_335	9_675_911	2_454_208	3_874_521	4_482_161

For f64 100_000_000 floats

Distribution	Voracious	DLSD	Rust Std	Rust Unstable	RdxSort*	AFSort*
Uniform	2_358_032	2_873_768	14_247_551	7_108_842	4_548_991	N/A
Zipf	2_198_049	1_221_660	6_435_186	805_088	6_242_734	N/A
Normal (SD 10^6)	2_357_697	2_334_541	14_049_225	7_109_580	4_309_830	N/A

For i64 100_000_000 integers

Distribution	Voracious	DLSD	Rust Std	Rust Unstable	RdxSort*	AFSort*
Uniform	2_037_479	1_347_168	9_932_912	3_516_609	3_302_737	N/A
Zipf	401_947	1_287_534	5_499_072	320_038	5_807_618	N/A
Normal (SD 10^6)	1_856_729	3_039_194	9_821_670	2_602_098	4_225_584	N/A

For char 100_000_000 chars

Distribution	Voracious	DLSD	Rust Std	Rust Unstable	RdxSort*	AFSort*
Uniform	777_537	802_939	6_116_985	1_813_057	1_933_041	N/A
All Equal	47_914	47_929	47_488	41_212	2_229_338	N/A
Small CharSet	114_896	394_616	6_197_632	689_738	2_006_239	N/A
Medium CharSet	113_521	622_184	6_144_734	629_989	1_982_256	N/A
Big CharSet	867_986	857_884	6_169_368	727_749	2_029_007	N/A

For Developers and Researchers

Logic

• Voracious sort is a MSD radix sort. It is an improvement of the Ska sort and it uses the Verge sort pre-processing heuristic. Depending on the type and the input size, another sort might be choosen (LSD sort, Counting sort, etc...). The purpose is to implement a multithread radix sort (see Regions sort and the article).

• DLSD (Diverting LSD radix sort) is a simpler version of the DFR sort with a different diversion and a variable radix (see article).

• All sorts fallback on the PDQ sort (Rust Unstable sort) for very small inputs (or Rust stable sort).

Future work

• Add multithread sort.
• Improve k-way-merge algorithm.
• Add more generators (for tests).
• Add a sort for String.

Re-exports

pub use traits::dispatcher::Dispatcher;

pub use traits::radix_key::RadixKey;

pub use traits::radixable::Radixable;

pub use traits::radixsort::RadixSort;

Modules

traits

Functions

american_flag_sort	American flag sort
boolean_sort	Boolean sort
counting_sort	Counting sort
ded_lsd_radixsort
dlsd_radixsort	DLSD sort: Diverting LSD sort
insertion_sort	Insertion sort
lsd_radixsort	LSD sort
msd_radixsort	MSD sort
msd_stable_radixsort	MSD stable sort
ska_sort	Ska sort
thiel_radixsort	Thiel sort
voracious_sort	Voracious sort