diff options
| -rw-r--r-- | library/core/src/slice/sort/shared/smallsort.rs | 38 | ||||
| -rw-r--r-- | library/core/src/slice/sort/stable/merge.rs | 150 |
2 files changed, 98 insertions, 90 deletions
diff --git a/library/core/src/slice/sort/shared/smallsort.rs b/library/core/src/slice/sort/shared/smallsort.rs index 6e4424310e8..7cd351c9f25 100644 --- a/library/core/src/slice/sort/shared/smallsort.rs +++ b/library/core/src/slice/sort/shared/smallsort.rs @@ -94,9 +94,9 @@ impl<T: FreezeMarker> UnstableSmallSortTypeImpl for T { #[inline(always)] fn small_sort_threshold() -> usize { match const { choose_unstable_small_sort::<T>() } { - UnstalbeSmallSort::Fallback => SMALL_SORT_FALLBACK_THRESHOLD, - UnstalbeSmallSort::General => SMALL_SORT_GENERAL_THRESHOLD, - UnstalbeSmallSort::Network => SMALL_SORT_NETWORK_THRESHOLD, + UnstableSmallSort::Fallback => SMALL_SORT_FALLBACK_THRESHOLD, + UnstableSmallSort::General => SMALL_SORT_GENERAL_THRESHOLD, + UnstableSmallSort::Network => SMALL_SORT_NETWORK_THRESHOLD, } } @@ -137,34 +137,34 @@ const SMALL_SORT_NETWORK_SCRATCH_LEN: usize = SMALL_SORT_NETWORK_THRESHOLD; /// within this limit. const MAX_STACK_ARRAY_SIZE: usize = 4096; -enum UnstalbeSmallSort { +enum UnstableSmallSort { Fallback, General, Network, } -const fn choose_unstable_small_sort<T: FreezeMarker>() -> UnstalbeSmallSort { +const fn choose_unstable_small_sort<T: FreezeMarker>() -> UnstableSmallSort { if T::is_copy() && has_efficient_in_place_swap::<T>() && (mem::size_of::<T>() * SMALL_SORT_NETWORK_SCRATCH_LEN) <= MAX_STACK_ARRAY_SIZE { // Heuristic for int like types. - return UnstalbeSmallSort::Network; + return UnstableSmallSort::Network; } if (mem::size_of::<T>() * SMALL_SORT_GENERAL_SCRATCH_LEN) <= MAX_STACK_ARRAY_SIZE { - return UnstalbeSmallSort::General; + return UnstableSmallSort::General; } - UnstalbeSmallSort::Fallback + UnstableSmallSort::Fallback } const fn inst_unstable_small_sort<T: FreezeMarker, F: FnMut(&T, &T) -> bool>() -> fn(&mut [T], &mut F) { match const { choose_unstable_small_sort::<T>() } { - UnstalbeSmallSort::Fallback => small_sort_fallback::<T, F>, - UnstalbeSmallSort::General => small_sort_general::<T, F>, - UnstalbeSmallSort::Network => small_sort_network::<T, F>, + UnstableSmallSort::Fallback => small_sort_fallback::<T, F>, + UnstableSmallSort::General => small_sort_general::<T, F>, + UnstableSmallSort::Network => small_sort_network::<T, F>, } } @@ -384,8 +384,12 @@ where } } -// Never inline this function to avoid code bloat. It still optimizes nicely and has practically no -// performance impact. +/// Sorts the first 9 elements of `v` with a fast fixed function. +/// +/// Should `is_less` generate substantial amounts of code the compiler can choose to not inline +/// `swap_if_less`. If the code of a sort impl changes so as to call this function in multiple +/// places, `#[inline(never)]` is recommended to keep binary-size in check. The current design of +/// `small_sort_network` makes sure to only call this once. fn sort9_optimal<T, F>(v: &mut [T], is_less: &mut F) where F: FnMut(&T, &T) -> bool, @@ -429,8 +433,12 @@ where } } -// Never inline this function to avoid code bloat. It still optimizes nicely and has practically no -// performance impact. +/// Sorts the first 13 elements of `v` with a fast fixed function. +/// +/// Should `is_less` generate substantial amounts of code the compiler can choose to not inline +/// `swap_if_less`. If the code of a sort impl changes so as to call this function in multiple +/// places, `#[inline(never)]` is recommended to keep binary-size in check. The current design of +/// `small_sort_network` makes sure to only call this once. fn sort13_optimal<T, F>(v: &mut [T], is_less: &mut F) where F: FnMut(&T, &T) -> bool, diff --git a/library/core/src/slice/sort/stable/merge.rs b/library/core/src/slice/sort/stable/merge.rs index 4f6a98bc7b8..6739e114b13 100644 --- a/library/core/src/slice/sort/stable/merge.rs +++ b/library/core/src/slice/sort/stable/merge.rs @@ -61,91 +61,91 @@ pub fn merge<T, F: FnMut(&T, &T) -> bool>( // Finally, `merge_state` gets dropped. If the shorter run was not fully // consumed, whatever remains of it will now be copied into the hole in `v`. } +} - // When dropped, copies the range `start..end` into `dst..`. - struct MergeState<T> { - start: *mut T, - end: *mut T, - dst: *mut T, - } +// When dropped, copies the range `start..end` into `dst..`. +struct MergeState<T> { + start: *mut T, + end: *mut T, + dst: *mut T, +} - impl<T> MergeState<T> { - /// # Safety - /// The caller MUST guarantee that `self` is initialized in a way where `start -> end` is - /// the longer sub-slice and so that `dst` can be written to at least the shorter sub-slice - /// length times. In addition `start -> end` and `right -> right_end` MUST be valid to be - /// read. This function MUST only be called once. - unsafe fn merge_up<F: FnMut(&T, &T) -> bool>( - &mut self, - mut right: *const T, - right_end: *const T, - is_less: &mut F, - ) { - // SAFETY: See function safety comment. - unsafe { - let left = &mut self.start; - let out = &mut self.dst; - - while *left != self.end && right as *const T != right_end { - let consume_left = !is_less(&*right, &**left); - - let src = if consume_left { *left } else { right }; - ptr::copy_nonoverlapping(src, *out, 1); - - *left = left.add(consume_left as usize); - right = right.add(!consume_left as usize); - - *out = out.add(1); - } +impl<T> MergeState<T> { + /// # Safety + /// The caller MUST guarantee that `self` is initialized in a way where `start -> end` is + /// the longer sub-slice and so that `dst` can be written to at least the shorter sub-slice + /// length times. In addition `start -> end` and `right -> right_end` MUST be valid to be + /// read. This function MUST only be called once. + unsafe fn merge_up<F: FnMut(&T, &T) -> bool>( + &mut self, + mut right: *const T, + right_end: *const T, + is_less: &mut F, + ) { + // SAFETY: See function safety comment. + unsafe { + let left = &mut self.start; + let out = &mut self.dst; + + while *left != self.end && right as *const T != right_end { + let consume_left = !is_less(&*right, &**left); + + let src = if consume_left { *left } else { right }; + ptr::copy_nonoverlapping(src, *out, 1); + + *left = left.add(consume_left as usize); + right = right.add(!consume_left as usize); + + *out = out.add(1); } } + } - /// # Safety - /// The caller MUST guarantee that `self` is initialized in a way where `left_end <- dst` is - /// the shorter sub-slice and so that `out` can be written to at least the shorter sub-slice - /// length times. In addition `left_end <- dst` and `right_end <- end` MUST be valid to be - /// read. This function MUST only be called once. - unsafe fn merge_down<F: FnMut(&T, &T) -> bool>( - &mut self, - left_end: *const T, - right_end: *const T, - mut out: *mut T, - is_less: &mut F, - ) { - // SAFETY: See function safety comment. - unsafe { - loop { - let left = self.dst.sub(1); - let right = self.end.sub(1); - out = out.sub(1); - - let consume_left = is_less(&*right, &*left); - - let src = if consume_left { left } else { right }; - ptr::copy_nonoverlapping(src, out, 1); - - self.dst = left.add(!consume_left as usize); - self.end = right.add(consume_left as usize); - - if self.dst as *const T == left_end || self.end as *const T == right_end { - break; - } + /// # Safety + /// The caller MUST guarantee that `self` is initialized in a way where `left_end <- dst` is + /// the shorter sub-slice and so that `out` can be written to at least the shorter sub-slice + /// length times. In addition `left_end <- dst` and `right_end <- end` MUST be valid to be + /// read. This function MUST only be called once. + unsafe fn merge_down<F: FnMut(&T, &T) -> bool>( + &mut self, + left_end: *const T, + right_end: *const T, + mut out: *mut T, + is_less: &mut F, + ) { + // SAFETY: See function safety comment. + unsafe { + loop { + let left = self.dst.sub(1); + let right = self.end.sub(1); + out = out.sub(1); + + let consume_left = is_less(&*right, &*left); + + let src = if consume_left { left } else { right }; + ptr::copy_nonoverlapping(src, out, 1); + + self.dst = left.add(!consume_left as usize); + self.end = right.add(consume_left as usize); + + if self.dst as *const T == left_end || self.end as *const T == right_end { + break; } } } } +} - impl<T> Drop for MergeState<T> { - fn drop(&mut self) { - // SAFETY: The user of MergeState MUST ensure, that at any point this drop - // impl MAY run, for example when the user provided `is_less` panics, that - // copying the contiguous region between `start` and `end` to `dst` will - // leave the input slice `v` with each original element and all possible - // modifications observed. - unsafe { - let len = self.end.sub_ptr(self.start); - ptr::copy_nonoverlapping(self.start, self.dst, len); - } +impl<T> Drop for MergeState<T> { + fn drop(&mut self) { + // SAFETY: The user of MergeState MUST ensure, that at any point this drop + // impl MAY run, for example when the user provided `is_less` panics, that + // copying the contiguous region between `start` and `end` to `dst` will + // leave the input slice `v` with each original element and all possible + // modifications observed. + unsafe { + let len = self.end.sub_ptr(self.start); + ptr::copy_nonoverlapping(self.start, self.dst, len); } } } |