[webkit-changes] [291540] trunk

Sat, 19 Mar 2022 21:12:25 -0700

Title: [291540] trunk
Revision
291540
Author
cdu...@apple.com
Date
2022-03-19 21:11:32 -0700 (Sat, 19 Mar 2022)

Log Message

Vector move constructor and move assignment operator are suboptimal when the vector has an inline buffer
https://bugs.webkit.org/show_bug.cgi?id=238096

Reviewed by Darin Adler.

Source/WTF:

The move constructor (and move assignment operators) for Vector were implemented using Vector::swap(), which
is fine for vectors with out of line buffers because we're just swapping pointers. However, when the vector
has inline capacity, this is suboptimal because it is not cheap to move data from one inline buffer to another
and moving any data to the source buffer is unnecessary.

* wtf/Vector.h:
(WTF::VectorBuffer::VectorBuffer):
(WTF::VectorBuffer::adopt):
(WTF::Malloc>::Vector):
(WTF::=):

Tools:

Add API test coverage.

* TestWebKitAPI/Tests/WTF/Vector.cpp:
(TestWebKitAPI::TEST):

Modified Paths

Diff

Modified: trunk/Source/WTF/ChangeLog (291539 => 291540)


--- trunk/Source/WTF/ChangeLog	2022-03-20 03:46:37 UTC (rev 291539)
+++ trunk/Source/WTF/ChangeLog	2022-03-20 04:11:32 UTC (rev 291540)
@@ -1,3 +1,21 @@
+2022-03-19  Chris Dumez  <cdu...@apple.com>
+
+        Vector move constructor and move assignment operator are suboptimal when the vector has an inline buffer
+        https://bugs.webkit.org/show_bug.cgi?id=238096
+
+        Reviewed by Darin Adler.
+
+        The move constructor (and move assignment operators) for Vector were implemented using Vector::swap(), which
+        is fine for vectors with out of line buffers because we're just swapping pointers. However, when the vector
+        has inline capacity, this is suboptimal because it is not cheap to move data from one inline buffer to another
+        and moving any data to the source buffer is unnecessary.
+
+        * wtf/Vector.h:
+        (WTF::VectorBuffer::VectorBuffer):
+        (WTF::VectorBuffer::adopt):
+        (WTF::Malloc>::Vector):
+        (WTF::=):
+
 2022-03-18  Philippe Normand  <pnorm...@igalia.com>
 
         [GStreamer] Initial import of the GstWebRTC backend

Modified: trunk/Source/WTF/wtf/Vector.h (291539 => 291540)


--- trunk/Source/WTF/wtf/Vector.h	2022-03-20 03:46:37 UTC (rev 291539)
+++ trunk/Source/WTF/wtf/Vector.h	2022-03-20 04:11:32 UTC (rev 291540)
@@ -435,6 +435,21 @@
 protected:
     using Base::m_size;
 
+    VectorBuffer(VectorBuffer<T, 0, Malloc>&& other)
+    {
+        m_buffer = std::exchange(other.m_buffer, nullptr);
+        m_capacity = std::exchange(other.m_capacity, 0);
+        m_size = std::exchange(other.m_size, 0);
+    }
+
+    void adopt(VectorBuffer&& other)
+    {
+        deallocateBuffer(buffer());
+        m_buffer = std::exchange(other.m_buffer, nullptr);
+        m_capacity = std::exchange(other.m_capacity, 0);
+        m_size = std::exchange(other.m_size, 0);
+    }
+
 private:
     friend class JSC::LLIntOffsetsExtractor;
     using Base::m_buffer;
@@ -556,6 +571,34 @@
 protected:
     using Base::m_size;
 
+    VectorBuffer(VectorBuffer&& other)
+        : Base(inlineBuffer(), inlineCapacity, 0)
+    {
+        if (other.buffer() == other.inlineBuffer())
+            VectorTypeOperations<T>::move(other.inlineBuffer(), other.inlineBuffer() + other.m_size, inlineBuffer());
+        else {
+            m_buffer = std::exchange(other.m_buffer, other.inlineBuffer());
+            m_capacity = std::exchange(other.m_capacity, inlineCapacity);
+        }
+        m_size = std::exchange(other.m_size, 0);
+    }
+
+    void adopt(VectorBuffer&& other)
+    {
+        if (buffer() != inlineBuffer()) {
+            deallocateBuffer(buffer());
+            m_buffer = inlineBuffer();
+        }
+        if (other.buffer() == other.inlineBuffer()) {
+            VectorTypeOperations<T>::move(other.inlineBuffer(), other.inlineBuffer() + other.m_size, inlineBuffer());
+            m_capacity = other.m_capacity;
+        } else {
+            m_buffer = std::exchange(other.m_buffer, other.inlineBuffer());
+            m_capacity = std::exchange(other.m_capacity, inlineCapacity);
+        }
+        m_size = std::exchange(other.m_size, 0);
+    }
+
 private:
     using Base::m_buffer;
     using Base::m_capacity;
@@ -974,14 +1017,24 @@
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::Vector(Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>&& other)
+    : Base(WTFMove(other))
 {
-    swap(other);
 }
 
 template<typename T, size_t inlineCapacity, typename OverflowHandler, size_t minCapacity, typename Malloc>
 inline Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>& Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>::operator=(Vector<T, inlineCapacity, OverflowHandler, minCapacity, Malloc>&& other)
 {
-    swap(other);
+    if (m_size)
+        VectorTypeOperations<T>::destruct(begin(), end());
+
+    // Make it possible to copy inline buffer.
+    asanSetBufferSizeToFullCapacity();
+    other.asanSetBufferSizeToFullCapacity();
+
+    Base::adopt(WTFMove(other));
+
+    asanSetInitialBufferSizeTo(m_size);
+
     return *this;
 }

Modified: trunk/Tools/ChangeLog (291539 => 291540)


--- trunk/Tools/ChangeLog	2022-03-20 03:46:37 UTC (rev 291539)
+++ trunk/Tools/ChangeLog	2022-03-20 04:11:32 UTC (rev 291540)
@@ -1,3 +1,15 @@
+2022-03-19  Chris Dumez  <cdu...@apple.com>
+
+        Vector move constructor and move assignment operator are suboptimal when the vector has an inline buffer
+        https://bugs.webkit.org/show_bug.cgi?id=238096
+
+        Reviewed by Darin Adler.
+
+        Add API test coverage.
+
+        * TestWebKitAPI/Tests/WTF/Vector.cpp:
+        (TestWebKitAPI::TEST):
+
 2022-03-18  Myles C. Maxfield  <mmaxfi...@apple.com>
 
         [Cocoa] Teach WebKit how to serialize CGColors

Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp (291539 => 291540)


--- trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp	2022-03-20 03:46:37 UTC (rev 291539)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/Vector.cpp	2022-03-20 04:11:32 UTC (rev 291540)
@@ -1512,4 +1512,233 @@
     EXPECT_FLOAT_EQ(output[1], 2.0f);
 }
 
+TEST(WTF_Vector, MoveConstructor)
+{
+    {
+        Vector<String> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        Vector<String> strings2(WTFMove(strings));
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 0U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 5U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 10> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 10U);
+        Vector<String, 10> strings2(WTFMove(strings));
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 10U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 10U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 10U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 2> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 5U);
+        Vector<String, 2> strings2(WTFMove(strings));
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 2U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 5U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+}
+
+TEST(WTF_Vector, MoveAssignmentOperator)
+{
+    {
+        Vector<String> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 5U);
+        Vector<String> strings2;
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 0U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 5U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        Vector<String> strings2({ "foo"_str, "bar"_str });
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 0U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 5U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 10> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 10U);
+        Vector<String, 10> strings2;
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 10U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 10U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 10U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 10> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 10U);
+        Vector<String, 10> strings2({ "foo"_str, "bar"_str });
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 10U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 10U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 10U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 2> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 5U);
+        Vector<String, 2> strings2;
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 2U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 5U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 2> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 5U);
+        Vector<String, 2> strings2({ "foo"_str, "bar"_str });
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 2U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 5U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 2> strings({ "a"_str, "b"_str, "c"_str, "d"_str, "e"_str });
+        EXPECT_EQ(strings.size(), 5U);
+        EXPECT_EQ(strings.capacity(), 5U);
+        Vector<String, 2> strings2({ "foo"_str, "bar"_str, "baz"_str });
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 2U);
+        EXPECT_EQ(strings2.size(), 5U);
+        EXPECT_EQ(strings2.capacity(), 5U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+        EXPECT_STREQ(strings2[3].utf8().data(), "d");
+        EXPECT_STREQ(strings2[4].utf8().data(), "e");
+        strings2.append("f"_str);
+        EXPECT_EQ(strings2.size(), 6U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[5].utf8().data(), "f");
+    }
+
+    {
+        Vector<String, 2> strings({ "a"_str, "b"_str });
+        EXPECT_EQ(strings.size(), 2U);
+        EXPECT_EQ(strings.capacity(), 2U);
+        Vector<String, 2> strings2({ "foo"_str, "bar"_str, "baz"_str });
+        strings2 = WTFMove(strings);
+        EXPECT_EQ(strings.size(), 0U);
+        EXPECT_EQ(strings.capacity(), 2U);
+        EXPECT_EQ(strings2.size(), 2U);
+        EXPECT_EQ(strings2.capacity(), 2U);
+        EXPECT_STREQ(strings2[0].utf8().data(), "a");
+        EXPECT_STREQ(strings2[1].utf8().data(), "b");
+        strings2.append("c"_str);
+        EXPECT_EQ(strings2.size(), 3U);
+        EXPECT_EQ(strings2.capacity(), 16U);
+        EXPECT_STREQ(strings2[2].utf8().data(), "c");
+    }
+}
+
 } // namespace TestWebKitAPI

_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to