diff --git a/llvm/include/llvm/ADT/SmallVector.h b/llvm/include/llvm/ADT/SmallVector.h --- a/llvm/include/llvm/ADT/SmallVector.h +++ b/llvm/include/llvm/ADT/SmallVector.h @@ -101,6 +101,10 @@ AlignedCharArrayUnion FirstEl; }; +namespace detail { +template class GrowBufferBase; +} // namespace detail + /// This is the part of SmallVectorTemplateBase which does not depend on whether /// the type T is a POD. The extra dummy template argument is used by ArrayRef /// to avoid unnecessarily requiring T to be complete. @@ -108,6 +112,7 @@ class SmallVectorTemplateCommon : public SmallVectorBase> { using Base = SmallVectorBase>; + friend class detail::GrowBufferBase; /// Find the address of the first element. For this pointer math to be valid /// with small-size of 0 for T with lots of alignment, it's important that @@ -136,6 +141,23 @@ this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect. } + size_t grow_size(size_t MinSize = 0) { + // Ensure we can fit the new capacity. + // This is only going to be applicable when the capacity is 32 bit. + if (MinSize > this->SizeTypeMax()) + this->report_size_overflow(MinSize); + + // Ensure we can meet the guarantee of space for at least one more element. + // The above check alone will not catch the case where grow is called with a + // default MinSize of 0, but the current capacity cannot be increased. + // This is only going to be applicable when the capacity is 32 bit. + if (this->capacity() == this->SizeTypeMax()) + this->report_at_maximum_capacity(); + // Always grow, even from zero. + size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2)); + return std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax()); + } + public: using size_type = size_t; using difference_type = ptrdiff_t; @@ -207,6 +229,151 @@ } }; +namespace detail { +template +static constexpr bool + is_pod_like_v = (is_trivially_copy_constructible::value) && + (is_trivially_move_constructible::value) && + std::is_trivially_destructible::value; + +template class GrowBufferBase { +public: + using Size_T = SmallVectorSizeType; + + GrowBufferBase(Size_T Size, Size_T Capacity) + : Size(Size), Capacity(Capacity) { + BeginX = llvm::safe_malloc(sizeof(T) * Capacity); + } + + ~GrowBufferBase() { + assert(BeginX == nullptr && "Buffers haven't been swapped out"); + } + +protected: + T *begin() { return static_cast(BeginX); } + T *end() { return begin() + Size; } + void *BeginX; + Size_T Size, Capacity; + + void take_buffers(SmallVectorTemplateCommon &Vec) { + if (!Vec.isSmall()) + free(Vec.begin()); + Vec.BeginX = BeginX; + Vec.Size = Size; + Vec.Capacity = Capacity; + BeginX = nullptr; + Size = 0U; + Capacity = 0U; + } +}; + +template > +class GrowBuffer : public GrowBufferBase { +public: + using GrowBufferBase::GrowBufferBase; + + using Size_T = typename GrowBufferBase::Size_T; + void default_construct_at_end(Size_T Count) { + assert((this->Size + Count) <= this->Capacity && + "Overflowed GrowBuffer storage"); + T *First = this->end(); + this->Size += Count; + T *Last = this->end(); + for (; First != Last; ++First) { + new (static_cast(First)) T; + } + } + + void push_back(const T &Elt) { + assert(this->Size < this->Capacity && "Overflowed GrowBuffer storage"); + new (static_cast(this->end())) T(Elt); + ++this->Size; + } + + void push_back(T &&Elt) { + assert(this->Size < this->Capacity && "Overflowed GrowBuffer storage"); + new (static_cast(this->end())) T(std::move(Elt)); + ++this->Size; + } + + void append(Size_T Count, const T &Elt) { + assert((this->Size + Count) <= this->Capacity && + "Overflowed GrowBuffer storage"); + std::uninitialized_fill_n(this->end(), Count, Elt); + this->Size += Count; + } + + void swap_out_buffer(SmallVectorTemplateCommon &Vec) { + auto Begin = std::make_move_iterator(Vec.rbegin()); + auto End = std::make_move_iterator(Vec.rend()); + auto Src = std::reverse_iterator(this->begin() + Vec.size()); + std::uninitialized_copy(Begin, End, Src); + // Destory the items in the old vector. + std::for_each(Vec.begin(), Vec.end(), [](T &I) { I.~T(); }); + this->take_buffers(Vec); + } + + void swap_out_split_buffer(SmallVectorTemplateCommon &Vec, + Size_T SplitIndex) { + std::uninitialized_copy( + std::make_move_iterator( + std::reverse_iterator(Vec.begin() + SplitIndex)), + std::make_move_iterator(Vec.rend()), + std::reverse_iterator(this->begin() + SplitIndex)); + std::uninitialized_copy(std::make_move_iterator(&Vec[SplitIndex]), + std::make_move_iterator(Vec.end()), this->end()); + this->Size += Vec.size() - SplitIndex; + // Destory the items in the old vector. + std::for_each(Vec.begin(), Vec.end(), [](T &I) { I.~T(); }); + this->take_buffers(Vec); + } +}; + +template class GrowBuffer : public GrowBufferBase { +public: + using GrowBufferBase::GrowBufferBase; + using Size_T = typename GrowBufferBase::Size_T; + void default_construct_at_end(Size_T Count) { + assert((this->Size + Count) <= this->Capacity && + "Overflowed GrowBuffer storage"); + // No need to do any construction here. + this->Size += Count; + } + + void push_back(const T &Elt) { + assert(this->Size < this->Capacity && "Overflowed GrowBuffer storage"); + memcpy(this->end(), &Elt, sizeof(Elt)); + ++this->Size; + } + + void append(Size_T Count, const T &Elt) { + assert((this->Size + Count) <= this->Capacity && + "Overflowed GrowBuffer storage"); + T *First = this->end(); + this->Size += Count; + T *Last = this->end(); + for (; First != Last; ++First) { + memcpy(First, &Elt, sizeof(Elt)); + } + } + + void swap_out_buffer(SmallVectorTemplateCommon &Vec) { + memcpy(this->begin(), Vec.begin(), Vec.size_in_bytes()); + this->take_buffers(Vec); + } + + void swap_out_split_buffer(SmallVectorTemplateCommon &Vec, + Size_T SplitIndex) { + memcpy(this->begin(), Vec.begin(), SplitIndex * sizeof(T)); + memcpy(this->end(), &Vec[SplitIndex], + (Vec.size() - SplitIndex) * sizeof(T)); + this->Size += Vec.size() - SplitIndex; + this->take_buffers(Vec); + } +}; + +} // namespace detail + /// SmallVectorTemplateBase - This is where we put /// method implementations that are designed to work with non-trivial T's. /// @@ -215,9 +382,7 @@ /// copy these types with memcpy, there is no way for the type to observe this. /// This catches the important case of std::pair, which is not /// trivially assignable. -template ::value) && - (is_trivially_move_constructible::value) && - std::is_trivially_destructible::value> +template > class SmallVectorTemplateBase : public SmallVectorTemplateCommon { protected: SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon(Size) {} @@ -251,15 +416,23 @@ public: void push_back(const T &Elt) { - if (LLVM_UNLIKELY(this->size() >= this->capacity())) - this->grow(); + if (LLVM_UNLIKELY(this->size() >= this->capacity())) { + detail::GrowBuffer Buffer(this->size(), this->grow_size()); + Buffer.push_back(Elt); + Buffer.swap_out_buffer(*this); + return; + } ::new ((void*) this->end()) T(Elt); this->set_size(this->size() + 1); } void push_back(T &&Elt) { - if (LLVM_UNLIKELY(this->size() >= this->capacity())) - this->grow(); + if (LLVM_UNLIKELY(this->size() >= this->capacity())) { + detail::GrowBuffer Buffer(this->size(), this->grow_size()); + Buffer.push_back(std::move(Elt)); + Buffer.swap_out_buffer(*this); + return; + } ::new ((void*) this->end()) T(::std::move(Elt)); this->set_size(this->size() + 1); } @@ -273,21 +446,7 @@ // Define this out-of-line to dissuade the C++ compiler from inlining it. template void SmallVectorTemplateBase::grow(size_t MinSize) { - // Ensure we can fit the new capacity. - // This is only going to be applicable when the capacity is 32 bit. - if (MinSize > this->SizeTypeMax()) - this->report_size_overflow(MinSize); - - // Ensure we can meet the guarantee of space for at least one more element. - // The above check alone will not catch the case where grow is called with a - // default MinSize of 0, but the current capacity cannot be increased. - // This is only going to be applicable when the capacity is 32 bit. - if (this->capacity() == this->SizeTypeMax()) - this->report_at_maximum_capacity(); - - // Always grow, even from zero. - size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2)); - NewCapacity = std::min(std::max(NewCapacity, MinSize), this->SizeTypeMax()); + size_t NewCapacity = this->grow_size(MinSize); T *NewElts = static_cast(llvm::safe_malloc(NewCapacity*sizeof(T))); // Move the elements over. @@ -353,8 +512,12 @@ public: void push_back(const T &Elt) { - if (LLVM_UNLIKELY(this->size() >= this->capacity())) - this->grow(); + if (LLVM_UNLIKELY(this->size() >= this->capacity())) { + detail::GrowBuffer Buffer(this->size(), this->grow_size()); + Buffer.push_back(Elt); + Buffer.swap_out_buffer(*this); + return; + } memcpy(reinterpret_cast(this->end()), &Elt, sizeof(T)); this->set_size(this->size() + 1); } @@ -412,8 +575,12 @@ this->destroy_range(this->begin()+N, this->end()); this->set_size(N); } else if (N > this->size()) { - if (this->capacity() < N) - this->grow(N); + if (this->capacity() < N) { + detail::GrowBuffer Buffer(this->size(), this->grow_size(N)); + Buffer.append(N - this->size(), NV); + Buffer.swap_out_buffer(*this); + return; + } std::uninitialized_fill(this->end(), this->begin()+N, NV); this->set_size(N); } @@ -448,8 +615,13 @@ /// Append \p NumInputs copies of \p Elt to the end. void append(size_type NumInputs, const T &Elt) { - if (NumInputs > this->capacity() - this->size()) - this->grow(this->size()+NumInputs); + if (NumInputs > this->capacity() - this->size()) { + detail::GrowBuffer Buffer(this->size(), + this->grow_size(this->size() + NumInputs)); + Buffer.append(NumInputs, Elt); + Buffer.swap_out_buffer(*this); + return; + } std::uninitialized_fill_n(this->end(), NumInputs, Elt); this->set_size(this->size() + NumInputs); @@ -463,11 +635,25 @@ // re-initializing them - for all assign(...) variants. void assign(size_type NumElts, const T &Elt) { - clear(); - if (this->capacity() < NumElts) - this->grow(NumElts); - this->set_size(NumElts); - std::uninitialized_fill(this->begin(), this->end(), Elt); + if (this->capacity() < NumElts) { + detail::GrowBuffer Buffer(0, this->grow_size(NumElts)); + Buffer.append(NumElts, Elt); + this->clear(); + Buffer.swap_out_buffer(*this); + return; + } + if (NumElts == this->size()) { + std::fill(this->begin(), this->end(), Elt); + } + if (NumElts < this->size()) { + this->destroy_range(this->begin() + NumElts, this->end()); + this->set_size(NumElts); + std::fill(this->begin(), this->end(), Elt); + } else { + std::fill(this->begin(), this->end(), Elt); + std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt); + this->set_size(NumElts); + } } template ::iterator_category, std::input_iterator_tag>::value>> void assign(in_iter in_start, in_iter in_end) { - clear(); - append(in_start, in_end); + size_type NumElts = std::distance(in_start, in_end); + if (this->capacity() < NumElts) { + detail::GrowBuffer Buffer(0, this->grow_size(NumElts)); + for (; in_start != in_end; ++in_start) { + Buffer.push_back(*in_start); + } + this->clear(); + Buffer.swap_out_buffer(*this); + return; + } + if (NumElts == this->size()) { + std::copy(in_start, in_end, this->begin()); + } + if (NumElts < this->size()) { + this->destroy_range(this->begin() + NumElts, this->end()); + this->set_size(NumElts); + std::copy(in_start, in_end, this->begin()); + } else { + for (auto I = this->begin(), E = this->end(); I != E; ++I, ++in_start) { + *I = *in_start; + } + std::uninitialized_copy(in_start, in_end, this->end()); + this->set_size(NumElts); + } } - void assign(std::initializer_list IL) { - clear(); - append(IL); - } + void assign(std::initializer_list IL) { assign(IL.begin(), IL.end()); } iterator erase(const_iterator CI) { // Just cast away constness because this is a non-const member function. @@ -528,8 +733,10 @@ if (this->size() >= this->capacity()) { size_t EltNo = I-this->begin(); - this->grow(); - I = this->begin()+EltNo; + detail::GrowBuffer Buffer(EltNo, this->grow_size()); + Buffer.push_back(std::move(Elt)); + Buffer.swap_out_split_buffer(*this, EltNo); + return this->begin() + EltNo; } ::new ((void*) this->end()) T(::std::move(this->back())); @@ -558,8 +765,10 @@ if (this->size() >= this->capacity()) { size_t EltNo = I-this->begin(); - this->grow(); - I = this->begin()+EltNo; + detail::GrowBuffer Buffer(EltNo, this->grow_size()); + Buffer.push_back(Elt); + Buffer.swap_out_split_buffer(*this, EltNo); + return this->begin() + EltNo; } ::new ((void*) this->end()) T(std::move(this->back())); // Push everything else over. @@ -588,11 +797,13 @@ assert(I >= this->begin() && "Insertion iterator is out of bounds."); assert(I <= this->end() && "Inserting past the end of the vector."); - // Ensure there is enough space. - reserve(this->size() + NumToInsert); - - // Uninvalidate the iterator. - I = this->begin()+InsertElt; + if ((this->size() + NumToInsert) > this->capacity()) { + detail::GrowBuffer Buffer(InsertElt, + this->grow_size(this->size() + NumToInsert)); + Buffer.append(NumToInsert, Elt); + Buffer.swap_out_split_buffer(*this, InsertElt); + return this->begin() + InsertElt; + } // If there are more elements between the insertion point and the end of the // range than there are being inserted, we can use a simple approach to @@ -645,11 +856,15 @@ size_t NumToInsert = std::distance(From, To); - // Ensure there is enough space. - reserve(this->size() + NumToInsert); - - // Uninvalidate the iterator. - I = this->begin()+InsertElt; + if ((this->size() + NumToInsert) > this->capacity()) { + detail::GrowBuffer Buffer(InsertElt, + this->grow_size(this->size() + NumToInsert)); + for (; From != To; ++From) { + Buffer.push_back(*From); + } + Buffer.swap_out_split_buffer(*this, InsertElt); + return this->begin() + InsertElt; + } // If there are more elements between the insertion point and the end of the // range than there are being inserted, we can use a simple approach to diff --git a/llvm/unittests/ADT/SmallVectorTest.cpp b/llvm/unittests/ADT/SmallVectorTest.cpp --- a/llvm/unittests/ADT/SmallVectorTest.cpp +++ b/llvm/unittests/ADT/SmallVectorTest.cpp @@ -32,39 +32,43 @@ static int numAssignmentCalls; static int numMoveAssignmentCalls; static int numCopyAssignmentCalls; + enum ObjectState { OS_Invalid = 0, OS_Constructed, OS_MovedOut }; - bool constructed; + ObjectState State; int value; public: - Constructable() : constructed(true), value(0) { - ++numConstructorCalls; - } + Constructable() : State(OS_Constructed), value(0) { ++numConstructorCalls; } - Constructable(int val) : constructed(true), value(val) { + Constructable(int val) : State(OS_Constructed), value(val) { ++numConstructorCalls; } - Constructable(const Constructable & src) : constructed(true) { + Constructable(const Constructable &src) : State(src.State) { + EXPECT_EQ(State, OS_Constructed); value = src.value; ++numConstructorCalls; ++numCopyConstructorCalls; } - Constructable(Constructable && src) : constructed(true) { + Constructable(Constructable &&src) : State(src.State) { + EXPECT_EQ(State, OS_Constructed); value = src.value; + src.State = OS_MovedOut; ++numConstructorCalls; ++numMoveConstructorCalls; } ~Constructable() { - EXPECT_TRUE(constructed); + EXPECT_NE(State, OS_Invalid); ++numDestructorCalls; - constructed = false; + State = OS_Invalid; } Constructable & operator=(const Constructable & src) { - EXPECT_TRUE(constructed); + EXPECT_NE(State, OS_Invalid); + EXPECT_EQ(src.State, OS_Constructed); + State = src.State; value = src.value; ++numAssignmentCalls; ++numCopyAssignmentCalls; @@ -72,14 +76,18 @@ } Constructable & operator=(Constructable && src) { - EXPECT_TRUE(constructed); + EXPECT_NE(State, OS_Invalid); + EXPECT_EQ(src.State, OS_Constructed); + State = src.State; value = src.value; + src.State = OS_MovedOut; ++numAssignmentCalls; ++numMoveAssignmentCalls; return *this; } int getValue() const { + EXPECT_EQ(State, OS_Constructed); return abs(value); } @@ -564,21 +572,28 @@ this->makeSequence(this->theVector, 1, 4); Constructable::reset(); + bool RequiresGrowth = this->theVector.capacity() < 6; auto I = this->theVector.insert(this->theVector.begin() + 1, 2, Constructable(16)); - // Move construct the top element into newly allocated space, and optionally - // reallocate the whole buffer, move constructing into it. - // FIXME: This is inefficient, we shouldn't move things into newly allocated - // space, then move them up/around, there should only be 2 or 4 move - // constructions here. - EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || - Constructable::getNumMoveConstructorCalls() == 6); - // Move assign the next two to shift them up and make a gap. - EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); - // Copy construct the two new elements from the parameter. - EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); - // All without any copy construction. - EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); + + if (RequiresGrowth) { + // Moving [1] and [2,3,4] into the new storage. + EXPECT_EQ(4, Constructable::getNumMoveConstructorCalls()); + // Copy construct the new elements directly into the new storage. + EXPECT_EQ(2, Constructable::getNumCopyConstructorCalls()); + // Nothing is move or copy assigned in the growth case. + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + } else { + // Shifting [3,4] down 2 blocks into uninitialized storage. + EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls()); + // Shifting [2] into where [4] lived. + EXPECT_EQ(1, Constructable::getNumMoveAssignmentCalls()); + // Copy assign the two new elements inside the buffer. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyConstructorCalls()); + } + EXPECT_EQ(this->theVector.begin() + 1, I); this->assertValuesInOrder(this->theVector, 6u, 1, 16, 16, 2, 3, 4); } @@ -635,18 +650,28 @@ this->makeSequence(this->theVector, 1, 3); Constructable::reset(); + bool RequiresGrowth = this->theVector.capacity() < 6; auto I = this->theVector.insert(this->theVector.begin() + 1, Arr, Arr + 3); - // Move construct the top 3 elements into newly allocated space. - // Possibly move the whole sequence into new space first. - // FIXME: This is inefficient, we shouldn't move things into newly allocated - // space, then move them up/around, there should only be 2 or 3 move - // constructions here. - EXPECT_TRUE(Constructable::getNumMoveConstructorCalls() == 2 || - Constructable::getNumMoveConstructorCalls() == 5); - // Copy assign the lower 2 new elements into existing space. - EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); - // Copy construct the third element into newly allocated space. - EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); + + if (RequiresGrowth) { + // Moving [1] and [2,3] into the new storage. + EXPECT_EQ(3, Constructable::getNumMoveConstructorCalls()); + // Copy construct the 3 items from Arr into the new storage. + EXPECT_EQ(3, Constructable::getNumCopyConstructorCalls()); + // Nothing is move or copy assigned in the growth case. + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + EXPECT_EQ(0, Constructable::getNumCopyAssignmentCalls()); + } else { + // Shifting [2,3] down 3 blocks into uninitialized storage. + EXPECT_EQ(2, Constructable::getNumMoveConstructorCalls()); + // Copy assign the lower 2 new elements into existing space. + EXPECT_EQ(2, Constructable::getNumCopyAssignmentCalls()); + // Copy construct the third element into uninitialized storage. + EXPECT_EQ(1, Constructable::getNumCopyConstructorCalls()); + // Nothing needs to be move assigned here as the only items that need + // shifting, are shifter into uninitialized storage. + EXPECT_EQ(0, Constructable::getNumMoveAssignmentCalls()); + } EXPECT_EQ(this->theVector.begin() + 1, I); this->assertValuesInOrder(this->theVector, 6u, 1, 77, 77, 77, 2, 3); }