Auto merge of #79186 - JulianKnodt:str_from, r=Mark-Simulacrum

Change slice::to_vec to not use extend_from_slice

I saw this [Zulip thread](https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs/topic/String.3A.3Afrom%28.26str%29.20wonky.20codegen/near/216164455), and didn't see any update from it, so I thought I'd try to fix it. This converts `to_vec` to no longer use `extend_from_slice`, but relies on knowing that the allocated capacity is the same size as the input.

[Godbolt new v1](https://rust.godbolt.org/z/1bcWKG)
[Godbolt new v2 w/ drop guard](https://rust.godbolt.org/z/5jn76K)
[Godbolt old version](https://rust.godbolt.org/z/e4ePav)

After some amount of iteration, there are now two specializations for `to_vec`, one for `Copy` types that use memcpy, and one for clone types which is the original from this PR.

This is then used inside of `impl<T: Clone> FromIterator<Iter::Slice<T>> for Vec<T>` which is essentially equivalent to `&[T] -> Vec<T>`, instead of previous specialization of the `extend` function. This is because extend has to reason more about existing capacity by calling `reserve` on an existing vec, and thus produces worse asm.

Downsides: This allocates the exact capacity, so I think if many items are added to this `Vec` after, it might need to allocate whereas extending may not. I also noticed the number of faults went up in the benchmarks, but not sure where from exactly.

3 files changed, 85 insertions, 17 deletions

diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs
index 41ebb1cf654..949a3bb1d70 100644
--- a/library/alloc/src/slice.rs
+++ b/library/alloc/src/slice.rs
@@ -155,13 +155,65 @@ mod hack {
     }
 
     #[inline]
-    pub fn to_vec<T, A: AllocRef>(s: &[T], alloc: A) -> Vec<T, A>
-    where
-        T: Clone,
-    {
-        let mut vec = Vec::with_capacity_in(s.len(), alloc);
-        vec.extend_from_slice(s);
-        vec
+    pub fn to_vec<T: ConvertVec, A: AllocRef>(s: &[T], alloc: A) -> Vec<T, A> {
+        T::to_vec(s, alloc)
+    }
+
+    pub trait ConvertVec {
+        fn to_vec<A: AllocRef>(s: &[Self], alloc: A) -> Vec<Self, A>
+        where
+            Self: Sized;
+    }
+
+    impl<T: Clone> ConvertVec for T {
+        #[inline]
+        default fn to_vec<A: AllocRef>(s: &[Self], alloc: A) -> Vec<Self, A> {
+            struct DropGuard<'a, T, A: AllocRef> {
+                vec: &'a mut Vec<T, A>,
+                num_init: usize,
+            }
+            impl<'a, T, A: AllocRef> Drop for DropGuard<'a, T, A> {
+                #[inline]
+                fn drop(&mut self) {
+                    // SAFETY:
+                    // items were marked initialized in the loop below
+                    unsafe {
+                        self.vec.set_len(self.num_init);
+                    }
+                }
+            }
+            let mut vec = Vec::with_capacity_in(s.len(), alloc);
+            let mut guard = DropGuard { vec: &mut vec, num_init: 0 };
+            let slots = guard.vec.spare_capacity_mut();
+            // .take(slots.len()) is necessary for LLVM to remove bounds checks
+            // and has better codegen than zip.
+            for (i, b) in s.iter().enumerate().take(slots.len()) {
+                guard.num_init = i;
+                slots[i].write(b.clone());
+            }
+            core::mem::forget(guard);
+            // SAFETY:
+            // the vec was allocated and initialized above to at least this length.
+            unsafe {
+                vec.set_len(s.len());
+            }
+            vec
+        }
+    }
+
+    impl<T: Copy> ConvertVec for T {
+        #[inline]
+        fn to_vec<A: AllocRef>(s: &[Self], alloc: A) -> Vec<Self, A> {
+            let mut v = Vec::with_capacity_in(s.len(), alloc);
+            // SAFETY:
+            // allocated above with the capacity of `s`, and initialize to `s.len()` in
+            // ptr::copy_to_non_overlapping below.
+            unsafe {
+                s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len());
+                v.set_len(s.len());
+            }
+            v
+        }
     }
 }
 
diff --git a/library/alloc/src/vec.rs b/library/alloc/src/vec.rs
index 2225bf63e3c..51687920928 100644
--- a/library/alloc/src/vec.rs
+++ b/library/alloc/src/vec.rs
@@ -2508,17 +2508,23 @@ where
     }
 }
 
-impl<'a, T: 'a> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec<T>
-where
-    T: Copy,
-{
-    // reuses the extend specialization for T: Copy
+// This utilizes `iterator.as_slice().to_vec()` since spec_extend
+// must take more steps to reason about the final capacity + length
+// and thus do more work. `to_vec()` directly allocates the correct amount
+// and fills it exactly.
+impl<'a, T: 'a + Clone> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec<T> {
+    #[cfg(not(test))]
     fn from_iter(iterator: slice::Iter<'a, T>) -> Self {
-        let mut vec = Vec::new();
-        // must delegate to spec_extend() since extend() itself delegates
-        // to spec_from for empty Vecs
-        vec.spec_extend(iterator);
-        vec
+        iterator.as_slice().to_vec()
+    }
+
+    // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is
+    // required for this method definition, is not available. Instead use the
+    // `slice::to_vec`  function which is only available with cfg(test)
+    // NB see the slice::hack module in slice.rs for more information
+    #[cfg(test)]
+    fn from_iter(iterator: slice::Iter<'a, T>) -> Self {
+        crate::slice::to_vec(iterator.as_slice(), Global)
     }
 }
 
diff --git a/src/test/codegen/to_vec.rs b/src/test/codegen/to_vec.rs
new file mode 100644
index 00000000000..60dc4efcb62
--- /dev/null
+++ b/src/test/codegen/to_vec.rs
@@ -0,0 +1,10 @@
+// compile-flags: -O
+
+#![crate_type = "lib"]
+
+// CHECK-LABEL: @copy_to_vec
+#[no_mangle]
+fn copy_to_vec(s: &[u64]) -> Vec<u64> {
+  s.to_vec()
+  // CHECK: call void @llvm.memcpy
+}