Auto merge of #52166 - orlp:master, r=joshtriplett

Performance improvement of Vec's swap_remove.

The old implementation *literally* swapped and then removed, which resulted in unnecessary move instructions. The new implementation does use unsafe code, but is easy to see that it is correct.

Fixes https://github.com/rust-lang/rust/issues/52150.

1 files changed, 9 insertions, 3 deletions

diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs
index fbbaced540e..5efe1e23309 100644
--- a/src/liballoc/vec.rs
+++ b/src/liballoc/vec.rs
@@ -809,9 +809,15 @@ impl<T> Vec<T> {
     #[inline]
     #[stable(feature = "rust1", since = "1.0.0")]
     pub fn swap_remove(&mut self, index: usize) -> T {
-        let length = self.len();
-        self.swap(index, length - 1);
-        self.pop().unwrap()
+        unsafe {
+            // We replace self[index] with the last element. Note that if the
+            // bounds check on hole succeeds there must be a last element (which
+            // can be self[index] itself).
+            let hole: *mut T = &mut self[index];
+            let last = ptr::read(self.get_unchecked(self.len - 1));
+            self.len -= 1;
+            ptr::replace(hole, last)
+        }
     }
 
     /// Inserts an element at position `index` within the vector, shifting all