From c05676b97f2151242a07e98bbde53e9c5d7f1e7a Mon Sep 17 00:00:00 2001 From: Scott McMurray Date: Sun, 30 Apr 2017 23:50:59 -0700 Subject: [PATCH] Add an in-place rotate method for slices to libcore A helpful primitive for moving chunks of data around inside a slice. In particular, adding elements to the end of a Vec then moving them somewhere else, as a way to do efficient multiple-insert. (There's drain for efficient block-remove, but no easy way to block-insert.) Talk with another example: --- src/doc/unstable-book/src/SUMMARY.md | 1 + .../src/library-features/slice-rotate.md | 7 + src/libcollections/benches/lib.rs | 1 + src/libcollections/benches/slice.rs | 41 +++++ src/libcollections/lib.rs | 1 + src/libcollections/slice.rs | 52 ++++++ src/libcollections/tests/lib.rs | 1 + src/libcollections/tests/slice.rs | 36 ++++ src/libcore/slice/mod.rs | 16 ++ src/libcore/slice/rotate.rs | 154 ++++++++++++++++++ src/libcore/tests/lib.rs | 1 + src/libcore/tests/slice.rs | 16 ++ 12 files changed, 327 insertions(+) create mode 100644 src/doc/unstable-book/src/library-features/slice-rotate.md create mode 100644 src/libcore/slice/rotate.rs diff --git a/src/doc/unstable-book/src/SUMMARY.md b/src/doc/unstable-book/src/SUMMARY.md index 39f80059148..de2c2b83767 100644 --- a/src/doc/unstable-book/src/SUMMARY.md +++ b/src/doc/unstable-book/src/SUMMARY.md @@ -195,6 +195,7 @@ - [sip_hash_13](library-features/sip-hash-13.md) - [slice_concat_ext](library-features/slice-concat-ext.md) - [slice_get_slice](library-features/slice-get-slice.md) + - [slice_rotate](library-features/slice-rotate.md) - [slice_rsplit](library-features/slice-rsplit.md) - [sort_internals](library-features/sort-internals.md) - [sort_unstable](library-features/sort-unstable.md) diff --git a/src/doc/unstable-book/src/library-features/slice-rotate.md b/src/doc/unstable-book/src/library-features/slice-rotate.md new file mode 100644 index 00000000000..40063412c29 --- /dev/null +++ b/src/doc/unstable-book/src/library-features/slice-rotate.md @@ -0,0 +1,7 @@ +# `slice_rotate` + +The tracking issue for this feature is: [#123456789] + +[#123456789]: https://github.com/rust-lang/rust/issues/123456789 + +------------------------ diff --git a/src/libcollections/benches/lib.rs b/src/libcollections/benches/lib.rs index 9f356e4b579..958020d0b0e 100644 --- a/src/libcollections/benches/lib.rs +++ b/src/libcollections/benches/lib.rs @@ -13,6 +13,7 @@ #![feature(i128_type)] #![feature(rand)] #![feature(repr_simd)] +#![feature(slice_rotate)] #![feature(sort_unstable)] #![feature(test)] diff --git a/src/libcollections/benches/slice.rs b/src/libcollections/benches/slice.rs index 0079f2d0103..aa5a438b35e 100644 --- a/src/libcollections/benches/slice.rs +++ b/src/libcollections/benches/slice.rs @@ -195,6 +195,11 @@ fn gen_random(len: usize) -> Vec { rng.gen_iter::().take(len).collect() } +fn gen_random_bytes(len: usize) -> Vec { + let mut rng = thread_rng(); + rng.gen_iter::().take(len).collect() +} + fn gen_mostly_ascending(len: usize) -> Vec { let mut rng = thread_rng(); let mut v = gen_ascending(len); @@ -315,3 +320,39 @@ fn $name(b: &mut Bencher) { reverse!(reverse_u128, u128, |x| x as u128); #[repr(simd)] struct F64x4(f64, f64, f64, f64); reverse!(reverse_simd_f64x4, F64x4, |x| { let x = x as f64; F64x4(x,x,x,x) }); + +macro_rules! rotate { + ($name:ident, $gen:expr, $len:expr, $mid:expr) => { + #[bench] + fn $name(b: &mut Bencher) { + let size = mem::size_of_val(&$gen(1)[0]); + let mut v = $gen($len * 8 / size); + b.iter(|| black_box(&mut v).rotate(($mid*8+size-1)/size)); + b.bytes = (v.len() * size) as u64; + } + } +} + +rotate!(rotate_tiny_by1, gen_random, 16, 1); +rotate!(rotate_tiny_half, gen_random, 16, 16/2); +rotate!(rotate_tiny_half_plus_one, gen_random, 16, 16/2+1); + +rotate!(rotate_medium_by1, gen_random, 9158, 1); +rotate!(rotate_medium_by727_u64, gen_random, 9158, 727); +rotate!(rotate_medium_by727_bytes, gen_random_bytes, 9158, 727); +rotate!(rotate_medium_by727_strings, gen_strings, 9158, 727); +rotate!(rotate_medium_half, gen_random, 9158, 9158/2); +rotate!(rotate_medium_half_plus_one, gen_random, 9158, 9158/2+1); + +// Intended to use more RAM than the machine has cache +rotate!(rotate_huge_by1, gen_random, 5*1024*1024, 1); +rotate!(rotate_huge_by9199_u64, gen_random, 5*1024*1024, 9199); +rotate!(rotate_huge_by9199_bytes, gen_random_bytes, 5*1024*1024, 9199); +rotate!(rotate_huge_by9199_strings, gen_strings, 5*1024*1024, 9199); +rotate!(rotate_huge_by9199_big, gen_big_random, 5*1024*1024, 9199); +rotate!(rotate_huge_by1234577_u64, gen_random, 5*1024*1024, 1234577); +rotate!(rotate_huge_by1234577_bytes, gen_random_bytes, 5*1024*1024, 1234577); +rotate!(rotate_huge_by1234577_strings, gen_strings, 5*1024*1024, 1234577); +rotate!(rotate_huge_by1234577_big, gen_big_random, 5*1024*1024, 1234577); +rotate!(rotate_huge_half, gen_random, 5*1024*1024, 5*1024*1024/2); +rotate!(rotate_huge_half_plus_one, gen_random, 5*1024*1024, 5*1024*1024/2+1); diff --git a/src/libcollections/lib.rs b/src/libcollections/lib.rs index 842f2f44fff..713f379014f 100644 --- a/src/libcollections/lib.rs +++ b/src/libcollections/lib.rs @@ -55,6 +55,7 @@ #![feature(shared)] #![feature(slice_get_slice)] #![feature(slice_patterns)] +#![cfg_attr(not(test), feature(slice_rotate))] #![feature(slice_rsplit)] #![cfg_attr(not(test), feature(sort_unstable))] #![feature(specialization)] diff --git a/src/libcollections/slice.rs b/src/libcollections/slice.rs index 3efda1faa3b..c4c20848caa 100644 --- a/src/libcollections/slice.rs +++ b/src/libcollections/slice.rs @@ -1337,6 +1337,58 @@ pub fn sort_unstable_by_key(&mut self, f: F) core_slice::SliceExt::sort_unstable_by_key(self, f); } + /// Permutes the slice in-place such that `self[mid..]` move to the + /// beginning of the slice while `self[..mid]` move to the end of the + /// slice. Equivalently, rotates the slice `mid` places to the left + /// or `k = self.len() - mid` places to the right. + /// + /// Rotation by `mid` and rotation by `k` are inverse operations. + /// The method returns `k`, which is also the new location of + /// the formerly-first element. + /// + /// This is a "k-rotation", a permutation in which item `i` moves to + /// position `i + k`, modulo the length of the slice. See _Elements + /// of Programming_ [§10.4][eop]. + /// + /// [eop]: https://books.google.com/books?id=CO9ULZGINlsC&pg=PA178&q=k-rotation + /// + /// # Panics + /// + /// This function will panic if `mid` is greater than the length of the + /// slice. (Note that `mid == self.len()` does _not_ panic; it's a nop + /// rotation with `k == 0`, the inverse of a rotation with `mid == 0`.) + /// + /// # Complexity + /// + /// Takes linear (in `self.len()`) time. + /// + /// # Examples + /// + /// ``` + /// #![feature(slice_rotate)] + /// + /// let mut a = [1, 2, 3, 4, 5, 6, 7]; + /// let k = a.rotate(2); + /// assert_eq!(&a, &[3, 4, 5, 6, 7, 1, 2]); + /// a.rotate(k); + /// assert_eq!(&a, &[1, 2, 3, 4, 5, 6, 7]); + /// + /// fn extend_at(v: &mut Vec, index: usize, iter: I) + /// where I: Iterator + /// { + /// let mid = v.len() - index; + /// v.extend(iter); + /// v[index..].rotate(mid); + /// } + /// let mut v = (0..10).collect(); + /// extend_at(&mut v, 7, 100..104); + /// assert_eq!(&v, &[0, 1, 2, 3, 4, 5, 6, 100, 101, 102, 103, 7, 8, 9]); + /// ``` + #[unstable(feature = "slice_rotate", issue = "123456789")] + pub fn rotate(&mut self, mid: usize) -> usize { + core_slice::SliceExt::rotate(self, mid) + } + /// Copies the elements from `src` into `self`. /// /// The length of `src` must be the same as `self`. diff --git a/src/libcollections/tests/lib.rs b/src/libcollections/tests/lib.rs index eae3bf3915f..7eab5a049c3 100644 --- a/src/libcollections/tests/lib.rs +++ b/src/libcollections/tests/lib.rs @@ -20,6 +20,7 @@ #![feature(pattern)] #![feature(placement_in_syntax)] #![feature(rand)] +#![feature(slice_rotate)] #![feature(splice)] #![feature(step_by)] #![feature(str_escape)] diff --git a/src/libcollections/tests/slice.rs b/src/libcollections/tests/slice.rs index 1708f98b7ee..6feaf91d6da 100644 --- a/src/libcollections/tests/slice.rs +++ b/src/libcollections/tests/slice.rs @@ -466,6 +466,42 @@ fn test_sort_stability() { } } +#[test] +fn test_rotate() { + let expected: Vec<_> = (0..13).collect(); + let mut v = Vec::new(); + + // no-ops + v.clone_from(&expected); + v.rotate(0); + assert_eq!(v, expected); + v.rotate(expected.len()); + assert_eq!(v, expected); + let mut zst_array = [(), (), ()]; + zst_array.rotate(2); + + // happy path + v = (5..13).chain(0..5).collect(); + let k = v.rotate(8); + assert_eq!(v, expected); + assert_eq!(k, 5); + + let expected: Vec<_> = (0..1000).collect(); + + // small rotations in large slice, uses ptr::copy + v = (2..1000).chain(0..2).collect(); + v.rotate(998); + assert_eq!(v, expected); + v = (998..1000).chain(0..998).collect(); + v.rotate(2); + assert_eq!(v, expected); + + // non-small prime rotation, has a few rounds of swapping + v = (389..1000).chain(0..389).collect(); + v.rotate(1000-389); + assert_eq!(v, expected); +} + #[test] fn test_concat() { let v: [Vec; 0] = []; diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs index e15eb8f2444..744dd791a7e 100644 --- a/src/libcore/slice/mod.rs +++ b/src/libcore/slice/mod.rs @@ -51,6 +51,7 @@ use marker::{Copy, Send, Sync, Sized, self}; use iter_private::TrustedRandomAccess; +mod rotate; mod sort; #[repr(C)] @@ -202,6 +203,9 @@ unsafe fn get_unchecked_mut(&mut self, index: I) -> &mut I::Output #[stable(feature = "core", since = "1.6.0")] fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq; + #[unstable(feature = "slice_rotate", issue = "123456789")] + fn rotate(&mut self, mid: usize) -> usize; + #[stable(feature = "clone_from_slice", since = "1.7.0")] fn clone_from_slice(&mut self, src: &[Self::Item]) where Self::Item: Clone; @@ -635,6 +639,18 @@ fn binary_search(&self, x: &Q) -> Result self.binary_search_by(|p| p.borrow().cmp(x)) } + fn rotate(&mut self, mid: usize) -> usize { + assert!(mid <= self.len()); + let k = self.len() - mid; + + unsafe { + let p = self.as_mut_ptr(); + rotate::ptr_rotate(mid, p.offset(mid as isize), k); + } + + k + } + #[inline] fn clone_from_slice(&mut self, src: &[T]) where T: Clone { assert!(self.len() == src.len(), diff --git a/src/libcore/slice/rotate.rs b/src/libcore/slice/rotate.rs new file mode 100644 index 00000000000..71a627a327c --- /dev/null +++ b/src/libcore/slice/rotate.rs @@ -0,0 +1,154 @@ +// Copyright 2012-2017 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use cmp; +use mem; +use ptr; + +/// Rotation is much faster if it has access to a little bit of memory. This +/// union provides a RawVec-like interface, but to a fixed-size stack buffer. +#[allow(unions_with_drop_fields)] +union RawArray { + /// Ensure this is appropriately aligned for T, and is big + /// enough for two elements even if T is enormous. + typed: [T; 2], + /// For normally-sized types, especially things like u8, having more + /// than 2 in the buffer is necessary for usefulness, so pad it out + /// enough to be helpful, but not so big as to risk overflow. + _extra: [usize; 32], +} + +impl RawArray { + fn new() -> Self { + unsafe { mem::uninitialized() } + } + fn ptr(&self) -> *mut T { + unsafe { &self.typed as *const T as *mut T } + } + fn cap() -> usize { + if mem::size_of::() == 0 { + usize::max_value() + } else { + mem::size_of::() / mem::size_of::() + } + } +} + +/// 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. +/// The type `T` must have non-zero size. +/// +/// # Algorithm +/// +/// For longer rotations, swap the left-most `delta = min(left, right)` +/// elements with the right-most `delta` elements. LLVM vectorizes this, +/// which is profitable as we only reach this step for a "large enough" +/// rotation. Doing this puts `delta` elements on the larger side into the +/// correct position, leaving a smaller rotate problem. Demonstration: +/// +/// ```text +/// [ 6 7 8 9 10 11 12 13 . 1 2 3 4 5 ] +/// 1 2 3 4 5 [ 11 12 13 . 6 7 8 9 10 ] +/// 1 2 3 4 5 [ 8 9 10 . 6 7 ] 11 12 13 +/// 1 2 3 4 5 6 7 [ 10 . 8 9 ] 11 12 13 +/// 1 2 3 4 5 6 7 [ 9 . 8 ] 10 11 12 13 +/// 1 2 3 4 5 6 7 8 [ . ] 9 10 11 12 13 +/// ``` +/// +/// Once the rotation is small enough, copy some elements into a stack +/// buffer, `memmove` the others, and move the ones back from the buffer. +pub unsafe fn ptr_rotate(mut left: usize, mid: *mut T, mut right: usize) { + loop { + let delta = cmp::min(left, right); + if delta <= RawArray::::cap() { + break; + } + + ptr_swap_n( + mid.offset(-(left as isize)), + mid.offset((right-delta) as isize), + delta); + + if left <= right { + right -= delta; + } else { + left -= delta; + } + } + + let rawarray = RawArray::new(); + let buf = rawarray.ptr(); + + let dim = mid.offset(-(left as isize)).offset(right as isize); + if left <= right { + ptr::copy_nonoverlapping(mid.offset(-(left as isize)), buf, left); + ptr::copy(mid, mid.offset(-(left as isize)), right); + ptr::copy_nonoverlapping(buf, dim, left); + } + else { + ptr::copy_nonoverlapping(mid, buf, right); + ptr::copy(mid.offset(-(left as isize)), dim, left); + ptr::copy_nonoverlapping(buf, mid.offset(-(left as isize)), right); + } +} + +unsafe fn ptr_swap_u8(a: *mut u8, b: *mut u8, n: usize) { + for i in 0..n { + ptr::swap(a.offset(i as isize), b.offset(i as isize)); + } +} +unsafe fn ptr_swap_u16(a: *mut u16, b: *mut u16, n: usize) { + for i in 0..n { + ptr::swap(a.offset(i as isize), b.offset(i as isize)); + } +} +unsafe fn ptr_swap_u32(a: *mut u32, b: *mut u32, n: usize) { + for i in 0..n { + ptr::swap(a.offset(i as isize), b.offset(i as isize)); + } +} +unsafe fn ptr_swap_u64(a: *mut u64, b: *mut u64, n: usize) { + for i in 0..n { + ptr::swap(a.offset(i as isize), b.offset(i as isize)); + } +} + +unsafe fn ptr_swap_n(a: *mut T, b: *mut T, n: usize) { + // Doing this as a generic is 16% & 40% slower in two of the `String` + // benchmarks, as (based on the block names) LLVM doesn't vectorize it. + // Since this is just operating on raw memory, dispatch to a version + // with appropriate alignment. Helps with code size as well, by + // avoiding monomorphizing different unrolled loops for `i32`, + // `u32`, `f32`, `[u32; 1]`, etc. + let size_of_t = mem::size_of::(); + let align_of_t = mem::align_of::(); + + let a64 = mem::align_of::(); + if a64 == 8 && align_of_t % a64 == 0 { + return ptr_swap_u64(a as *mut u64, b as *mut u64, n * (size_of_t / 8)); + } + + let a32 = mem::align_of::(); + if a32 == 4 && align_of_t % a32 == 0 { + return ptr_swap_u32(a as *mut u32, b as *mut u32, n * (size_of_t / 4)); + } + + let a16 = mem::align_of::(); + if a16 == 2 && align_of_t % a16 == 0 { + return ptr_swap_u16(a as *mut u16, b as *mut u16, n * (size_of_t / 2)); + } + + ptr_swap_u8(a as *mut u8, b as *mut u8, n * size_of_t); +} diff --git a/src/libcore/tests/lib.rs b/src/libcore/tests/lib.rs index c52155ead4f..a9f88e9fd02 100644 --- a/src/libcore/tests/lib.rs +++ b/src/libcore/tests/lib.rs @@ -29,6 +29,7 @@ #![feature(raw)] #![feature(sip_hash_13)] #![feature(slice_patterns)] +#![feature(slice_rotate)] #![feature(sort_internals)] #![feature(sort_unstable)] #![feature(step_by)] diff --git a/src/libcore/tests/slice.rs b/src/libcore/tests/slice.rs index 15047204e50..f34f9497500 100644 --- a/src/libcore/tests/slice.rs +++ b/src/libcore/tests/slice.rs @@ -238,6 +238,22 @@ fn test_find_rfind() { assert_eq!(v.iter().rfind(|&&x| x <= 3), Some(&3)); } +#[test] +fn test_rotate() { + const N: usize = 600; + let a: &mut [_] = &mut [0; N]; + for i in 0..N { + a[i] = i; + } + + let k = a.rotate(42); + + assert_eq!(k, N - 42); + for i in 0..N { + assert_eq!(a[(i+k)%N], i); + } +} + #[test] fn sort_unstable() { let mut v = [0; 600]; -- 2.44.0