mod.rs - source
Description: Source of the Rust file `library/core/src/slice/sort/unstable/mod.rs`.

#
core/slice/sort/unstable/
mod.rs

    1//! This module contains the entry points for `slice::sort_unstable`.
    2
    3use crate::mem::SizedTypeProperties;
    4use crate::ops::{Range, RangeBounds};
    5use crate::slice::sort::select::partition_at_index;
    6#[cfg(not(any(feature = "optimize_for_size", target_pointer_width = "16")))]
    7use crate::slice::sort::shared::find_existing_run;
    8#[cfg(not(any(feature = "optimize_for_size", target_pointer_width = "16")))]
    9use crate::slice::sort::shared::smallsort::insertion_sort_shift_left;
    10use crate::{cfg_select, intrinsics, slice};
    11
    12pub(crate) mod heapsort;
    13pub(crate) mod quicksort;
    14
    15/// Unstable sort called ipnsort by Lukas Bergdoll and Orson Peters.
    16/// Design document:
    17/// <https://github.com/Voultapher/sort-research-rs/blob/main/writeup/ipnsort_introduction/text.md>
    18///
    19/// Upholds all safety properties outlined here:
    20/// <https://github.com/Voultapher/sort-research-rs/blob/main/writeup/sort_safety/text.md>
    21#[inline(always)]
    22pub fn sort<T, F>(v: &mut [T], is_less: &mut F)
    23where
    24    F: FnMut(&T, &T) -> bool,
    25{
    26    // Arrays of zero-sized types are always all-equal, and thus sorted.
    27    if T::IS_ZST {
    28        return;
    29    }
    30
    31    // Instrumenting the standard library showed that 90+% of the calls to sort
    32    // by rustc are either of size 0 or 1.
    33    let len = v.len();
    34    if intrinsics::likely(len < 2) {
    35        return;
    36    }
    37
    38    cfg_select! {
    39        any(feature = "optimize_for_size", target_pointer_width = "16") => {
    40            heapsort::heapsort(v, is_less);
    41        }
    42        _ => {
    43            // More advanced sorting methods than insertion sort are faster if called in
    44            // a hot loop for small inputs, but for general-purpose code the small
    45            // binary size of insertion sort is more important. The instruction cache in
    46            // modern processors is very valuable, and for a single sort call in general
    47            // purpose code any gains from an advanced method are cancelled by i-cache
    48            // misses during the sort, and thrashing the i-cache for surrounding code.
    49            const MAX_LEN_ALWAYS_INSERTION_SORT: usize = 20;
    50            if intrinsics::likely(len <= MAX_LEN_ALWAYS_INSERTION_SORT) {
    51                insertion_sort_shift_left(v, 1, is_less);
    52                return;
    53            }
    54
    55            ipnsort(v, is_less);
    56        }
    57    }
    58}
    59
    60/// Unstable partial sort the range `start..end`, after which it's guaranteed that:
    61///
    62/// 1. Every element in `v[..start]` is smaller than or equal to
    63/// 2. Every element in `v[start..end]`, which is sorted, and smaller than or equal to
    64/// 3. Every element in `v[end..]`.
    65#[inline]
    66pub fn partial_sort<T, F, R>(v: &mut [T], range: R, mut is_less: F)
    67where
    68    F: FnMut(&T, &T) -> bool,
    69    R: RangeBounds<usize>,
    70{
    71    // Arrays of zero-sized types are always all-equal, and thus sorted.
    72    if T::IS_ZST {
    73        return;
    74    }
    75
    76    let len = v.len();
    77    let Range { start, end } = slice::range(range, ..len);
    78
    79    if end - start <= 1 {
    80        // Empty range or single element. This case can be resolved in at most
    81        // single partition_at_index call, without further sorting.
    82
    83        if end == 0 || start == len {
    84            // Do nothing if it is an empty range at start or end: all guarantees
    85            // are already upheld.
    86            return;
    87        }
    88
    89        partition_at_index(v, start, &mut is_less);
    90        return;
    91    }
    92
    93    // A heuristic factor to decide whether to partition the slice or not.
    94    // If the range bound is close to the edges of the slice, it's not worth
    95    // partitioning first.
    96    const PARTITION_THRESHOLD: usize = 8;
    97    let mut v = v;
    98    if end + PARTITION_THRESHOLD <= len {
    99        v = partition_at_index(v, end - 1, &mut is_less).0;
    100    }
    101    if start >= PARTITION_THRESHOLD {
    102        v = partition_at_index(v, start, &mut is_less).2;
    103    }
    104
    105    sort(v, &mut is_less);
    106}
    107
    108/// See [`sort`]
    109///
    110/// Deliberately don't inline the main sorting routine entrypoint to ensure the
    111/// inlined insertion sort i-cache footprint remains minimal.
    112#[cfg(not(any(feature = "optimize_for_size", target_pointer_width = "16")))]
    113#[inline(never)]
    114fn ipnsort<T, F>(v: &mut [T], is_less: &mut F)
    115where
    116    F: FnMut(&T, &T) -> bool,
    117{
    118    let len = v.len();
    119    let (run_len, was_reversed) = find_existing_run(v, is_less);
    120
    121    // SAFETY: find_existing_run promises to return a valid run_len.
    122    unsafe { intrinsics::assume(run_len <= len) };
    123
    124    if run_len == len {
    125        if was_reversed {
    126            v.reverse();
    127        }
    128
    129        // It would be possible to a do in-place merging here for a long existing streak. But that
    130        // makes the implementation a lot bigger, users can use `slice::sort` for that use-case.
    131        return;
    132    }
    133
    134    // Limit the number of imbalanced partitions to `2 * floor(log2(len))`.
    135    // The binary OR by one is used to eliminate the zero-check in the logarithm.
    136    let limit = 2 * (len | 1).ilog2();
    137    crate::slice::sort::unstable::quicksort::quicksort(v, None, limit, is_less);
    138}