Optimize buffer move with compatible allocators

3 files changed, 151 insertions, 12 deletions

diff --git a/asl/buffer.hpp b/asl/buffer.hpp
index a616011..ca371d2 100644
--- a/asl/buffer.hpp
+++ b/asl/buffer.hpp
@@ -86,11 +86,21 @@ private:
     constexpr T* push_uninit()

     {

         isize_t sz = size();

-        reserve_capacity(sz + 1);

-        set_size(sz + 1);

+        resize_uninit(sz + 1);

         return data() + sz;

     }

 

+    constexpr void resize_uninit(isize_t new_size)

+    {

+        isize_t old_size = size();

+        if (!trivially_destructible<T> && new_size < old_size)

+        {

+            destroy_n(data() + new_size, old_size - new_size);

+        }

+        reserve_capacity(new_size);

+        set_size(new_size);

+    }

+

     constexpr void set_size_inline(isize_t new_size)

     {

         ASL_ASSERT(new_size >= 0 && new_size <= kInlineCapacity);

@@ -112,22 +122,38 @@ private:
     }

 

     // NOLINTNEXTLINE(*-rvalue-reference-param-not-moved)

-    void move_from_other(buffer&& other)

+    void move_from_other(buffer&& other, bool assign)

     {

-        ASL_ASSERT(size() == 0 && !is_on_heap());

-        

         if (other.is_on_heap())

         {

+            destroy();

             m_data = other.m_data;

             m_capacity = other.m_capacity;

             store_size_encoded(other.load_size_encoded());

         }

         else if (trivially_move_constructible<T>)

         {

+            destroy();

             asl::memcpy(this, &other, kInlineRegionSize);

         }

+        else if (!assign || m_allocator == other.m_allocator)

+        {

+            isize_t other_n = other.size();

+            isize_t this_n = size();

+            resize_uninit(other_n);

+            if (other_n < this_n)

+            {

+                relocate_assign_n(data(), other.data(), other_n);

+            }

+            else

+            {

+                relocate_assign_n(data(), other.data(), this_n);

+                relocate_uninit_n(data() + this_n, other.data() + this_n, other_n - this_n);

+            }

+        }

         else

         {

+            destroy();

             isize_t n = other.size();

             ASL_ASSERT(n <= kInlineCapacity);

             relocate_uninit_n(data(), other.data(), n);

@@ -135,6 +161,11 @@ private:
         }

 

         other.set_size_inline(0);

+        

+        if (assign)

+        {

+            m_allocator = ASL_MOVE(other.m_allocator);

+        }

     }

 

 public:

@@ -147,17 +178,13 @@ public:
     constexpr buffer(buffer&& other)

         : buffer(ASL_MOVE(other.m_allocator))

     {

-        move_from_other(ASL_MOVE(other));

+        move_from_other(ASL_MOVE(other), false);

     }

 

     constexpr buffer& operator=(buffer&& other)

     {

         if (&other == this) { return *this; }

-

-        destroy();

-        m_allocator = ASL_MOVE(other.m_allocator);

-        move_from_other(ASL_MOVE(other));

-

+        move_from_other(ASL_MOVE(other), true);

         return *this;

     }

 

@@ -166,7 +193,7 @@ public:
         destroy();

     }

 

-    // @Todo Copy/move constructor & assignment

+    // @Todo Copy constructor & assignment

 

     constexpr isize_t size() const

     {

diff --git a/asl/memory.hpp b/asl/memory.hpp
index cfc7057..1209bf6 100644
--- a/asl/memory.hpp
+++ b/asl/memory.hpp
@@ -75,5 +75,24 @@ constexpr void relocate_uninit_n(T* to, T* from, isize_t n)
     }

 }

 

+template<move_assignable T>

+constexpr void relocate_assign_n(T* to, T* from, isize_t n)

+{

+    if constexpr (trivially_move_assignable<T>)

+    {

+        static_assert(trivially_destructible<T>);

+        memcpy(to, from, size_of<T> * n);

+    }

+    else

+    {

+        for (isize_t i = 0; i < n; ++i)

+        {

+            // NOLINTNEXTLINE(*-pointer-arithmetic)

+            to[i] = ASL_MOVE(from[i]);

+        }

+        destroy_n(from, n);

+    }

+}

+

 } // namespace asl

 

diff --git a/asl/tests/buffer_tests.cpp b/asl/tests/buffer_tests.cpp
index cc34420..1a08554 100644
--- a/asl/tests/buffer_tests.cpp
+++ b/asl/tests/buffer_tests.cpp
@@ -51,6 +51,27 @@ struct CounterAllocator
 };

 static_assert(asl::allocator<CounterAllocator>);

 

+struct IncompatibleAllocator

+{

+    static void* alloc(const asl::layout& layout)

+    {

+        return asl::GlobalHeap::alloc(layout);

+    }

+    

+    static void* realloc(void* ptr, const asl::layout& old, const asl::layout& new_layout)

+    {

+        return asl::GlobalHeap::realloc(ptr, old, new_layout);

+    }

+    

+    static void dealloc(void* ptr, const asl::layout& layout)

+    {

+        asl::GlobalHeap::dealloc(ptr, layout);

+    }

+

+    constexpr bool operator==(const IncompatibleAllocator&) const { return false; }

+};

+static_assert(asl::allocator<IncompatibleAllocator>);

+

 ASL_TEST(reserve_capacity)

 {

     isize_t count = 0;

@@ -376,3 +397,75 @@ ASL_TEST(move_assign_trivial_inline_to_heap)
     ASL_TEST_EXPECT(buf2[0] == 1);

     ASL_TEST_EXPECT(buf2[1] == 2);

 }

+

+ASL_TEST(move_assign_inline_to_heap)

+{

+    bool d[6]{};

+

+    {

+        asl::buffer<DestructorObserver> buf;

+        asl::buffer<DestructorObserver> buf2;

+

+        buf.push(&d[0]);

+        buf.push(&d[1]);

+

+        buf2.push(&d[2]);

+        buf2.push(&d[3]);

+        buf2.push(&d[4]);

+        buf2.push(&d[5]);

+

+        buf2 = ASL_MOVE(buf);

+

+        ASL_TEST_EXPECT(buf.size() == 0);

+        ASL_TEST_EXPECT(buf2.size() == 2);

+        ASL_TEST_EXPECT(d[0] == false);

+        ASL_TEST_EXPECT(d[1] == false);

+        ASL_TEST_EXPECT(d[2] == false); // moved but not destroyed

+        ASL_TEST_EXPECT(d[3] == false); // moved but not destroyed

+        ASL_TEST_EXPECT(d[4] == true);

+        ASL_TEST_EXPECT(d[5] == true);

+    }

+    

+    ASL_TEST_EXPECT(d[0] == true);

+    ASL_TEST_EXPECT(d[1] == true);

+    ASL_TEST_EXPECT(d[2] == false); // moved but not destroyed

+    ASL_TEST_EXPECT(d[3] == false); // moved but not destroyed

+    ASL_TEST_EXPECT(d[4] == true);

+    ASL_TEST_EXPECT(d[5] == true);

+}

+

+ASL_TEST(move_assign_from_inline_incompatible_allocator)

+{

+    bool d[6]{};

+

+    {

+        asl::buffer<DestructorObserver, IncompatibleAllocator> buf;

+        asl::buffer<DestructorObserver, IncompatibleAllocator> buf2;

+

+        buf.push(&d[0]);

+        buf.push(&d[1]);

+

+        buf2.push(&d[2]);

+        buf2.push(&d[3]);

+        buf2.push(&d[4]);

+        buf2.push(&d[5]);

+

+        buf2 = ASL_MOVE(buf);

+

+        ASL_TEST_EXPECT(buf.size() == 0);

+        ASL_TEST_EXPECT(buf2.size() == 2);

+        ASL_TEST_EXPECT(d[0] == false);

+        ASL_TEST_EXPECT(d[1] == false);

+        ASL_TEST_EXPECT(d[2] == true);

+        ASL_TEST_EXPECT(d[3] == true);

+        ASL_TEST_EXPECT(d[4] == true);

+        ASL_TEST_EXPECT(d[5] == true);

+    }

+    

+    ASL_TEST_EXPECT(d[0] == true);

+    ASL_TEST_EXPECT(d[1] == true);

+    ASL_TEST_EXPECT(d[2] == true);

+    ASL_TEST_EXPECT(d[3] == true);

+    ASL_TEST_EXPECT(d[4] == true);

+    ASL_TEST_EXPECT(d[5] == true);

+}