rdst 0.20.14

A flexible parallel unstable radix sort that supports sorting by any arbitrarily defined sequence of bytes.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

//! `StandardTuner` represents the default tuning of algorithm choices offered by rdst.
//!
//! StandardTuner algorithm choice is:
//!  * multi-threaded
//!  * aware of basic count distributions
//!  * dynamic msb / lsb

use crate::tuner::{Algorithm, Tuner, TuningParams};

pub struct StandardTuner;
impl Tuner for StandardTuner {
    #[inline]
    fn pick_algorithm(&self, p: &TuningParams, counts: &[usize]) -> Algorithm {
        if p.input_len <= 128 {
            return Algorithm::Comparative;
        }

        let depth = p.total_levels - p.level - 1;

        if p.input_len >= 5_000 {
            let distribution_threshold = (p.input_len / 256) * 2;

            for c in counts {
                if *c >= distribution_threshold {
                    return if depth == 0 {
                        match p.input_len {
                            0..=200_000 => Algorithm::LrLsb,
                            200_001..=350_000 => Algorithm::Ska,
                            350_001..=4_000_000 => Algorithm::MtLsb,
                            4_000_001..=usize::MAX => Algorithm::Regions,
                            _ => Algorithm::LrLsb,
                        }
                    } else {
                        match p.input_len {
                            0..=200_000 => Algorithm::LrLsb,
                            200_001..=800_000 => Algorithm::Ska,
                            800_001..=5_000_000 => Algorithm::Recombinating,
                            5_000_001..=usize::MAX => Algorithm::Regions,
                            _ => Algorithm::LrLsb,
                        }
                    };
                }
            }
        }

        if depth > 0 {
            match p.input_len {
                0..=200_000 => Algorithm::Lsb,
                200_001..=800_000 => Algorithm::Ska,
                800_001..=50_000_000 => Algorithm::Recombinating,
                50_000_001..=usize::MAX => Algorithm::Scanning,
                _ => Algorithm::Lsb,
            }
        } else {
            match p.input_len {
                0..=150_000 => Algorithm::Lsb,
                150_001..=260_000 => Algorithm::Ska,
                260_001..=50_000_000 => Algorithm::Recombinating,
                50_000_001..=usize::MAX => Algorithm::Scanning,
                _ => Algorithm::Lsb,
            }
        }
    }
}