Vector: Use memcpy to implement remove() for trivial types

This is a lot faster than the generic code path.
Also added some unit testing for this.

2 files changed, 54 insertions, 4 deletions

diff --git a/AK/Tests/TestVector.cpp b/AK/Tests/TestVector.cpp
index f2b084ead4..351a7aeedd 100644
--- a/AK/Tests/TestVector.cpp
+++ b/AK/Tests/TestVector.cpp
@@ -207,4 +207,49 @@ BENCHMARK_CASE(vector_append_trivial)
     }
 }
 
+BENCHMARK_CASE(vector_remove_trivial)
+{
+    // This should be super fast thanks to Vector using memmove.
+    Vector<int> ints;
+    for (int i = 0; i < 10000; ++i) {
+        ints.append(i);
+    }
+    while (!ints.is_empty()) {
+        ints.remove(0);
+    }
+    EXPECT_EQ(ints.size(), 0);
+}
+
+TEST_CASE(vector_remove)
+{
+    Vector<int> ints;
+    ints.append(1);
+    ints.append(2);
+    ints.append(3);
+    ints.append(4);
+    ints.append(5);
+
+    ints.remove(1);
+    EXPECT_EQ(ints.size(), 4);
+    EXPECT_EQ(ints[0], 1);
+    EXPECT_EQ(ints[1], 3);
+    EXPECT_EQ(ints[2], 4);
+    EXPECT_EQ(ints[3], 5);
+
+    ints.remove(0);
+    EXPECT_EQ(ints.size(), 3);
+    EXPECT_EQ(ints[0], 3);
+    EXPECT_EQ(ints[1], 4);
+    EXPECT_EQ(ints[2], 5);
+
+    ints.take_last();
+    EXPECT_EQ(ints.size(), 2);
+    EXPECT_EQ(ints[0], 3);
+    EXPECT_EQ(ints[1], 4);
+
+    ints.take_first();
+    EXPECT_EQ(ints.size(), 1);
+    EXPECT_EQ(ints[0], 4);
+}
+
 TEST_MAIN(Vector)
diff --git a/AK/Vector.h b/AK/Vector.h
index b2de84b207..22d1692afb 100644
--- a/AK/Vector.h
+++ b/AK/Vector.h
@@ -266,10 +266,15 @@ public:
     void remove(int index)
     {
         ASSERT(index < m_size);
-        at(index).~T();
-        for (int i = index + 1; i < m_size; ++i) {
-            new (slot(i - 1)) T(move(at(i)));
-            at(i).~T();
+
+        if constexpr (Traits<T>::is_trivial()) {
+            TypedTransfer<T>::copy(slot(index), slot(index + 1), m_size - index - 1);
+        } else {
+            at(index).~T();
+            for (int i = index + 1; i < m_size; ++i) {
+                new (slot(i - 1)) T(move(at(i)));
+                at(i).~T();
+            }
         }
 
         --m_size;