diff options
Diffstat (limited to 'src/libcore/slice/rotate.rs')
| -rw-r--r-- | src/libcore/slice/rotate.rs | 182 |
1 files changed, 0 insertions, 182 deletions
diff --git a/src/libcore/slice/rotate.rs b/src/libcore/slice/rotate.rs deleted file mode 100644 index a89596b15ef..00000000000 --- a/src/libcore/slice/rotate.rs +++ /dev/null @@ -1,182 +0,0 @@ -// ignore-tidy-undocumented-unsafe - -use crate::cmp; -use crate::mem::{self, MaybeUninit}; -use crate::ptr; - -/// Rotates the range `[mid-left, mid+right)` such that the element at `mid` becomes the first -/// element. Equivalently, rotates the range `left` elements to the left or `right` elements to the -/// right. -/// -/// # Safety -/// -/// The specified range must be valid for reading and writing. -/// -/// # Algorithm -/// -/// Algorithm 1 is used for small values of `left + right` or for large `T`. The elements are moved -/// into their final positions one at a time starting at `mid - left` and advancing by `right` steps -/// modulo `left + right`, such that only one temporary is needed. Eventually, we arrive back at -/// `mid - left`. However, if `gcd(left + right, right)` is not 1, the above steps skipped over -/// elements. For example: -/// ```text -/// left = 10, right = 6 -/// the `^` indicates an element in its final place -/// 6 7 8 9 10 11 12 13 14 15 . 0 1 2 3 4 5 -/// after using one step of the above algorithm (The X will be overwritten at the end of the round, -/// and 12 is stored in a temporary): -/// X 7 8 9 10 11 6 13 14 15 . 0 1 2 3 4 5 -/// ^ -/// after using another step (now 2 is in the temporary): -/// X 7 8 9 10 11 6 13 14 15 . 0 1 12 3 4 5 -/// ^ ^ -/// after the third step (the steps wrap around, and 8 is in the temporary): -/// X 7 2 9 10 11 6 13 14 15 . 0 1 12 3 4 5 -/// ^ ^ ^ -/// after 7 more steps, the round ends with the temporary 0 getting put in the X: -/// 0 7 2 9 4 11 6 13 8 15 . 10 1 12 3 14 5 -/// ^ ^ ^ ^ ^ ^ ^ ^ -/// ``` -/// Fortunately, the number of skipped over elements between finalized elements is always equal, so -/// we can just offset our starting position and do more rounds (the total number of rounds is the -/// `gcd(left + right, right)` value). The end result is that all elements are finalized once and -/// only once. -/// -/// Algorithm 2 is used if `left + right` is large but `min(left, right)` is small enough to -/// fit onto a stack buffer. The `min(left, right)` elements are copied onto the buffer, `memmove` -/// is applied to the others, and the ones on the buffer are moved back into the hole on the -/// opposite side of where they originated. -/// -/// Algorithms that can be vectorized outperform the above once `left + right` becomes large enough. -/// Algorithm 1 can be vectorized by chunking and performing many rounds at once, but there are too -/// few rounds on average until `left + right` is enormous, and the worst case of a single -/// round is always there. Instead, algorithm 3 utilizes repeated swapping of -/// `min(left, right)` elements until a smaller rotate problem is left. -/// -/// ```text -/// left = 11, right = 4 -/// [4 5 6 7 8 9 10 11 12 13 14 . 0 1 2 3] -/// ^ ^ ^ ^ ^ ^ ^ ^ swapping the right most elements with elements to the left -/// [4 5 6 7 8 9 10 . 0 1 2 3] 11 12 13 14 -/// ^ ^ ^ ^ ^ ^ ^ ^ swapping these -/// [4 5 6 . 0 1 2 3] 7 8 9 10 11 12 13 14 -/// we cannot swap any more, but a smaller rotation problem is left to solve -/// ``` -/// when `left < right` the swapping happens from the left instead. -pub unsafe fn ptr_rotate<T>(mut left: usize, mut mid: *mut T, mut right: usize) { - type BufType = [usize; 32]; - if mem::size_of::<T>() == 0 { - return; - } - loop { - // N.B. the below algorithms can fail if these cases are not checked - if (right == 0) || (left == 0) { - return; - } - if (left + right < 24) || (mem::size_of::<T>() > mem::size_of::<[usize; 4]>()) { - // Algorithm 1 - // Microbenchmarks indicate that the average performance for random shifts is better all - // the way until about `left + right == 32`, but the worst case performance breaks even - // around 16. 24 was chosen as middle ground. If the size of `T` is larger than 4 - // `usize`s, this algorithm also outperforms other algorithms. - let x = unsafe { mid.sub(left) }; - // beginning of first round - let mut tmp: T = unsafe { x.read() }; - let mut i = right; - // `gcd` can be found before hand by calculating `gcd(left + right, right)`, - // but it is faster to do one loop which calculates the gcd as a side effect, then - // doing the rest of the chunk - let mut gcd = right; - // benchmarks reveal that it is faster to swap temporaries all the way through instead - // of reading one temporary once, copying backwards, and then writing that temporary at - // the very end. This is possibly due to the fact that swapping or replacing temporaries - // uses only one memory address in the loop instead of needing to manage two. - loop { - tmp = unsafe { x.add(i).replace(tmp) }; - // instead of incrementing `i` and then checking if it is outside the bounds, we - // check if `i` will go outside the bounds on the next increment. This prevents - // any wrapping of pointers or `usize`. - if i >= left { - i -= left; - if i == 0 { - // end of first round - unsafe { x.write(tmp) }; - break; - } - // this conditional must be here if `left + right >= 15` - if i < gcd { - gcd = i; - } - } else { - i += right; - } - } - // finish the chunk with more rounds - for start in 1..gcd { - tmp = unsafe { x.add(start).read() }; - i = start + right; - loop { - tmp = unsafe { x.add(i).replace(tmp) }; - if i >= left { - i -= left; - if i == start { - unsafe { x.add(start).write(tmp) }; - break; - } - } else { - i += right; - } - } - } - return; - // `T` is not a zero-sized type, so it's okay to divide by its size. - } else if cmp::min(left, right) <= mem::size_of::<BufType>() / mem::size_of::<T>() { - // Algorithm 2 - // The `[T; 0]` here is to ensure this is appropriately aligned for T - let mut rawarray = MaybeUninit::<(BufType, [T; 0])>::uninit(); - let buf = rawarray.as_mut_ptr() as *mut T; - let dim = unsafe { mid.sub(left).add(right) }; - if left <= right { - unsafe { - ptr::copy_nonoverlapping(mid.sub(left), buf, left); - ptr::copy(mid, mid.sub(left), right); - ptr::copy_nonoverlapping(buf, dim, left); - } - } else { - unsafe { - ptr::copy_nonoverlapping(mid, buf, right); - ptr::copy(mid.sub(left), dim, left); - ptr::copy_nonoverlapping(buf, mid.sub(left), right); - } - } - return; - } else if left >= right { - // Algorithm 3 - // There is an alternate way of swapping that involves finding where the last swap - // of this algorithm would be, and swapping using that last chunk instead of swapping - // adjacent chunks like this algorithm is doing, but this way is still faster. - loop { - unsafe { - ptr::swap_nonoverlapping(mid.sub(right), mid, right); - mid = mid.sub(right); - } - left -= right; - if left < right { - break; - } - } - } else { - // Algorithm 3, `left < right` - loop { - unsafe { - ptr::swap_nonoverlapping(mid.sub(left), mid, left); - mid = mid.add(left); - } - right -= left; - if right < left { - break; - } - } - } - } -} |