diff options
Diffstat (limited to 'library/alloc/src/slice.rs')
| -rw-r--r-- | library/alloc/src/slice.rs | 209 |
1 files changed, 101 insertions, 108 deletions
diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs index ebe6f7e7caa..104f4ee753b 100644 --- a/library/alloc/src/slice.rs +++ b/library/alloc/src/slice.rs @@ -16,7 +16,7 @@ use core::borrow::{Borrow, BorrowMut}; #[cfg(not(no_global_oom_handling))] use core::cmp::Ordering::{self, Less}; #[cfg(not(no_global_oom_handling))] -use core::mem::{self, SizedTypeProperties}; +use core::mem::{self, MaybeUninit}; #[cfg(not(no_global_oom_handling))] use core::ptr; #[cfg(not(no_global_oom_handling))] @@ -24,7 +24,7 @@ use core::slice::sort; use crate::alloc::Allocator; #[cfg(not(no_global_oom_handling))] -use crate::alloc::{self, Global}; +use crate::alloc::Global; #[cfg(not(no_global_oom_handling))] use crate::borrow::ToOwned; use crate::boxed::Box; @@ -174,23 +174,32 @@ pub(crate) mod hack { #[cfg(not(test))] impl<T> [T] { - /// Sorts the slice. + /// Sorts the slice, preserving initial order of equal elements. /// - /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. + /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) + /// worst-case. + /// + /// If `T: Ord` does not implement a total order the resulting order is unspecified. All + /// original elements will remain in the slice and any possible modifications via interior + /// mutability are observed in the input. Same is true if `T: Ord` panics. /// /// When applicable, unstable sorting is preferred because it is generally faster than stable - /// sorting and it doesn't allocate auxiliary memory. - /// See [`sort_unstable`](slice::sort_unstable). + /// sorting and it doesn't allocate auxiliary memory. See + /// [`sort_unstable`](slice::sort_unstable). The exception are partially sorted slices, which + /// may be better served with `slice::sort`. /// /// # Current implementation /// - /// The current algorithm is an adaptive, iterative merge sort inspired by - /// [timsort](https://en.wikipedia.org/wiki/Timsort). - /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of - /// two or more sorted sequences concatenated one after another. + /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which + /// combines the fast average case of quicksort with the fast worst case and partial run + /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs + /// with k distinct elements, the expected time to sort the data is *O(*n* log(*k*))*. + /// + /// The auxiliary memory allocation behavior depends on the input length. Short slices are + /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it + /// clamps at `self.len() / 2`. /// - /// Also, it allocates temporary storage half the size of `self`, but for short slices a - /// non-allocating insertion sort is used instead. + /// If `T: Ord` does not implement a total order, the implementation may panic. /// /// # Examples /// @@ -200,6 +209,8 @@ impl<T> [T] { /// v.sort(); /// assert!(v == [-5, -3, 1, 2, 4]); /// ``` + /// + /// [driftsort]: https://github.com/Voultapher/driftsort #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] @@ -211,13 +222,18 @@ impl<T> [T] { stable_sort(self, T::lt); } - /// Sorts the slice with a comparator function. + /// Sorts the slice with a comparator function, preserving initial order of equal elements. + /// + /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) + /// worst-case. /// - /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case. + /// The comparator function should define a total ordering for the elements in the slice. If the + /// ordering is not total, the order of the elements is unspecified. /// - /// The comparator function must define a total ordering for the elements in the slice. If - /// the ordering is not total, the order of the elements is unspecified. An order is a - /// total order if it is (for all `a`, `b` and `c`): + /// If the comparator function does not implement a total order the resulting order is + /// unspecified. All original elements will remain in the slice and any possible modifications + /// via interior mutability are observed in the input. Same is true if the comparator function + /// panics. A total order (for all `a`, `b` and `c`): /// /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. @@ -227,23 +243,22 @@ impl<T> [T] { /// /// ``` /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0]; - /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap()); + /// floats.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap()); /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]); /// ``` /// - /// When applicable, unstable sorting is preferred because it is generally faster than stable - /// sorting and it doesn't allocate auxiliary memory. - /// See [`sort_unstable_by`](slice::sort_unstable_by). - /// /// # Current implementation /// - /// The current algorithm is an adaptive, iterative merge sort inspired by - /// [timsort](https://en.wikipedia.org/wiki/Timsort). - /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of - /// two or more sorted sequences concatenated one after another. + /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which + /// combines the fast average case of quicksort with the fast worst case and partial run + /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs + /// with k distinct elements, the expected time to sort the data is *O(*n* log(*k*))*. + /// + /// The auxiliary memory allocation behavior depends on the input length. Short slices are + /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it + /// clamps at `self.len() / 2`. /// - /// Also, it allocates temporary storage half the size of `self`, but for short slices a - /// non-allocating insertion sort is used instead. + /// If `T: Ord` does not implement a total order, the implementation may panic. /// /// # Examples /// @@ -256,6 +271,8 @@ impl<T> [T] { /// v.sort_by(|a, b| b.cmp(a)); /// assert!(v == [5, 4, 3, 2, 1]); /// ``` + /// + /// [driftsort]: https://github.com/Voultapher/driftsort #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] @@ -267,28 +284,27 @@ impl<T> [T] { stable_sort(self, |a, b| compare(a, b) == Less); } - /// Sorts the slice with a key extraction function. + /// Sorts the slice with a key extraction function, preserving initial order of equal elements. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*)) /// worst-case, where the key function is *O*(*m*). /// - /// For expensive key functions (e.g. functions that are not simple property accesses or - /// basic operations), [`sort_by_cached_key`](slice::sort_by_cached_key) is likely to be - /// significantly faster, as it does not recompute element keys. - /// - /// When applicable, unstable sorting is preferred because it is generally faster than stable - /// sorting and it doesn't allocate auxiliary memory. - /// See [`sort_unstable_by_key`](slice::sort_unstable_by_key). + /// If `K: Ord` does not implement a total order the resulting order is unspecified. + /// All original elements will remain in the slice and any possible modifications via interior + /// mutability are observed in the input. Same is true if `K: Ord` panics. /// /// # Current implementation /// - /// The current algorithm is an adaptive, iterative merge sort inspired by - /// [timsort](https://en.wikipedia.org/wiki/Timsort). - /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of - /// two or more sorted sequences concatenated one after another. + /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which + /// combines the fast average case of quicksort with the fast worst case and partial run + /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs + /// with k distinct elements, the expected time to sort the data is *O(*n* log(*k*))*. + /// + /// The auxiliary memory allocation behavior depends on the input length. Short slices are + /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it + /// clamps at `self.len() / 2`. /// - /// Also, it allocates temporary storage half the size of `self`, but for short slices a - /// non-allocating insertion sort is used instead. + /// If `K: Ord` does not implement a total order, the implementation may panic. /// /// # Examples /// @@ -298,6 +314,8 @@ impl<T> [T] { /// v.sort_by_key(|k| k.abs()); /// assert!(v == [1, 2, -3, 4, -5]); /// ``` + /// + /// [driftsort]: https://github.com/Voultapher/driftsort #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_key", since = "1.7.0")] @@ -310,27 +328,30 @@ impl<T> [T] { stable_sort(self, |a, b| f(a).lt(&f(b))); } - /// Sorts the slice with a key extraction function. + /// Sorts the slice with a key extraction function, preserving initial order of equal elements. /// - /// During sorting, the key function is called at most once per element, by using - /// temporary storage to remember the results of key evaluation. - /// The order of calls to the key function is unspecified and may change in future versions - /// of the standard library. + /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \* + /// log(*n*)) worst-case, where the key function is *O*(*m*). /// - /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \* log(*n*)) - /// worst-case, where the key function is *O*(*m*). + /// During sorting, the key function is called at most once per element, by using temporary + /// storage to remember the results of key evaluation. The order of calls to the key function is + /// unspecified and may change in future versions of the standard library. + /// + /// If `K: Ord` does not implement a total order the resulting order is unspecified. + /// All original elements will remain in the slice and any possible modifications via interior + /// mutability are observed in the input. Same is true if `K: Ord` panics. /// - /// For simple key functions (e.g., functions that are property accesses or - /// basic operations), [`sort_by_key`](slice::sort_by_key) is likely to be - /// faster. + /// For simple key functions (e.g., functions that are property accesses or basic operations), + /// [`sort_by_key`](slice::sort_by_key) is likely to be faster. /// /// # Current implementation /// - /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, - /// which combines the fast average case of randomized quicksort with the fast worst case of - /// heapsort, while achieving linear time on slices with certain patterns. It uses some - /// randomization to avoid degenerate cases, but with a fixed seed to always provide - /// deterministic behavior. + /// The current implementation is based on [instruction-parallel-network sort][ipnsort] by Lukas + /// Bergdoll, which combines the fast average case of randomized quicksort with the fast worst + /// case of heapsort, while achieving linear time on fully sorted and reversed inputs. And + /// *O*(*k* \* log(*n*)) where *k* is the number of distinct elements in the input. It leverages + /// superscalar out-of-order execution capabilities commonly found in CPUs, to efficiently + /// perform the operation. /// /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the /// length of the slice. @@ -344,7 +365,7 @@ impl<T> [T] { /// assert!(v == [-3, -5, 2, 32, 4]); /// ``` /// - /// [pdqsort]: https://github.com/orlp/pdqsort + /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")] @@ -361,7 +382,7 @@ impl<T> [T] { $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect(); // The elements of `indices` are unique, as they are indexed, so any sort will be // stable with respect to the original slice. We use `sort_unstable` here because - // it requires less memory allocation. + // it requires no memory allocation. indices.sort_unstable(); for i in 0..$slice.len() { let mut index = indices[i].1; @@ -374,24 +395,24 @@ impl<T> [T] { }}; } - let sz_u8 = mem::size_of::<(K, u8)>(); - let sz_u16 = mem::size_of::<(K, u16)>(); - let sz_u32 = mem::size_of::<(K, u32)>(); - let sz_usize = mem::size_of::<(K, usize)>(); - let len = self.len(); if len < 2 { return; } - if sz_u8 < sz_u16 && len <= (u8::MAX as usize) { - return sort_by_key!(u8, self, f); - } - if sz_u16 < sz_u32 && len <= (u16::MAX as usize) { - return sort_by_key!(u16, self, f); - } - if sz_u32 < sz_usize && len <= (u32::MAX as usize) { + + // Avoids binary-size usage in cases where the alignment doesn't work out to make this + // beneficial or on 32-bit platforms. + let is_using_u32_as_idx_type_helpful = + const { mem::size_of::<(K, u32)>() < mem::size_of::<(K, usize)>() }; + + // It's possible to instantiate this for u8 and u16 but, doing so is very wasteful in terms + // of compile-times and binary-size, the peak saved heap memory for u16 is (u8 + u16) -> 4 + // bytes * u16::MAX vs (u8 + u32) -> 8 bytes * u16::MAX, the saved heap memory is at peak + // ~262KB. + if is_using_u32_as_idx_type_helpful && len <= (u32::MAX as usize) { return sort_by_key!(u32, self, f); } + sort_by_key!(usize, self, f) } @@ -843,46 +864,18 @@ fn stable_sort<T, F>(v: &mut [T], mut is_less: F) where F: FnMut(&T, &T) -> bool, { - if T::IS_ZST { - // Sorting has no meaningful behavior on zero-sized types. Do nothing. - return; - } + use sort::stable::BufGuard; - let elem_alloc_fn = |len: usize| -> *mut T { - // SAFETY: Creating the layout is safe as long as merge_sort never calls this with len > - // v.len(). Alloc in general will only be used as 'shadow-region' to store temporary swap - // elements. - unsafe { alloc::alloc(alloc::Layout::array::<T>(len).unwrap_unchecked()) as *mut T } - }; - - let elem_dealloc_fn = |buf_ptr: *mut T, len: usize| { - // SAFETY: Creating the layout is safe as long as merge_sort never calls this with len > - // v.len(). The caller must ensure that buf_ptr was created by elem_alloc_fn with the same - // len. - unsafe { - alloc::dealloc(buf_ptr as *mut u8, alloc::Layout::array::<T>(len).unwrap_unchecked()); - } - }; - - let run_alloc_fn = |len: usize| -> *mut sort::TimSortRun { - // SAFETY: Creating the layout is safe as long as merge_sort never calls this with an - // obscene length or 0. - unsafe { - alloc::alloc(alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked()) - as *mut sort::TimSortRun + #[unstable(issue = "none", feature = "std_internals")] + impl<T> BufGuard<T> for Vec<T> { + fn with_capacity(capacity: usize) -> Self { + Vec::with_capacity(capacity) } - }; - let run_dealloc_fn = |buf_ptr: *mut sort::TimSortRun, len: usize| { - // SAFETY: The caller must ensure that buf_ptr was created by elem_alloc_fn with the same - // len. - unsafe { - alloc::dealloc( - buf_ptr as *mut u8, - alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked(), - ); + fn as_uninit_slice_mut(&mut self) -> &mut [MaybeUninit<T>] { + self.spare_capacity_mut() } - }; + } - sort::merge_sort(v, &mut is_less, elem_alloc_fn, elem_dealloc_fn, run_alloc_fn, run_dealloc_fn); + sort::stable::sort::<T, F, Vec<T>>(v, &mut is_less); } |