library/core/src/slice/rotate.rs

   1 // ignore-tidy-undocumented-unsafe
   2
   3 use crate::cmp;
   4 use crate::mem::{self, MaybeUninit};
   5 use crate::ptr;
   6
   7 /// Rotates the range `[mid-left, mid+right)` such that the element at `mid` becomes the first
   8 /// element. Equivalently, rotates the range `left` elements to the left or `right` elements to the
   9 /// right.
  10 ///
  11 /// # Safety
  12 ///
  13 /// The specified range must be valid for reading and writing.
  14 ///
  15 /// # Algorithm
  16 ///
  17 /// Algorithm 1 is used for small values of `left + right` or for large `T`. The elements are moved
  18 /// into their final positions one at a time starting at `mid - left` and advancing by `right` steps
  19 /// modulo `left + right`, such that only one temporary is needed. Eventually, we arrive back at
  20 /// `mid - left`. However, if `gcd(left + right, right)` is not 1, the above steps skipped over
  21 /// elements. For example:
  22 /// ```text
  23 /// left = 10, right = 6
  24 /// the `^` indicates an element in its final place
  25 /// 6 7 8 9 10 11 12 13 14 15 . 0 1 2 3 4 5
  26 /// after using one step of the above algorithm (The X will be overwritten at the end of the round,
  27 /// and 12 is stored in a temporary):
  28 /// X 7 8 9 10 11 6 13 14 15 . 0 1 2 3 4 5
  29 ///               ^
  30 /// after using another step (now 2 is in the temporary):
  31 /// X 7 8 9 10 11 6 13 14 15 . 0 1 12 3 4 5
  32 ///               ^                 ^
  33 /// after the third step (the steps wrap around, and 8 is in the temporary):
  34 /// X 7 2 9 10 11 6 13 14 15 . 0 1 12 3 4 5
  35 ///     ^         ^                 ^
  36 /// after 7 more steps, the round ends with the temporary 0 getting put in the X:
  37 /// 0 7 2 9 4 11 6 13 8 15 . 10 1 12 3 14 5
  38 /// ^   ^   ^    ^    ^       ^    ^    ^
  39 /// ```
  40 /// Fortunately, the number of skipped over elements between finalized elements is always equal, so
  41 /// we can just offset our starting position and do more rounds (the total number of rounds is the
  42 /// `gcd(left + right, right)` value). The end result is that all elements are finalized once and
  43 /// only once.
  44 ///
  45 /// Algorithm 2 is used if `left + right` is large but `min(left, right)` is small enough to
  46 /// fit onto a stack buffer. The `min(left, right)` elements are copied onto the buffer, `memmove`
  47 /// is applied to the others, and the ones on the buffer are moved back into the hole on the
  48 /// opposite side of where they originated.
  49 ///
  50 /// Algorithms that can be vectorized outperform the above once `left + right` becomes large enough.
  51 /// Algorithm 1 can be vectorized by chunking and performing many rounds at once, but there are too
  52 /// few rounds on average until `left + right` is enormous, and the worst case of a single
  53 /// round is always there. Instead, algorithm 3 utilizes repeated swapping of
  54 /// `min(left, right)` elements until a smaller rotate problem is left.
  55 ///
  56 /// ```text
  57 /// left = 11, right = 4
  58 /// [4 5 6 7 8 9 10 11 12 13 14 . 0 1 2 3]
  59 ///                  ^  ^  ^  ^   ^ ^ ^ ^ swapping the right most elements with elements to the left
  60 /// [4 5 6 7 8 9 10 . 0 1 2 3] 11 12 13 14
  61 ///        ^ ^ ^  ^   ^ ^ ^ ^ swapping these
  62 /// [4 5 6 . 0 1 2 3] 7 8 9 10 11 12 13 14
  63 /// we cannot swap any more, but a smaller rotation problem is left to solve
  64 /// ```
  65 /// when `left < right` the swapping happens from the left instead.
  66 pub unsafe fn ptr_rotate<T>(mut left: usize, mut mid: *mut T, mut right: usize) {
  67     type BufType = [usize; 32];
  68     if mem::size_of::<T>() == 0 {
  69         return;
  70     }
  71     loop {
  72         // N.B. the below algorithms can fail if these cases are not checked
  73         if (right == 0) || (left == 0) {
  74             return;
  75         }
  76         if (left + right < 24) || (mem::size_of::<T>() > mem::size_of::<[usize; 4]>()) {
  77             // Algorithm 1
  78             // Microbenchmarks indicate that the average performance for random shifts is better all
  79             // the way until about `left + right == 32`, but the worst case performance breaks even
  80             // around 16. 24 was chosen as middle ground. If the size of `T` is larger than 4
  81             // `usize`s, this algorithm also outperforms other algorithms.
  82             let x = unsafe { mid.sub(left) };
  83             // beginning of first round
  84             let mut tmp: T = unsafe { x.read() };
  85             let mut i = right;
  86             // `gcd` can be found before hand by calculating `gcd(left + right, right)`,
  87             // but it is faster to do one loop which calculates the gcd as a side effect, then
  88             // doing the rest of the chunk
  89             let mut gcd = right;
  90             // benchmarks reveal that it is faster to swap temporaries all the way through instead
  91             // of reading one temporary once, copying backwards, and then writing that temporary at
  92             // the very end. This is possibly due to the fact that swapping or replacing temporaries
  93             // uses only one memory address in the loop instead of needing to manage two.
  94             loop {
  95                 tmp = unsafe { x.add(i).replace(tmp) };
  96                 // instead of incrementing `i` and then checking if it is outside the bounds, we
  97                 // check if `i` will go outside the bounds on the next increment. This prevents
  98                 // any wrapping of pointers or `usize`.
  99                 if i >= left {
 100                     i -= left;
 101                     if i == 0 {
 102                         // end of first round
 103                         unsafe { x.write(tmp) };
 104                         break;
 105                     }
 106                     // this conditional must be here if `left + right >= 15`
 107                     if i < gcd {
 108                         gcd = i;
 109                     }
 110                 } else {
 111                     i += right;
 112                 }
 113             }
 114             // finish the chunk with more rounds
 115             for start in 1..gcd {
 116                 tmp = unsafe { x.add(start).read() };
 117                 i = start + right;
 118                 loop {
 119                     tmp = unsafe { x.add(i).replace(tmp) };
 120                     if i >= left {
 121                         i -= left;
 122                         if i == start {
 123                             unsafe { x.add(start).write(tmp) };
 124                             break;
 125                         }
 126                     } else {
 127                         i += right;
 128                     }
 129                 }
 130             }
 131             return;
 132         // `T` is not a zero-sized type, so it's okay to divide by its size.
 133         } else if cmp::min(left, right) <= mem::size_of::<BufType>() / mem::size_of::<T>() {
 134             // Algorithm 2
 135             // The `[T; 0]` here is to ensure this is appropriately aligned for T
 136             let mut rawarray = MaybeUninit::<(BufType, [T; 0])>::uninit();
 137             let buf = rawarray.as_mut_ptr() as *mut T;
 138             let dim = unsafe { mid.sub(left).add(right) };
 139             if left <= right {
 140                 unsafe {
 141                     ptr::copy_nonoverlapping(mid.sub(left), buf, left);
 142                     ptr::copy(mid, mid.sub(left), right);
 143                     ptr::copy_nonoverlapping(buf, dim, left);
 144                 }
 145             } else {
 146                 unsafe {
 147                     ptr::copy_nonoverlapping(mid, buf, right);
 148                     ptr::copy(mid.sub(left), dim, left);
 149                     ptr::copy_nonoverlapping(buf, mid.sub(left), right);
 150                 }
 151             }
 152             return;
 153         } else if left >= right {
 154             // Algorithm 3
 155             // There is an alternate way of swapping that involves finding where the last swap
 156             // of this algorithm would be, and swapping using that last chunk instead of swapping
 157             // adjacent chunks like this algorithm is doing, but this way is still faster.
 158             loop {
 159                 unsafe {
 160                     ptr::swap_nonoverlapping(mid.sub(right), mid, right);
 161                     mid = mid.sub(right);
 162                 }
 163                 left -= right;
 164                 if left < right {
 165                     break;
 166                 }
 167             }
 168         } else {
 169             // Algorithm 3, `left < right`
 170             loop {
 171                 unsafe {
 172                     ptr::swap_nonoverlapping(mid.sub(left), mid, left);
 173                     mid = mid.add(left);
 174                 }
 175                 right -= left;
 176                 if right < left {
 177                     break;
 178                 }
 179             }
 180         }
 181     }
 182 }