================
@@ -428,50 +653,60 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp,
_Allocator>::shrink_to_fi
}
}
-template <class _Tp, class _Allocator>
+template <class _Tp, class _Allocator, template <class, class, class> class
_Layout>
template <class... _Args>
-_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp,
_Allocator>::emplace_front(_Args&&... __args) {
- if (__begin_ == __first_) {
- if (__end_ < __cap_) {
- difference_type __d = __cap_ - __end_;
+_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator,
_Layout>::emplace_front(_Args&&... __args) {
+ if (__front_spare() == 0) {
+ pointer __end = end();
+ if (__back_spare() > 0) {
+ // The elements are pressed up against the front of the buffer: we need
to move them back a
+ // little bit to make `emplace_front` have amortised O(1) complexity.
+ difference_type __d = __back_spare();
__d = (__d + 1) / 2;
- __begin_ = std::move_backward(__begin_, __end_, __end_ + __d);
- __end_ += __d;
+ __set_begin(std::move_backward(begin(), __end, __end + __d));
+
+ // `begin()` was moved further into the buffer, so we need to update the
pointer-based
+ // layout's end with it. We don't need to do anything for the size-based
layout here, because
+ // the number of elements hasn't changed yet.
+ __set_size_if_pointer_based(__d);
} else {
- size_type __c = std::max<size_type>(2 * static_cast<size_type>(__cap_ -
__first_), 1);
- __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4,
__alloc_);
- __t.__construct_at_end(move_iterator<pointer>(__begin_),
move_iterator<pointer>(__end_));
- std::swap(__first_, __t.__first_);
- std::swap(__begin_, __t.__begin_);
- std::swap(__end_, __t.__end_);
- std::swap(__cap_, __t.__cap_);
+ size_type __c = std::max<size_type>(2 * capacity(), 1);
+ __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4,
this->__alloc_);
+ __t.__construct_at_end(move_iterator<pointer>(begin()),
move_iterator<pointer>(__end));
+ __swap_without_allocator(__t);
}
}
- __alloc_traits::construct(__alloc_, std::__to_address(__begin_ - 1),
std::forward<_Args>(__args)...);
- --__begin_;
+
+ __alloc_traits::construct(this->__alloc_, std::__to_address(begin() - 1),
std::forward<_Args>(__args)...);
+ __set_begin(begin() - 1);
+
+ // Now that we've added an element to the front of the buffer, we need to
update the size-based
+ // layout's size. We don't need to do anything for the pointer-based layout
here, because the end
+ // pointer was never updated.
+ __set_end_if_size_based();
----------------
ldionne wrote:
Similarly to the above, here I would set the size unconditionally:
`__set_sentinel(size() + 1)`. Actually, writing this makes me realize that it's
awkward to call `__set_sentinel(size() + 1)` at this point since we have not
changed the end of the `split_buffer`, and we're really using that call as a
way to set the size.
I surveyed the various places where you use `__set_begin`, and they are always
followed by a call to `__set_sentinel`, except in `__destruct_at_begin` where
it's not immediately obvious why the code is correct (the code is correct
because `__set_begin` also adjusts the size in the size-based layout).
Instead, if we also forced setting the `end` when we set the `begin`, I think
we'd simplify the code without really impacting performance. In most places
where you call `__set_begin(...)` followed by `__set_sentinel(...)`, you'd now
call `__set_begin_sentinel(...)` instead (pick a name). That would get rid of
an often duplicated setting of the size from within the size-based layout's
`__set_sentinel` method, too. I think you'd need to keep `__set_sentinel` where
you *only* set the sentinel, because that one seems to be used quite a bit on
its own.
Inside `__destruct_at_begin`, you'd also just call `__set_begin_sentinel` and
that would result in no additional work in the size-based layout, and an extra
setting of the end in the pointer-based layout. I'd be curious whether that
redundant store of a pointer that hasn't changed can be optimized out by the
compiler, and if not whether it really has an impact on the overall
performance. I suspect it doesn't, and if it does, then I suspect that
rewriting the code to avoid escaping the `*this` pointer would solve this issue
in addition to other (unknown as of yet) performance issues, like it's been
conjectured in `std::string`.
https://github.com/llvm/llvm-project/pull/139632
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
