From 7bd9ff910d489658da58251de1317eb3f790a2c6 Mon Sep 17 00:00:00 2001 From: Arthur O'Dwyer Date: Sun, 3 Mar 2024 18:47:41 -0800 Subject: PR #1632: inlined_vector: Use trivial relocation for `erase` Imported from GitHub PR https://github.com/abseil/abseil-cpp/pull/1632 Prior art for the `vector::erase` optimization: https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/vectorcommon.hpp#L176-L180 https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslalg/bslalg_arrayprimitives.h#L3787-L3799 https://github.com/facebook/folly/blob/d24bf04/folly/FBVector.h#L1254-L1262 https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/tools/qarraydataops.h#L856-L861 Merge 6ce011079ccf945ae95434ce45ea6c5e3a088af8 into 55d28d4b3b82f9a47b3fa9b811b675a032820621 Merging this change closes #1632 COPYBARA_INTEGRATE_REVIEW=https://github.com/abseil/abseil-cpp/pull/1632 from Quuxplusone:trivial-erase 6ce011079ccf945ae95434ce45ea6c5e3a088af8 PiperOrigin-RevId: 612278964 Change-Id: I327ace8a38292b4610c6be031cc334e77c76fd35 --- absl/container/inlined_vector.h | 13 ++++++++ absl/container/inlined_vector_test.cc | 51 ++++++++++++++++++++++++++++++++ absl/container/internal/inlined_vector.h | 30 ++++++++++++++----- 3 files changed, 86 insertions(+), 8 deletions(-) diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 04e2c385..974b6521 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -775,7 +775,20 @@ class InlinedVector { ABSL_HARDENING_ASSERT(pos >= begin()); ABSL_HARDENING_ASSERT(pos < end()); + // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=102329#c2 + // It appears that GCC thinks that since `pos` is a const pointer and may + // point to uninitialized memory at this point, a warning should be + // issued. But `pos` is actually only used to compute an array index to + // write to. +#if !defined(__clang__) && defined(__GNUC__) +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wmaybe-uninitialized" +#pragma GCC diagnostic ignored "-Wuninitialized" +#endif return storage_.Erase(pos, pos + 1); +#if !defined(__clang__) && defined(__GNUC__) +#pragma GCC diagnostic pop +#endif } // Overload of `InlinedVector::erase(...)` that erases every element in the diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc index 5ecf88a9..6954262e 100644 --- a/absl/container/inlined_vector_test.cc +++ b/absl/container/inlined_vector_test.cc @@ -333,6 +333,57 @@ TEST(UniquePtr, Swap) { } } +// Erasing from a container of unique pointers should work fine, with no +// leaks, despite the fact that unique pointers are trivially relocatable but +// not trivially destructible. +// TODO(absl-team): Using unique_ptr here is technically correct, but +// a trivially relocatable struct would be less semantically confusing. +TEST(UniquePtr, EraseSingle) { + for (size_t size = 4; size < 16; ++size) { + absl::InlinedVector, 8> a; + for (size_t i = 0; i < size; ++i) { + a.push_back(std::make_unique(i)); + } + a.erase(a.begin()); + ASSERT_THAT(a, SizeIs(size - 1)); + for (size_t i = 0; i < size - 1; ++i) { + ASSERT_THAT(a[i], Pointee(i + 1)); + } + a.erase(a.begin() + 2); + ASSERT_THAT(a, SizeIs(size - 2)); + ASSERT_THAT(a[0], Pointee(1)); + ASSERT_THAT(a[1], Pointee(2)); + for (size_t i = 2; i < size - 2; ++i) { + ASSERT_THAT(a[i], Pointee(i + 2)); + } + } +} + +// Erasing from a container of unique pointers should work fine, with no +// leaks, despite the fact that unique pointers are trivially relocatable but +// not trivially destructible. +// TODO(absl-team): Using unique_ptr here is technically correct, but +// a trivially relocatable struct would be less semantically confusing. +TEST(UniquePtr, EraseMulti) { + for (size_t size = 5; size < 16; ++size) { + absl::InlinedVector, 8> a; + for (size_t i = 0; i < size; ++i) { + a.push_back(std::make_unique(i)); + } + a.erase(a.begin(), a.begin() + 2); + ASSERT_THAT(a, SizeIs(size - 2)); + for (size_t i = 0; i < size - 2; ++i) { + ASSERT_THAT(a[i], Pointee(i + 2)); + } + a.erase(a.begin() + 1, a.begin() + 3); + ASSERT_THAT(a, SizeIs(size - 4)); + ASSERT_THAT(a[0], Pointee(2)); + for (size_t i = 1; i < size - 4; ++i) { + ASSERT_THAT(a[i], Pointee(i + 4)); + } + } +} + // At the end of this test loop, the elements between [erase_begin, erase_end) // should have reference counts == 0, and all others elements should have // reference counts == 1. diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index 90a74dc7..a1575328 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -893,16 +893,30 @@ auto Storage::Erase(ConstIterator from, std::distance(ConstIterator(storage_view.data), from)); SizeType erase_end_index = erase_index + erase_size; - IteratorValueAdapter> move_values( - MoveIterator(storage_view.data + erase_end_index)); - - AssignElements(storage_view.data + erase_index, move_values, - storage_view.size - erase_end_index); + // Fast path: if the value type is trivially relocatable and we know + // the allocator doesn't do anything fancy, then we know it is legal for us to + // simply destroy the elements in the "erasure window" (which cannot throw) + // and then memcpy downward to close the window. + if (absl::is_trivially_relocatable>::value && + std::is_nothrow_destructible>::value && + std::is_same>>::value) { + DestroyAdapter::DestroyElements( + GetAllocator(), storage_view.data + erase_index, erase_size); + std::memmove( + reinterpret_cast(storage_view.data + erase_index), + reinterpret_cast(storage_view.data + erase_end_index), + (storage_view.size - erase_end_index) * sizeof(ValueType)); + } else { + IteratorValueAdapter> move_values( + MoveIterator(storage_view.data + erase_end_index)); - DestroyAdapter::DestroyElements( - GetAllocator(), storage_view.data + (storage_view.size - erase_size), - erase_size); + AssignElements(storage_view.data + erase_index, move_values, + storage_view.size - erase_end_index); + DestroyAdapter::DestroyElements( + GetAllocator(), storage_view.data + (storage_view.size - erase_size), + erase_size); + } SubtractSize(erase_size); return Iterator(storage_view.data + erase_index); } -- cgit v1.2.3