Repository: bluss/arrayvec (rust)

Issue:
Performance regression in 0.6.1
https://github.com/niklasf/shakmaty/blob/master/benches/benches.rs are showing a major performance regression going from arravec 0.6.0 to 0.6.1. For example:

```
bench_shallow_perft
  Instructions:            31844284 (+153.8268%)
  L1 Accesses:             54897187 (+233.5472%)
  L2 Accesses:                  315 (+47.19626%)
  RAM Accesses:                 472 (+8.505747%)
  Estimated Cycles:        54915282 (+233.3271%)
```

I bisected it to 5ad4687b1be20707dc281fd383486c1128700a41 as the first bad commit.

The benchmarks are mostly using `ArrayVec::{new,push,retain}()`. So far I did not manage to reduce it further.

Pull request description:
Add new_const() for const construction and revert new to old version
The new() function is significantly faster, it optimizes better at the
moment/in current rust. For this reason, provide a const fn constructor,
but not as the default `new`.

It's not expected that the Rust optimization problem can be fixed in the short
term, so we just revert the change to `fn new`. The performance issue in `fn new_const`
is not a problem when it's actually used for initializing statics which is the
most important use case.

Fixes #182 

Patch:
diff --git a/src/array_string.rs b/src/array_string.rs
index 392ff4e..96f57c7 100644
--- a/src/array_string.rs
+++ b/src/array_string.rs
@@ -59,8 +59,27 @@ impl<const CAP: usize> ArrayString<CAP>
     /// assert_eq!(&string[..], "foo");
     /// assert_eq!(string.capacity(), 16);
     /// ```
-    pub const fn new() -> ArrayString<CAP> {
+    pub fn new() -> ArrayString<CAP> {
         assert_capacity_limit!(CAP);
+        unsafe {
+            ArrayString { xs: MaybeUninit::uninit().assume_init(), len: 0 }
+        }
+    }
+
+    /// Create a new empty `ArrayString` (const fn).
+    ///
+    /// Capacity is inferred from the type parameter.
+    ///
+    /// ```
+    /// use arrayvec::ArrayString;
+    ///
+    /// let mut string = ArrayString::<16>::new();
+    /// string.push_str("foo");
+    /// assert_eq!(&string[..], "foo");
+    /// assert_eq!(string.capacity(), 16);
+    /// ```
+    pub const fn new_const() -> ArrayString<CAP> {
+        assert_capacity_limit_const!(CAP);
         ArrayString { xs: MakeMaybeUninit::ARRAY, len: 0 }
     }
 
diff --git a/src/arrayvec.rs b/src/arrayvec.rs
index 3c18df4..5703aff 100644
--- a/src/arrayvec.rs
+++ b/src/arrayvec.rs
@@ -77,8 +77,28 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
     /// assert_eq!(&array[..], &[1, 2]);
     /// assert_eq!(array.capacity(), 16);
     /// ```
-    pub const fn new() -> ArrayVec<T, CAP> {
+    pub fn new() -> ArrayVec<T, CAP> {
         assert_capacity_limit!(CAP);
+        unsafe {
+            ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 }
+        }
+    }
+
+    /// Create a new empty `ArrayVec` (const fn).
+    ///
+    /// The maximum capacity is given by the generic parameter `CAP`.
+    ///
+    /// ```
+    /// use arrayvec::ArrayVec;
+    ///
+    /// let mut array = ArrayVec::<_, 16>::new();
+    /// array.push(1);
+    /// array.push(2);
+    /// assert_eq!(&array[..], &[1, 2]);
+    /// assert_eq!(array.capacity(), 16);
+    /// ```
+    pub const fn new_const() -> ArrayVec<T, CAP> {
+        assert_capacity_limit_const!(CAP);
         ArrayVec { xs: MakeMaybeUninit::ARRAY, len: 0 }
     }
 
@@ -443,58 +463,22 @@ impl<T, const CAP: usize> ArrayVec<T, CAP> {
     pub fn retain<F>(&mut self, mut f: F)
         where F: FnMut(&mut T) -> bool
     {
-        // Check the implementation of
-        // https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain
-        // for safety arguments (especially regarding panics in f and when
-        // dropping elements). Implementation closely mirrored here.
-
-        let original_len = self.len();
-        unsafe { self.set_len(0) };
-
-        struct BackshiftOnDrop<'a, T, const CAP: usize> {
-            v: &'a mut ArrayVec<T, CAP>,
-            processed_len: usize,
-            deleted_cnt: usize,
-            original_len: usize,
-        }
-
-        impl<T, const CAP: usize> Drop for BackshiftOnDrop<'_, T, CAP> {
-            fn drop(&mut self) {
-                if self.deleted_cnt > 0 {
-                    unsafe {
-                        ptr::copy(
-                            self.v.as_ptr().add(self.processed_len),
-                            self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),
-                            self.original_len - self.processed_len
-                        );
-                    }
-                }
-                unsafe {
-                    self.v.set_len(self.original_len - self.deleted_cnt);
+        let len = self.len();
+        let mut del = 0;
+        {
+            let v = &mut **self;
+
+            for i in 0..len {
+                if !f(&mut v[i]) {
+                    del += 1;
+                } else if del > 0 {
+                    v.swap(i - del, i);
                 }
             }
         }
-
-        let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };
-
-        while g.processed_len < original_len {
-            let cur = unsafe { g.v.as_mut_ptr().add(g.processed_len) };
-            if !f(unsafe { &mut *cur }) {
-                g.processed_len += 1;
-                g.deleted_cnt += 1;
-                unsafe { ptr::drop_in_place(cur) };
-                continue;
-            }
-            if g.deleted_cnt > 0 {
-                unsafe {
-                    let hole_slot = g.v.as_mut_ptr().add(g.processed_len - g.deleted_cnt);
-                    ptr::copy_nonoverlapping(cur, hole_slot, 1);
-                }
-            }
-            g.processed_len += 1;
+        if del > 0 {
+            self.drain(len - del..);
         }
-
-        drop(g);
     }
 
     /// Set the vector’s length without dropping or moving out elements
diff --git a/src/lib.rs b/src/lib.rs
index af11a95..36ec748 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -31,6 +31,16 @@ extern crate core as std;
 pub(crate) type LenUint = u32;
 
 macro_rules! assert_capacity_limit {
+    ($cap:expr) => {
+        if std::mem::size_of::<usize>() > std::mem::size_of::<LenUint>() {
+            if $cap > LenUint::MAX as usize {
+                panic!("ArrayVec: largest supported capacity is u32::MAX")
+            }
+        }
+    }
+}
+
+macro_rules! assert_capacity_limit_const {
     ($cap:expr) => {
         if std::mem::size_of::<usize>() > std::mem::size_of::<LenUint>() {
             if $cap > LenUint::MAX as usize {


Test patch:
diff --git a/tests/tests.rs b/tests/tests.rs
index 662f5e4..ca42c74 100644
--- a/tests/tests.rs
+++ b/tests/tests.rs
@@ -718,19 +718,29 @@ fn allow_max_capacity_arrayvec_type() {
     let _v: ArrayVec<(), {usize::MAX}>;
 }
 
-#[should_panic(expected="index out of bounds")]
+#[should_panic(expected="largest supported capacity")]
 #[test]
 fn deny_max_capacity_arrayvec_value() {
     if mem::size_of::<usize>() <= mem::size_of::<u32>() {
-        panic!("This test does not work on this platform. 'index out of bounds'");
+        panic!("This test does not work on this platform. 'largest supported capacity'");
     }
     // this type is allowed to be used (but can't be constructed)
     let _v: ArrayVec<(), {usize::MAX}> = ArrayVec::new();
 }
 
+#[should_panic(expected="index out of bounds")]
+#[test]
+fn deny_max_capacity_arrayvec_value_const() {
+    if mem::size_of::<usize>() <= mem::size_of::<u32>() {
+        panic!("This test does not work on this platform. 'index out of bounds'");
+    }
+    // this type is allowed to be used (but can't be constructed)
+    let _v: ArrayVec<(), {usize::MAX}> = ArrayVec::new_const();
+}
+
 #[test]
 fn test_arrayvec_const_constructible() {
-    const OF_U8: ArrayVec<Vec<u8>, 10> = ArrayVec::new();
+    const OF_U8: ArrayVec<Vec<u8>, 10> = ArrayVec::new_const();
 
     let mut var = OF_U8;
     assert!(var.is_empty());
@@ -742,7 +752,7 @@ fn test_arrayvec_const_constructible() {
 
 #[test]
 fn test_arraystring_const_constructible() {
-    const AS: ArrayString<10> = ArrayString::new();
+    const AS: ArrayString<10> = ArrayString::new_const();
 
     let mut var = AS;
     assert!(var.is_empty());