diff options
| -rw-r--r-- | absl/container/inlined_vector.h | 173 | ||||
| -rw-r--r-- | absl/container/internal/inlined_vector.h | 116 |
2 files changed, 229 insertions, 60 deletions
diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h index 42a4f946..f5b819a1 100644 --- a/absl/container/inlined_vector.h +++ b/absl/container/inlined_vector.h @@ -77,8 +77,6 @@ class InlinedVector { template <typename TheA> using MoveIterator = inlined_vector_internal::MoveIterator<TheA>; template <typename TheA> - using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<TheA>; - template <typename TheA> using IsMoveAssignOk = inlined_vector_internal::IsMoveAssignOk<TheA>; template <typename TheA, typename Iterator> @@ -182,14 +180,33 @@ class InlinedVector { // provided `allocator`. InlinedVector(const InlinedVector& other, const allocator_type& allocator) : storage_(allocator) { + // Fast path: if the other vector is empty, there's nothing for us to do. if (other.empty()) { - // Empty; nothing to do. - } else if (IsMemcpyOk<A>::value && !other.storage_.GetIsAllocated()) { - // Memcpy-able and do not need allocation. + return; + } + + // Fast path: if the value type is trivially copy constructible, we know the + // allocator doesn't do anything fancy, and there is nothing on the heap + // then we know it is legal for us to simply memcpy the other vector's + // inlined bytes to form our copy of its elements. + // + // TODO(b/274984172): the condition on copy-assignability is here only for + // historical reasons. It doesn't make semantic sense: we don't need to be + // able to copy assign here, we are doing an "as-if" copy construction. + // + // TODO(b/274984172): the condition on trivial destructibility is here only + // for historical reasons. It doesn't make sense: there is no destruction + // here. + if (absl::is_trivially_copy_constructible<value_type>::value && + std::is_same<A, std::allocator<value_type>>::value && + absl::is_trivially_copy_assignable<value_type>::value && + absl::is_trivially_destructible<value_type>::value && + !other.storage_.GetIsAllocated()) { storage_.MemcpyFrom(other.storage_); - } else { - storage_.InitFrom(other.storage_); + return; } + + storage_.InitFrom(other.storage_); } // Creates an inlined vector by moving in the contents of `other` without @@ -210,26 +227,57 @@ class InlinedVector { absl::allocator_is_nothrow<allocator_type>::value || std::is_nothrow_move_constructible<value_type>::value) : storage_(other.storage_.GetAllocator()) { - if (IsMemcpyOk<A>::value) { + // Fast path: if the value type can be trivally move constructed and + // destroyed, and we know the allocator doesn't do anything fancy, then it's + // safe for us to simply adopt the contents of the storage for `other` and + // remove its own reference to them. It's as if we had individually + // move-constructed each value and then destroyed the original. + // + // TODO(b/274984172): we check for copy-constructibility here only for + // historical reasons. This is too strict: we are simulating move + // construction here. In fact this is arguably incorrect, since in theory a + // type might be trivially copy-constructible but not trivially + // move-constructible. + // + // TODO(b/274984172): the condition on copy-assignability is here only for + // historical reasons. It doesn't make semantic sense: we don't need to be + // able to copy assign here, we are doing an "as-if" move construction. + // + // TODO(b/274984172): a move construction followed by destroying the source + // is a "relocation" in the language of P1144R4. So actually the minimum + // condition we need here (in addition to the allocator) is "trivially + // relocatable". Relaxing this would allow using memcpy with types like + // std::unique_ptr that opt in to declaring themselves trivially relocatable + // despite not being trivially move-constructible and/oror destructible. + if (absl::is_trivially_copy_constructible<value_type>::value && + absl::is_trivially_destructible<value_type>::value && + std::is_same<A, std::allocator<value_type>>::value && + absl::is_trivially_copy_assignable<value_type>::value) { storage_.MemcpyFrom(other.storage_); - other.storage_.SetInlinedSize(0); - } else if (other.storage_.GetIsAllocated()) { + return; + } + + // Fast path: if the other vector is on the heap, we can simply take over + // its allocation. + if (other.storage_.GetIsAllocated()) { storage_.SetAllocation({other.storage_.GetAllocatedData(), other.storage_.GetAllocatedCapacity()}); storage_.SetAllocatedSize(other.storage_.GetSize()); other.storage_.SetInlinedSize(0); - } else { - IteratorValueAdapter<A, MoveIterator<A>> other_values( - MoveIterator<A>(other.storage_.GetInlinedData())); + return; + } - inlined_vector_internal::ConstructElements<A>( - storage_.GetAllocator(), storage_.GetInlinedData(), other_values, - other.storage_.GetSize()); + // Otherwise we must move each element individually. + IteratorValueAdapter<A, MoveIterator<A>> other_values( + MoveIterator<A>(other.storage_.GetInlinedData())); - storage_.SetInlinedSize(other.storage_.GetSize()); - } + inlined_vector_internal::ConstructElements<A>( + storage_.GetAllocator(), storage_.GetInlinedData(), other_values, + other.storage_.GetSize()); + + storage_.SetInlinedSize(other.storage_.GetSize()); } // Creates an inlined vector by moving in the contents of `other` with a copy @@ -244,22 +292,53 @@ class InlinedVector { const allocator_type& allocator) noexcept(absl::allocator_is_nothrow<allocator_type>::value) : storage_(allocator) { - if (IsMemcpyOk<A>::value) { + // Fast path: if the value type can be trivally move constructed and + // destroyed and we know the allocator doesn't do anything fancy, then it's + // safe for us to simply adopt the contents of the storage for `other` and + // remove its own reference to them. It's as if we had individually + // move-constructed each value and then destroyed the original. + // + // TODO(b/274984172): we check for copy-constructibility here only for + // historical reasons. This is too strict: we are simulating move + // construction here. In fact this is arguably incorrect, since in theory a + // type might be trivially copy-constructible but not trivially + // move-constructible. + // + // TODO(b/274984172): the condition on copy-assignability is here only for + // historical reasons. It doesn't make semantic sense: we don't need to be + // able to copy assign here, we are doing an "as-if" move construction. + // + // TODO(b/274984172): a move construction followed by destroying the source + // is a "relocation" in the language of P1144R4. So actually the minimum + // condition we need here (in addition to the allocator) is "trivially + // relocatable". Relaxing this would allow using memcpy with types like + // std::unique_ptr that opt in to declaring themselves trivially relocatable + // despite not being trivially move-constructible and/oror destructible. + if (absl::is_trivially_copy_constructible<value_type>::value && + absl::is_trivially_destructible<value_type>::value && + std::is_same<A, std::allocator<value_type>>::value && + absl::is_trivially_copy_assignable<value_type>::value) { storage_.MemcpyFrom(other.storage_); - other.storage_.SetInlinedSize(0); - } else if ((storage_.GetAllocator() == other.storage_.GetAllocator()) && - other.storage_.GetIsAllocated()) { + return; + } + + // Fast path: if the other vector is on the heap and shared the same + // allocator, we can simply take over its allocation. + if ((storage_.GetAllocator() == other.storage_.GetAllocator()) && + other.storage_.GetIsAllocated()) { storage_.SetAllocation({other.storage_.GetAllocatedData(), other.storage_.GetAllocatedCapacity()}); storage_.SetAllocatedSize(other.storage_.GetSize()); other.storage_.SetInlinedSize(0); - } else { - storage_.Initialize(IteratorValueAdapter<A, MoveIterator<A>>( - MoveIterator<A>(other.data())), - other.size()); + return; } + + // Otherwise we must move each element individually. + storage_.Initialize( + IteratorValueAdapter<A, MoveIterator<A>>(MoveIterator<A>(other.data())), + other.size()); } ~InlinedVector() {} @@ -784,6 +863,10 @@ class InlinedVector { friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a); void MoveAssignment(MemcpyPolicy, InlinedVector&& other) { + // TODO(b/274984172): we shouldn't need to do this. We already know the + // elements are trivially destructible when our move-assignment policy is + // MemcpyPolicy. Except the other overloads of MoveAssignment call this one. + // Make them not. inlined_vector_internal::DestroyAdapter<A>::DestroyElements( storage_.GetAllocator(), data(), size()); storage_.DeallocateIfAllocated(); @@ -793,30 +876,38 @@ class InlinedVector { } void MoveAssignment(ElementwiseAssignPolicy, InlinedVector&& other) { + // Fast path: if the other vector is on the heap then we don't worry about + // actually move-assigning each element. Instead we only throw away our own + // existing elements and adopt the heap allocation of the other vector. if (other.storage_.GetIsAllocated()) { MoveAssignment(MemcpyPolicy{}, std::move(other)); - } else { - storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>( - MoveIterator<A>(other.storage_.GetInlinedData())), - other.size()); + return; } + + storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>( + MoveIterator<A>(other.storage_.GetInlinedData())), + other.size()); } void MoveAssignment(ElementwiseConstructPolicy, InlinedVector&& other) { + // Fast path: if the other vector is on the heap then we don't worry about + // actually move-assigning each element. Instead we only throw away our own + // existing elements and adopt the heap allocation of the other vector. if (other.storage_.GetIsAllocated()) { MoveAssignment(MemcpyPolicy{}, std::move(other)); - } else { - inlined_vector_internal::DestroyAdapter<A>::DestroyElements( - storage_.GetAllocator(), data(), size()); - storage_.DeallocateIfAllocated(); - - IteratorValueAdapter<A, MoveIterator<A>> other_values( - MoveIterator<A>(other.storage_.GetInlinedData())); - inlined_vector_internal::ConstructElements<A>( - storage_.GetAllocator(), storage_.GetInlinedData(), other_values, - other.storage_.GetSize()); - storage_.SetInlinedSize(other.storage_.GetSize()); + return; } + + inlined_vector_internal::DestroyAdapter<A>::DestroyElements( + storage_.GetAllocator(), data(), size()); + storage_.DeallocateIfAllocated(); + + IteratorValueAdapter<A, MoveIterator<A>> other_values( + MoveIterator<A>(other.storage_.GetInlinedData())); + inlined_vector_internal::ConstructElements<A>( + storage_.GetAllocator(), storage_.GetInlinedData(), other_values, + other.storage_.GetSize()); + storage_.SetInlinedSize(other.storage_.GetSize()); } Storage storage_; diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h index 0398f530..3cd69b55 100644 --- a/absl/container/internal/inlined_vector.h +++ b/absl/container/internal/inlined_vector.h @@ -77,13 +77,6 @@ using IsAtLeastForwardIterator = std::is_convertible< std::forward_iterator_tag>; template <typename A> -using IsMemcpyOk = - absl::conjunction<std::is_same<A, std::allocator<ValueType<A>>>, - absl::is_trivially_copy_constructible<ValueType<A>>, - absl::is_trivially_copy_assignable<ValueType<A>>, - absl::is_trivially_destructible<ValueType<A>>>; - -template <typename A> using IsMoveAssignOk = std::is_move_assignable<ValueType<A>>; template <typename A> using IsSwapOk = absl::type_traits_internal::IsSwappable<ValueType<A>>; @@ -308,11 +301,51 @@ class Storage { struct ElementwiseConstructPolicy {}; using MoveAssignmentPolicy = absl::conditional_t< - IsMemcpyOk<A>::value, MemcpyPolicy, + // Fast path: if the value type can be trivally move assigned and + // destroyed, and we know the allocator doesn't do anything fancy, then + // it's safe for us to simply adopt the contents of the storage for + // `other` and remove its own reference to them. It's as if we had + // individually move-assigned each value and then destroyed the original. + // + // TODO(b/274984172): we check for copy-assignability here only for + // historical reasons. This is too strict: we are simulating move + // assignment here. + // + // TODO(b/274984172): the condition on copy-constructibility is here only + // for historical reasons. It doesn't make semantic sense: we don't need + // to be able to copy construct here, we are doing an "as-if" move + // assignment. + absl::conjunction< + absl::is_trivially_copy_assignable<ValueType<A>>, + absl::is_trivially_destructible<ValueType<A>>, + std::is_same<A, std::allocator<ValueType<A>>>, + absl::is_trivially_copy_constructible<ValueType<A>>>::value, + MemcpyPolicy, + // Otherwise we use move assignment if possible. If not, we simulate + // move assignment using move construction. + // + // Note that this is in contrast to e.g. std::vector and std::optional, + // which are themselves not move-assignable when their contained type is + // not. absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy, ElementwiseConstructPolicy>>; - using SwapPolicy = absl::conditional_t< - IsMemcpyOk<A>::value, MemcpyPolicy, + + // The policy to be used specifically when swapping inlined elements. + using SwapInlinedElementsPolicy = absl::conditional_t< + // Fast path: if the value type can be trivally move constructed/assigned + // and destroyed, and we know the allocator doesn't do anything fancy, + // then it's safe for us to simply swap the bytes in the inline storage. + // It's as if we had move-constructed a temporary vector, move-assigned + // one to the other, then move-assigned the first from the temporary. + // + // TODO(b/274984172): we check for copy-constructability and + // -assignability here only for historical reasons. This is too strict: we + // are simulating move operations here. + absl::conjunction<absl::is_trivially_copy_constructible<ValueType<A>>, + absl::is_trivially_copy_assignable<ValueType<A>>, + absl::is_trivially_destructible<ValueType<A>>, + std::is_same<A, std::allocator<ValueType<A>>>>::value, + MemcpyPolicy, absl::conditional_t<IsSwapOk<A>::value, ElementwiseSwapPolicy, ElementwiseConstructPolicy>>; @@ -335,14 +368,26 @@ class Storage { : metadata_(allocator, /* size and is_allocated */ 0u) {} ~Storage() { + // Fast path: if we are empty and not allocated, there's nothing to do. if (GetSizeAndIsAllocated() == 0) { - // Empty and not allocated; nothing to do. - } else if (IsMemcpyOk<A>::value) { - // No destructors need to be run; just deallocate if necessary. + return; + } + + // Fast path: if no destructors need to be run and we know the allocator + // doesn't do anything fancy, then all we need to do is allocate (and maybe + // not even that). + // + // TODO(b/274984172): the conditions on copy constructibility/assignability + // are unnecessary, and are here only for historical reasons. Remove them. + if (absl::is_trivially_destructible<ValueType<A>>::value && + std::is_same<A, std::allocator<ValueType<A>>>::value && + absl::is_trivially_copy_constructible<ValueType<A>>::value && + absl::is_trivially_copy_assignable<ValueType<A>>::value) { DeallocateIfAllocated(); - } else { - DestroyContents(); + return; } + + DestroyContents(); } // --------------------------------------------------------------------------- @@ -461,8 +506,25 @@ class Storage { } void MemcpyFrom(const Storage& other_storage) { - ABSL_HARDENING_ASSERT(IsMemcpyOk<A>::value || - other_storage.GetIsAllocated()); + // Assumption check: it doesn't make sense to memcpy inlined elements unless + // we know the allocator doesn't do anything fancy, and one of the following + // holds: + // + // * It's possible to trivially move construct/assign the elements and + // then destroy the source. + // + // * It's possible to trivially copy construct/assign the elements. + // + // TODO(b/274984172): the conditions here, preserved from historical ones, + // don't actually implement this. They are far too conservative (they don't + // work for move-only types, and require both copyability and + // assignability). + ABSL_HARDENING_ASSERT( + other_storage.GetIsAllocated() || + (std::is_same<A, std::allocator<ValueType<A>>>::value && + absl::is_trivially_copy_constructible<ValueType<A>>::value && + absl::is_trivially_copy_assignable<ValueType<A>>::value && + absl::is_trivially_destructible<ValueType<A>>::value)); GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated(); data_ = other_storage.data_; @@ -542,13 +604,29 @@ void Storage<T, N, A>::InitFrom(const Storage& other) { dst = allocation.data; src = other.GetAllocatedData(); } - if (IsMemcpyOk<A>::value) { + + // Fast path: if the value type is trivially copy constructible and we know + // the allocator doesn't do anything fancy, then we know it is legal for us to + // simply memcpy the other vector's elements. + // + // TODO(b/274984172): the condition on copy-assignability is here only for + // historical reasons. It doesn't make semantic sense: we don't need to be + // able to copy assign here, we are doing an "as-if" copy construction. + // + // TODO(b/274984172): the condition on trivial destructibility is here only + // for historical reasons. It doesn't make sense: there is no destruction + // here. + if (absl::is_trivially_copy_constructible<ValueType<A>>::value && + std::is_same<A, std::allocator<ValueType<A>>>::value && + absl::is_trivially_copy_assignable<ValueType<A>>::value && + absl::is_trivially_destructible<ValueType<A>>::value) { std::memcpy(reinterpret_cast<char*>(dst), reinterpret_cast<const char*>(src), n * sizeof(ValueType<A>)); } else { auto values = IteratorValueAdapter<A, ConstPointer<A>>(src); ConstructElements<A>(GetAllocator(), dst, values, n); } + GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated(); } @@ -921,7 +999,7 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void { if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) { swap(data_.allocated, other_storage_ptr->data_.allocated); } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) { - SwapInlinedElements(SwapPolicy{}, other_storage_ptr); + SwapInlinedElements(SwapInlinedElementsPolicy{}, other_storage_ptr); } else { Storage* allocated_ptr = this; Storage* inlined_ptr = other_storage_ptr; |