From 12b864491fe9750e9fbe09e354374bb441941761 Mon Sep 17 00:00:00 2001 From: Steven Le Rouzic Date: Thu, 2 Jan 2025 19:08:40 +0100 Subject: Optimize buffer move with compatible allocators --- asl/buffer.hpp | 51 +++++++++++++++++++------ asl/memory.hpp | 19 ++++++++++ asl/tests/buffer_tests.cpp | 93 ++++++++++++++++++++++++++++++++++++++++++++++ 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 && 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) { + 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 +constexpr void relocate_assign_n(T* to, T* from, isize_t n) +{ + if constexpr (trivially_move_assignable) + { + static_assert(trivially_destructible); + memcpy(to, from, size_of * 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); +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); + 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 buf; + asl::buffer 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 buf; + asl::buffer 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); +} -- cgit