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
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 04e2c38..974b652 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -775,7 +775,20 @@
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 5ecf88a..6954262 100644
--- a/absl/container/inlined_vector_test.cc
+++ b/absl/container/inlined_vector_test.cc
@@ -333,6 +333,57 @@
}
}
+// 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<std::unique_ptr<size_t>, 8> a;
+ for (size_t i = 0; i < size; ++i) {
+ a.push_back(std::make_unique<size_t>(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<std::unique_ptr<size_t>, 8> a;
+ for (size_t i = 0; i < size; ++i) {
+ a.push_back(std::make_unique<size_t>(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 90a74dc..a157532 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -893,16 +893,30 @@
std::distance(ConstIterator<A>(storage_view.data), from));
SizeType<A> erase_end_index = erase_index + erase_size;
- IteratorValueAdapter<A, MoveIterator<A>> move_values(
- MoveIterator<A>(storage_view.data + 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<ValueType<A>>::value &&
+ std::is_nothrow_destructible<ValueType<A>>::value &&
+ std::is_same<A, std::allocator<ValueType<A>>>::value) {
+ DestroyAdapter<A>::DestroyElements(
+ GetAllocator(), storage_view.data + erase_index, erase_size);
+ std::memmove(
+ reinterpret_cast<char*>(storage_view.data + erase_index),
+ reinterpret_cast<const char*>(storage_view.data + erase_end_index),
+ (storage_view.size - erase_end_index) * sizeof(ValueType<A>));
+ } else {
+ IteratorValueAdapter<A, MoveIterator<A>> move_values(
+ MoveIterator<A>(storage_view.data + erase_end_index));
- AssignElements<A>(storage_view.data + erase_index, move_values,
- storage_view.size - erase_end_index);
+ AssignElements<A>(storage_view.data + erase_index, move_values,
+ storage_view.size - erase_end_index);
- DestroyAdapter<A>::DestroyElements(
- GetAllocator(), storage_view.data + (storage_view.size - erase_size),
- erase_size);
-
+ DestroyAdapter<A>::DestroyElements(
+ GetAllocator(), storage_view.data + (storage_view.size - erase_size),
+ erase_size);
+ }
SubtractSize(erase_size);
return Iterator<A>(storage_view.data + erase_index);
}
