[libcxx] adds size-based __split_buffer representation to unstable ABI
#139632
+688
−286
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
**tl;dr** We can significantly improve the runtime performance of `std::vector` by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the [RFC] for more information. `vector` depends on `__split_buffer` for inserting elements. Changing `__split_buffer` to match `vector`'s representation simplifies the model, as it eliminates the need to convert between two different representations of a contiguous buffer in the same configuration of libc++. [RFC]: TODO
|
@llvm/pr-subscribers-lldb @llvm/pr-subscribers-libcxx Author: Christopher Di Bella (cjdb) Changestl;dr We can significantly improve the runtime performance of
Patch is 41.17 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/139632.diff 3 Files Affected:
diff --git a/libcxx/include/__split_buffer b/libcxx/include/__split_buffer
index 21e58f4abc6b3..9710dfec774f7 100644
--- a/libcxx/include/__split_buffer
+++ b/libcxx/include/__split_buffer
@@ -13,10 +13,12 @@
#include <__algorithm/max.h>
#include <__algorithm/move.h>
#include <__algorithm/move_backward.h>
+#include <__assert>
#include <__config>
#include <__iterator/distance.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/move_iterator.h>
+#include <__memory/addressof.h>
#include <__memory/allocate_at_least.h>
#include <__memory/allocator.h>
#include <__memory/allocator_traits.h>
@@ -78,23 +80,260 @@ public:
__split_buffer,
void>;
- pointer __first_;
- pointer __begin_;
- pointer __end_;
- _LIBCPP_COMPRESSED_PAIR(pointer, __cap_, allocator_type, __alloc_);
+ struct __data {
+ pointer __first_ = nullptr;
+ pointer __begin_ = nullptr;
+#ifndef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ pointer __end_ = nullptr;
+ _LIBCPP_COMPRESSED_PAIR(pointer, __cap_ = nullptr, allocator_type, __alloc_);
+#else
+ size_type __size_ = 0;
+ _LIBCPP_COMPRESSED_PAIR(size_type, __cap_ = 0, allocator_type, __alloc_);
+#endif
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __data() = default;
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __data(const allocator_type& __alloc)
+ : __alloc_(__alloc)
+ {}
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer first() noexcept {
+ return __first_;
+ }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer first() const noexcept {
+ return __first_;
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer begin() noexcept {
+ return __begin_;
+ }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer begin() const noexcept {
+ return __begin_;
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __begin_ + __size_;
+#else
+ return __end_;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __begin_ + __size_;
+#else
+ return __end_;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __size_;
+#else
+ return static_cast<size_type>(__end_ - __begin_);
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __size_ == 0;
+#else
+ return __begin_ == __end_;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __cap_;
+#else
+ return static_cast<size_type>(__cap_ - __first_);
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __capacity_as_pointer() noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __first_ + __cap_;
+#else
+ return __cap_;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __capacity_as_pointer() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __first_ + __cap_;
+#else
+ return __cap_;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __update_begin(pointer __new_begin) noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ __size_ -= __new_begin - __begin_;
+#else
+ // TODO: explain why there isn't a pointer-based analogue
+#endif
+
+ __begin_ = __new_begin;
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const noexcept {
+ return static_cast<size_type>(__begin_ - __first_);
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __update_sentinel(pointer __new_end) noexcept {
+ _LIBCPP_ASSERT(__first_ <= __new_end, "__new_end cannot precede __first_");
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ __size_ += __new_end - end();
+#else
+ __end_ = __new_end;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __update_sentinel(size_type __new_size) noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ __size_ = __new_size;
+#else
+ __end_ = __begin_ + __new_size;
+#endif
+ }
- __split_buffer(const __split_buffer&) = delete;
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __update_capacity(size_type __new_capacity) noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ __cap_ = __new_capacity;
+#else
+ __cap_ = __first_ + __new_capacity;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ // `__cap_ - __end_` tells us the total number of spares when in size-mode. We need to remove
+ // the __front_spare from the count.
+ return __cap_ - __size_ - __front_spare();
+#else
+ return static_cast<size_type>(__cap_ - __end_);
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __begin_[__size_ - 1];
+#else
+ return *(__end_ - 1);
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __begin_[__size_ - 1];
+#else
+ return *(__end_ - 1);
+#endif
+ }
+
+ template<class _Data2>
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(_Data2& __other) noexcept {
+ std::swap(__first_, __other.__first_);
+ std::swap(__begin_, __other.__begin_);
+ std::swap(__cap_, __other.__cap_);
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ std::swap(__size_, __other.__size_);
+#else
+ std::swap(__end_, __other.__end_);
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__data& __other) noexcept {
+ __swap_without_allocator(__other);
+ std::__swap_allocator(__alloc_, __other.__alloc_);
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const noexcept {
+ if (__first_ == nullptr) {
+ if (__begin_ != nullptr) {
+ return false;
+ }
+
+ if (!empty()) {
+ return false;
+ }
+
+ if (capacity() != 0) {
+ return false;
+ }
+
+ return true;
+ }
+
+ if (__begin_ < __first_) {
+ return false;
+ }
+
+ if (capacity() < size()) {
+ return false;
+ }
+
+ if (end() < __begin_) {
+ return false;
+ }
+
+ return true;
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __is_full() const noexcept {
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ return __size_ == __cap_;
+#else
+ return __end_ == __cap_;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __reset() noexcept {
+ __first_ = nullptr;
+ __begin_ = nullptr;
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ __size_ = 0;
+ __cap_ = 0;
+#else
+ __end_ = nullptr;
+ __cap_ = nullptr;
+#endif
+ }
+
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_without_alloc(__data const& __other)
+ noexcept(is_nothrow_copy_assignable<pointer>::value)
+ {
+ __first_ = __other.__first_;
+ __begin_ = __other.__begin_;
+ __cap_ = __other.__cap_;
+#ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR
+ __size_ = __other.__size_;
+#else
+ __end_ = __other.__end_;
+#endif
+ }
+ };
+
+ __data __data_;
+
+ __split_buffer(const __split_buffer&) = delete;
__split_buffer& operator=(const __split_buffer&) = delete;
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer()
- _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
- : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __cap_(nullptr) {}
+ _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
+ : __data_{}
+ {}
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(__alloc_rr& __a)
- : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __cap_(nullptr), __alloc_(__a) {}
+ _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
+ : __data_(__a)
+ {}
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(const __alloc_rr& __a)
- : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __cap_(nullptr), __alloc_(__a) {}
+ _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
+ : __data_(__a)
+ {}
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a);
@@ -111,36 +350,22 @@ public:
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~__split_buffer();
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __begin_; }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __begin_; }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __data_.begin(); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __data_.begin(); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __data_.end(); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __data_.end(); }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __end_; }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __end_; }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(__data_.__begin_); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const { return __data_.size(); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __data_.empty(); }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(__begin_); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const { return __data_.capacity(); }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const {
- return static_cast<size_type>(__end_ - __begin_);
- }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() { return *__data_.__begin_; }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *__data_.__begin_; }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __end_ == __begin_; }
-
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const {
- return static_cast<size_type>(__cap_ - __first_);
- }
-
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const {
- return static_cast<size_type>(__begin_ - __first_);
- }
-
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const {
- return static_cast<size_type>(__cap_ - __end_);
- }
-
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() { return *__begin_; }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *__begin_; }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() { return *(__end_ - 1); }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return *(__end_ - 1); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() { return __data_.back(); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return __data_.back(); }
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;
@@ -149,8 +374,8 @@ public:
template <class... _Args>
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args);
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(__begin_ + 1); }
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(__end_ - 1); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(__data_.begin() + 1); }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(__data_.end() - 1); }
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);
@@ -185,66 +410,52 @@ public:
_NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>);
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
-
private:
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer& __c, true_type)
_NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
- __alloc_ = std::move(__c.__alloc_);
+ __data_.__alloc_ = std::move(__c.__data_.__alloc_);
}
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT {}
struct _ConstructTransaction {
_LIBCPP_CONSTEXPR_SINCE_CXX20
- _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(pointer* __p, size_type __n) _NOEXCEPT
- : __pos_(*__p),
- __end_(*__p + __n),
- __dest_(__p) {}
+ _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(__split_buffer* __parent, pointer __p, size_type __n) noexcept
+ : __pos_(__p),
+ __end_(__p + __n),
+ __parent_(__parent) {}
- _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { *__dest_ = __pos_; }
+ _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() {
+ __parent_->__data_.__update_sentinel(__pos_);
+ }
pointer __pos_;
const pointer __end_;
private:
- pointer* __dest_;
+ __split_buffer* __parent_;
};
};
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 bool __split_buffer<_Tp, _Allocator>::__invariants() const {
- if (__first_ == nullptr) {
- if (__begin_ != nullptr)
- return false;
- if (__end_ != nullptr)
- return false;
- if (__cap_ != nullptr)
- return false;
- } else {
- if (__begin_ < __first_)
- return false;
- if (__end_ < __begin_)
- return false;
- if (__cap_ < __end_)
- return false;
- }
- return true;
+ return __data_.__invariants();
}
-// Default constructs __n objects starting at __end_
+// Default constructs __n objects starting at `__begin_ + size()`
// throws if construction throws
// Precondition: __n > 0
// Precondition: size() + __n <= capacity()
// Postcondition: size() == size() + __n
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) {
- _ConstructTransaction __tx(std::addressof(this->__end_), __n);
+ _ConstructTransaction __tx(this, __data_.end(), __n);
for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
- __alloc_traits::construct(__alloc_, std::__to_address(__tx.__pos_));
+ __alloc_traits::construct(__data_.__alloc_, std::__to_address(__tx.__pos_));
}
}
-// Copy constructs __n objects starting at __end_ from __x
+// Copy constructs __n objects starting at `__begin_ + size()` from __x
// throws if construction throws
// Precondition: __n > 0
// Precondition: size() + __n <= capacity()
@@ -253,30 +464,35 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::__construct_
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) {
- _ConstructTransaction __tx(std::addressof(this->__end_), __n);
+ _ConstructTransaction __tx(this, __data_.end(), __n);
for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) {
- __alloc_traits::construct(__alloc_, std::__to_address(__tx.__pos_), __x);
+ __alloc_traits::construct(__data_.__alloc_, std::__to_address(__tx.__pos_), __x);
}
}
-template <class _Tp, class _Allocator>
-template <class _Iterator, class _Sentinel>
+template<class _Tp, class _Allocator>
+template<class _Iterator, class _Sentinel>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
__split_buffer<_Tp, _Allocator>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) {
- __alloc_rr& __a = __alloc_;
+ __alloc_rr& __a = __data_.__alloc_;
for (; __first != __last; ++__first) {
- if (__end_ == __cap_) {
- size_type __old_cap = __cap_ - __first_;
+ if (__data_.__back_spare() == 0) {
+ size_type __old_cap = __data_.capacity();
size_type __new_cap = std::max<size_type>(2 * __old_cap, 8);
__split_buffer __buf(__new_cap, 0, __a);
- for (pointer __p = __begin_; __p != __end_; ++__p, (void)++__buf.__end_)
- __alloc_traits::construct(__buf.__alloc_, std::__to_address(__buf.__end_), std::move(*__p));
+ pointer __buf_end = __buf.__data_.end();
+ pointer __end = __data_.end();
+ for (pointer __p = __data_.__begin_; __p != __end; ++__p, (void)++__buf_end)
+ __alloc_traits::construct(__buf.__data_.__alloc_, std::__to_address(__buf_end), std::move(*__p));
+ __buf.__data_.__update_sentinel(__buf_end);
swap(__buf);
}
- __alloc_traits::construct(__a, std::__to_address(this->__end_), *__first);
- ++this->__end_;
+
+ __alloc_traits::construct(__a, std::__to_address(__data_.end()), *__first);
+ __data_.__update_sentinel(size() + 1);
}
}
+
template <class _Tp, class _Allocator>
template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
@@ -288,92 +504,82 @@ template <class _Tp, class _Allocator>
template <class _ForwardIterator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
__split_buffer<_Tp, _Allocator>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) {
- _ConstructTransaction __tx(std::addressof(this->__end_), __n);
+ _ConstructTransaction __tx(this, __data_.end(), __n);
for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__first) {
- __alloc_traits::construct(__alloc_, std::__to_address(__tx.__pos_), *__first);
+ __alloc_traits::construct(__data_.__alloc_, std::__to_address(__tx.__pos_), *__first);
}
}
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) {
- while (__begin_ != __new_begin)
- __alloc_traits::destroy(__alloc_, std::__to_address(__begin_++));
+ pointer __begin = __data_.__begin_;
+ while (__begin != __new_begin)
+ __alloc_traits::destroy(__data_.__alloc_, std::__to_address(__begin++));
+ __data_.__update_begin(__begin);
}
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) {
- __begin_ = __new_begin;
+ __data_.__update_begin(__new_begin);
}
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT {
- while (__new_last != __end_)
- __alloc_traits::destroy(__alloc_, std::__to_address(--__end_));
-}
-
-template <class _Tp, class _Allocator>
-_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
-__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT {
- __end_ = __new_last;
+ pointer __end = __data_.end();
+ while (__new_last != __end)
+ __alloc_traits::destroy(__data_.__alloc_, std::__to_address(--__end));
+ __data_.__update_sentinel(__end);
}
template <class _Tp, class _Allocator>
_LIBCPP_CONSTEXPR_SINCE_CXX20
__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr...
[truncated]
|
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
6 tasks
philnik777
reviewed
May 25, 2025
libcxx/include/__split_buffer
Outdated
| _LIBCPP_COMPRESSED_PAIR(pointer, __cap_, allocator_type, __alloc_); | ||
| struct __data { | ||
| pointer __first_ = nullptr; | ||
| pointer __begin_ = nullptr; |
There was a problem hiding this comment.
Should __begin_ be represented as an offset as well?
There was a problem hiding this comment.
I don't think so, or at least, not while vector uses it. vector uses __begin_ for its operations, and only refers to __first in two places (both swaps). It would be an interesting thing to explore as a potential deque optimisation, if we were to drop the vector dependency.
There was a problem hiding this comment.
Why is that a problem? We can just introduce a __begin() helper. This layout change is also (arguably mostly) affecting deque, so we might as well go all the way.
There was a problem hiding this comment.
A very quick index of our code shows that vector has more than 1.3M uses, whereas deque has less than 20k. I haven't done any benchmarks for this, but I don't expect any improvements to be above the noise for deque. My concern is that there might be a small (but noticeable) pessimisation for vector, simply due to its overwhelming usage.
Perhaps we could investigate the impact of __begin() after the size-based vector PR lands?
libcxx/include/__split_buffer
Outdated
Comment on lines
235
to
245
| template<class _Data2> | ||
| _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(_Data2& __other) _NOEXCEPT { | ||
| std::swap(__first_, __other.__first_); | ||
| std::swap(__begin_, __other.__begin_); | ||
| std::swap(__cap_, __other.__cap_); | ||
| #ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR | ||
| std::swap(__size_, __other.__size_); | ||
| #else | ||
| std::swap(__end_, __other.__end_); | ||
| #endif | ||
| } |
There was a problem hiding this comment.
This seems like a quite unfortunate function. Doesn't this result in an invalid state after the function?
There was a problem hiding this comment.
We swap without the allocator in quite a few places. I'm happy to replace it with a regular swap, but this is faithful to those call sites.
There was a problem hiding this comment.
I think I'd like that a lot more if it's feasible. Maybe as a separate patch to land before this one?
Edit: Actually, are these possibly the places where we have a reference as an allocator? If that's the case, maybe a function like __swap_buffer would be good that static_asserts that we've got a reference. (And possibly a _LIBCPP_ASSERT_INTERNAL(__alloc_ == destination_alloc)?)
There was a problem hiding this comment.
Yes, these are all called when the allocator is a reference, except for swap immediately below. My only aversion to adding the static assert is that it means we need to duplicate this code in swap, which isn't the worst thing, but it's a bit strange to repeat it immediately after this function's definition.
philnik777
reviewed
May 27, 2025
libcxx/include/__split_buffer
Outdated
| _LIBCPP_COMPRESSED_PAIR(pointer, __cap_, allocator_type, __alloc_); | ||
| struct __data { | ||
| pointer __first_ = nullptr; | ||
| pointer __begin_ = nullptr; |
There was a problem hiding this comment.
Why is that a problem? We can just introduce a __begin() helper. This layout change is also (arguably mostly) affecting deque, so we might as well go all the way.
libcxx/include/__split_buffer
Outdated
Comment on lines
235
to
245
| template<class _Data2> | ||
| _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(_Data2& __other) _NOEXCEPT { | ||
| std::swap(__first_, __other.__first_); | ||
| std::swap(__begin_, __other.__begin_); | ||
| std::swap(__cap_, __other.__cap_); | ||
| #ifdef _LIBCPP_ABI_SIZE_BASED_VECTOR | ||
| std::swap(__size_, __other.__size_); | ||
| #else | ||
| std::swap(__end_, __other.__end_); | ||
| #endif | ||
| } |
There was a problem hiding this comment.
I think I'd like that a lot more if it's feasible. Maybe as a separate patch to land before this one?
Edit: Actually, are these possibly the places where we have a reference as an allocator? If that's the case, maybe a function like __swap_buffer would be good that static_asserts that we've got a reference. (And possibly a _LIBCPP_ASSERT_INTERNAL(__alloc_ == destination_alloc)?)
libcxx/include/__split_buffer
Outdated
Comment on lines
108
to
122
| _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() _NOEXCEPT { | ||
| #ifdef _LIBCPP_ABI_SIZE_BASED_CONTAINERS | ||
| return __begin_ + __size_; | ||
| #else | ||
| return __end_; | ||
| #endif | ||
| } | ||
|
|
||
| _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const _NOEXCEPT { | ||
| #ifdef _LIBCPP_ABI_SIZE_BASED_CONTAINERS | ||
| return __begin_ + __size_; | ||
| #else | ||
| return __end_; | ||
| #endif | ||
| } |
There was a problem hiding this comment.
Can we remove these and instead implement __split_buffers end() as begin() + size()?
There was a problem hiding this comment.
The current code preserves what's currently in the main branch. Changing end() and empty() to use size() in the stable ABI would force pointer subtraction, which results in additional codegen.
There was a problem hiding this comment.
Could you provide an example where that makes a difference?
There was a problem hiding this comment.
Here's what calling end() when optimisations are disabled looks like with both implementations, across a handful of popular targets (or targets with increasing popularity). It looks like a fairly noticeable increase in code size, which risks pessimising debug performance. It's impossible to know if this is indeed a performance regression without benchmarks, and our load test infrastructure isn't set up to evaluate debug performance, which is why I wanted to keep the code consistent with what's currently there.
There isn't a need to debate the trade-off any further though. IIUC your goal here was to reduce the #ifdef granularity, which the current implementation does in a different way.
libcxx/include/__split_buffer
Outdated
Comment on lines
132
to
138
| _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { | ||
| #ifdef _LIBCPP_ABI_SIZE_BASED_CONTAINERS | ||
| return __size_ == 0; | ||
| #else | ||
| return __begin_ == __end_; | ||
| #endif | ||
| } |
There was a problem hiding this comment.
Same idea here: implement __split_buffers empty() as size() == 0?
|
✅ With the latest revision this PR passed the Python code formatter. |
|
Ping. I would appreciate it if this PR could be merged in time for my presentation at Asia LLVM, which is at the start of next week. |
ldionne
requested changes
Jun 26, 2025
libcxx/include/__split_buffer
Outdated
| @@ -78,23 +80,232 @@ public: | |||
| __split_buffer, | |||
There was a problem hiding this comment.
The documentation of the __split_buffer class above will have to be updated: it references members that don't exist anymore after this patch.
|
I've been asked to look at the LLDB/pretty printer pieces of this PR. I can't comment on the libc++ code, but I've looked at the LLDB/pretty printer changes, and I approve those changes (LGTM), assuming the libc++ changes get approved. |
vogelsgesang
reviewed
Jul 7, 2025
Michael137
reviewed
Jul 7, 2025
Michael137
reviewed
Jul 7, 2025
ldionne
reviewed
Jul 9, 2025
ldionne
reviewed
Aug 18, 2025
There was a problem hiding this comment.
Thanks for addressing the comments. I think this makes the code easier to follow in several places, modulo a few remaining comments.
Also, I see the LLDB data formatters failing and std/containers/sequences/deque/deque.cons/move_alloc.pass.cpp also failing in the CI.
libcxx/include/__split_buffer
Outdated
| using iterator = pointer; | ||
| using const_iterator = const_pointer; | ||
|
|
||
| public: // TODO: make private after vector becomes size-based |
There was a problem hiding this comment.
Can you explain what will making vector size-based change with respect to these fields being private vs public?
There was a problem hiding this comment.
The primary reason for these to be public is because vector::__swap_out_circular_buffer needs to swap its data members with __split_buffer's. I think I can get the next patch to end up refactoring this so that the equivalent __vector_*_layout classes can swap with __split_buffer_*_layout without breaking encapsulation.
There was a problem hiding this comment.
Turns out that I don't need to wait for vector's layout classes: everything can be done in vector directly. The outcome does add some annoying complexity though; PTAL and let me know if you'd rather 40ba28d be rolled back.
libcxx/include/__split_buffer
Outdated
Comment on lines
668
to
671
| // `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); |
There was a problem hiding this comment.
The fact that we special-case on the layout here is a smell. The split buffer's layout should be generic and __split_buffer should work regardless of the layout passed to it (even if we had e.g. a 3rd layout that is somehow different from the existing two).
I believe we should always call __set_sentinel(__end + __d). In the size-based layout, this will redundantly set __size_, but at least it will always be correct (if we e.g. had a different layout), and it will remove the need for the arguably ad-hoc __set_size_if_pointer_based function. I suspect that the redundant store will be entirely in the noise compared to all the work we're doing in emplace_front.
There was a problem hiding this comment.
Done. I'm still trying to understand why this change is a valid alternative, though. (I'm not saying "why is this better", I'm saying "I don't understand how this doesn't fail in the size-based case". Probably just a mindset shift, or something.)
The body accidentally became synonymous with a default constructor.
cjdb
added a commit
to cjdb/llvm-project
that referenced
this pull request
Aug 25, 2025
**tl;dr** We can significantly improve the runtime performance of `std::vector` by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the [RFC] for more information. This commit changes `std::vector`'s representation in a similar manner to `__split_buffer` in llvm#139632. We introduce a layout type that tracks implementation details that differ between the pointer-based vector and size-based vector representations. `vector` does not parameterise its layout type, unlike `__split_buffer`. `__split_buffer` is used by both `vector` and `deque`, and being able to take an ABI break on `vector` doesn't automatically mean that users can also tolerate a break on `deque`. The most convenient way to work around this problem is to parameterise the layout type. Users of `std::vector` should not depend on its layout, and libc++ has no internal reason to toggle it, so we keep the representation concrete. To use this feature, you'll need to configure libc++ so that it's built with `-DLIBCXX_UNSTABLE_ABI=Yes`. [RFC]: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306
cjdb
added a commit
to cjdb/llvm-project
that referenced
this pull request
Aug 26, 2025
**tl;dr** We can significantly improve the runtime performance of `std::vector` by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the [RFC] for more information. This commit changes `std::vector`'s representation in a similar manner to `__split_buffer` in llvm#139632. We introduce a layout type that tracks implementation details that differ between the pointer-based vector and size-based vector representations. `vector` does not parameterise its layout type, unlike `__split_buffer`. `__split_buffer` is used by both `vector` and `deque`, and being able to take an ABI break on `vector` doesn't automatically mean that users can also tolerate a break on `deque`. The most convenient way to work around this problem is to parameterise the layout type. Users of `std::vector` should not depend on its layout, and libc++ has no internal reason to toggle it, so we keep the representation concrete. To use this feature, you'll need to configure libc++ so that it's built with `-DLIBCXX_UNSTABLE_ABI=Yes`. [RFC]: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306
cjdb
added a commit
to cjdb/llvm-project
that referenced
this pull request
Aug 26, 2025
**tl;dr** We can significantly improve the runtime performance of `std::vector` by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the [RFC] for more information. This commit changes `std::vector`'s representation in a similar manner to `__split_buffer` in llvm#139632. We introduce a layout type that tracks implementation details that differ between the pointer-based vector and size-based vector representations. `vector` does not parameterise its layout type, unlike `__split_buffer`. `__split_buffer` is used by both `vector` and `deque`, and being able to take an ABI break on `vector` doesn't automatically mean that users can also tolerate a break on `deque`. The most convenient way to work around this problem is to parameterise the layout type. Users of `std::vector` should not depend on its layout, and libc++ has no internal reason to toggle it, so we keep the representation concrete. To use this feature, you'll need to configure libc++ so that it's built with `-DLIBCXX_UNSTABLE_ABI=Yes`. [RFC]: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306
cjdb
added a commit
to cjdb/llvm-project
that referenced
this pull request
Aug 26, 2025
**tl;dr** We can significantly improve the runtime performance of `std::vector` by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the [RFC] for more information. This commit changes `std::vector`'s representation in a similar manner to `__split_buffer` in llvm#139632. We introduce a layout type that tracks implementation details that differ between the pointer-based vector and size-based vector representations. `vector` does not parameterise its layout type, unlike `__split_buffer`. `__split_buffer` is used by both `vector` and `deque`, and being able to take an ABI break on `vector` doesn't automatically mean that users can also tolerate a break on `deque`. The most convenient way to work around this problem is to parameterise the layout type. Users of `std::vector` should not depend on its layout, and libc++ has no internal reason to toggle it, so we keep the representation concrete. To use this feature, you'll need to configure libc++ so that it's built with `-DLIBCXX_UNSTABLE_ABI=Yes`. [RFC]: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306
|
Ping |
Yup, I'm reviewing this at the moment. I'll publish my comments when I'm done. |
ldionne
reviewed
Aug 27, 2025
| } | ||
|
|
||
| template <class _Data2> | ||
| _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator(_Data2& __other) _NOEXCEPT { |
There was a problem hiding this comment.
Why is this a template? I don't think we need the ability to swap between __split_buffers with different template arguments?
There was a problem hiding this comment.
We call this a fair number of times with a different allocator. I originally had the allocator type parameterised out, but that caused problems IIRC.
libcxx/include/__vector/vector.h
Outdated
|
|
||
| // TODO: replace with __set_valid_range and __set_capacity when vector supports it. | ||
| __begin_ = __v_begin; | ||
| __end_ = __v_sentinel; |
There was a problem hiding this comment.
This doesn't work in the case of a size-based split_buffer, right? Since the sentinel of the split buffer is an integer and the vector's __end_ is a pointer.
There was a problem hiding this comment.
|
Oh yes, also could you please run the benchmarks for In particular, don't forget to pass |
cjdb
commented
Aug 29, 2025
There was a problem hiding this comment.
$ libcxx/utils/libcxx-compare-benchmarks build-c7df8839d8f161883e5b4c3847c3470ab8e08e64 build-size-based-vector libcxx/test/benchmarks/containers/sequence/vector.bench.cpp
Requirement already satisfied: numpy in /tmp/libcxx-compare-benchmarks-venv/lib/python3.13/site-packages (from -r /tmp/llvm-project/third-party/benchmark/tools/requirements.txt (line 1)) (2.3.2)
Requirement already satisfied: scipy in /tmp/libcxx-compare-benchmarks-venv/lib/python3.13/site-packages (from -r /tmp/llvm-project/third-party/benchmark/tools/requirements.txt (line 2)) (1.16.1)
Comparing build-c7df8839d8f161883e5b4c3847c3470ab8e08e64/libcxx/test/benchmarks/containers/sequence/Output/vector.bench.cpp.dir/benchmark-result.json to build-size-based-vector/libcxx/test/benchmarks/containers/sequence/Output/vector.bench.cpp.dir/benchmark-result.json
Benchmark Time CPU Time Old Time New CPU Old CPU New
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
std::vector<int>::ctor(size)/32 +0.0272 +0.0268 14 15 14 15
std::vector<int>::ctor(size)/1024 +0.0026 +0.0023 71 71 71 71
std::vector<int>::ctor(size)/8192 -0.0016 -0.0010 349 349 349 349
std::vector<int>::ctor(size, value_type) (cheap elements)/32 +0.0251 +0.0252 13 13 13 13
std::vector<int>::ctor(size, value_type) (cheap elements)/1024 -0.0031 -0.0036 115 115 115 115
std::vector<int>::ctor(size, value_type) (cheap elements)/8192 +0.0043 +0.0043 659 662 658 661
std::vector<int>::ctor(Iterator, Iterator) (cheap elements)/32 -0.0034 -0.0038 15 15 15 15
std::vector<int>::ctor(Iterator, Iterator) (cheap elements)/1024 -0.0036 -0.0036 75 74 74 74
std::vector<int>::ctor(Iterator, Iterator) (cheap elements)/8192 +0.0000 -0.0001 669 669 668 668
std::vector<int>::ctor(Range) (cheap elements)/32 -0.0075 -0.0071 15 15 15 15
std::vector<int>::ctor(Range) (cheap elements)/1024 +0.0010 +0.0014 75 75 74 75
std::vector<int>::ctor(Range) (cheap elements)/8192 -0.0005 -0.0007 668 667 667 667
std::vector<int>::ctor(const&) (cheap elements)/32 -0.0021 -0.0019 15 15 15 15
std::vector<int>::ctor(const&) (cheap elements)/1024 -0.0035 -0.0030 75 75 75 75
std::vector<int>::ctor(const&) (cheap elements)/8192 -0.0037 -0.0033 669 667 669 667
std::vector<int>::operator=(const&) (cheap elements)/32 -0.0036 -0.0031 5 5 5 5
std::vector<int>::operator=(const&) (cheap elements)/1024 -0.0014 -0.0015 41 41 41 41
std::vector<int>::operator=(const&) (cheap elements)/8192 -0.0018 -0.0015 652 651 652 651
std::vector<int>::assign(input-iter, input-iter) (full container) (cheap elements)/32 +0.0190 +0.0191 24 25 24 25
std::vector<int>::assign(input-iter, input-iter) (full container) (cheap elements)/1024 +0.0043 +0.0046 656 659 655 658
std::vector<int>::assign(input-iter, input-iter) (full container) (cheap elements)/8192 +0.0037 +0.0036 5303 5322 5299 5318
std::vector<int>::insert(begin) (cheap elements)/32 +0.0023 +0.0024 9 9 9 9
std::vector<int>::insert(begin) (cheap elements)/1024 -0.0017 -0.0017 48 48 48 48
std::vector<int>::insert(begin) (cheap elements)/8192 -0.0015 -0.0013 332 331 332 331
std::vector<int>::insert(middle) (cheap elements)/32 -0.0033 -0.0036 9 9 9 9
std::vector<int>::insert(middle) (cheap elements)/1024 -0.0040 -0.0045 28 28 28 28
std::vector<int>::insert(middle) (cheap elements)/8192 -0.0014 -0.0010 169 169 169 169
std::vector<int>::insert(begin, input-iter, input-iter) (no realloc) (cheap elements)/32 +0.0027 +0.0037 1255 1258 1259 1263
std::vector<int>::insert(begin, input-iter, input-iter) (no realloc) (cheap elements)/1024 +0.0029 +0.0048 3834 3845 3839 3857
std::vector<int>::insert(begin, input-iter, input-iter) (no realloc) (cheap elements)/8192 +0.0099 +0.0100 21936 22153 21958 22177
std::vector<int>::insert(begin, input-iter, input-iter) (half filled) (cheap elements)/32 -0.0015 -0.0011 1123 1122 1127 1126
std::vector<int>::insert(begin, input-iter, input-iter) (half filled) (cheap elements)/1024 +0.0086 +0.0130 2172 2191 2184 2213
std::vector<int>::insert(begin, input-iter, input-iter) (half filled) (cheap elements)/8192 +0.0210 +0.0219 9519 9719 9544 9752
std::vector<int>::insert(begin, input-iter, input-iter) (near full) (cheap elements)/32 +0.0079 +0.0079 1149 1158 1153 1162
std::vector<int>::insert(begin, input-iter, input-iter) (near full) (cheap elements)/1024 +0.1679 +0.1659 1878 2193 1899 2214
std::vector<int>::insert(begin, input-iter, input-iter) (near full) (cheap elements)/8192 +0.3200 +0.3196 6809 8988 6825 9007
std::vector<int>::push_back() (growing) (cheap elements)/32 -0.0232 -0.0245 79 77 79 77
std::vector<int>::push_back() (growing) (cheap elements)/1024 -0.0169 -0.0164 193 190 193 190
std::vector<int>::push_back() (growing) (cheap elements)/8192 -0.0158 -0.0164 4362 4293 4347 4276
std::vector<int>::push_back() (with reserve) (cheap elements)/32 -0.0082 -0.0111 34 33 34 33
std::vector<int>::push_back() (with reserve) (cheap elements)/1024 -0.0105 -0.0128 34 34 34 33
std::vector<int>::push_back() (with reserve) (cheap elements)/8192 -0.0114 -0.0147 34 33 34 33
std::vector<int>::push_back() (many elements) (cheap elements)/32 -0.0069 -0.0073 34 33 34 33
std::vector<int>::push_back() (many elements) (cheap elements)/1024 -0.0099 -0.0106 1 1 1 1
std::vector<int>::push_back() (many elements) (cheap elements)/8192 -0.0065 -0.0062 1 1 1 1
std::vector<int>::erase(begin) (cheap elements)/32 +0.0086 +0.0084 10 10 10 10
std::vector<int>::erase(begin) (cheap elements)/1024 -0.0016 -0.0016 49 49 49 49
std::vector<int>::erase(begin) (cheap elements)/8192 -0.0016 -0.0012 333 332 333 332
std::vector<int>::erase(middle) (cheap elements)/32 -0.0058 -0.0062 8 8 8 8
std::vector<int>::erase(middle) (cheap elements)/1024 -0.0533 -0.0535 31 29 31 29
std::vector<int>::erase(middle) (cheap elements)/8192 -0.0013 -0.0011 171 171 171 171
std::vector<std::string>::ctor(size)/32 -0.0285 -0.0288 30 29 30 29
std::vector<std::string>::ctor(size)/1024 +0.0197 +0.0198 599 611 599 610
std::vector<std::string>::ctor(size)/8192 +0.0272 +0.0268 4857 4989 4853 4983
std::vector<std::string>::ctor(size, value_type) (cheap elements)/32 -0.1519 -0.1515 54 46 54 46
std::vector<std::string>::ctor(size, value_type) (cheap elements)/1024 +0.0076 +0.0079 1002 1009 1001 1009
std::vector<std::string>::ctor(size, value_type) (cheap elements)/8192 -0.0086 -0.0083 8557 8483 8548 8477
std::vector<std::string>::ctor(size, value_type) (expensive elements)/32 +0.0158 +0.0157 1160 1178 1159 1177
std::vector<std::string>::ctor(size, value_type) (expensive elements)/1024 +0.0086 +0.0088 38444 38777 38404 38741
std::vector<std::string>::ctor(size, value_type) (expensive elements)/8192 +0.0015 +0.0012 511106 511883 510649 511282
std::vector<std::string>::ctor(Iterator, Iterator) (cheap elements)/32 +0.0067 +0.0063 49 49 49 49
std::vector<std::string>::ctor(Iterator, Iterator) (cheap elements)/1024 +0.0052 +0.0047 1402 1409 1401 1408
std::vector<std::string>::ctor(Iterator, Iterator) (cheap elements)/8192 +0.0317 +0.0317 11411 11773 11402 11764
std::vector<std::string>::ctor(Iterator, Iterator) (expensive elements)/32 +0.0104 +0.0099 1107 1119 1107 1118
std::vector<std::string>::ctor(Iterator, Iterator) (expensive elements)/1024 -0.0425 -0.0422 40084 38379 40053 38361
std::vector<std::string>::ctor(Iterator, Iterator) (expensive elements)/8192 -0.0005 -0.0006 325009 324853 324743 324542
std::vector<std::string>::ctor(Range) (cheap elements)/32 -0.0133 -0.0128 50 50 50 50
std::vector<std::string>::ctor(Range) (cheap elements)/1024 -0.0044 -0.0044 1413 1407 1412 1406
std::vector<std::string>::ctor(Range) (cheap elements)/8192 +0.0172 +0.0174 11468 11666 11458 11657
std::vector<std::string>::ctor(Range) (expensive elements)/32 +0.0105 +0.0104 1106 1117 1105 1116
std::vector<std::string>::ctor(Range) (expensive elements)/1024 -0.0227 -0.0227 39841 38935 39802 38899
std::vector<std::string>::ctor(Range) (expensive elements)/8192 -0.0062 -0.0064 325031 323009 324784 322720
std::vector<std::string>::ctor(const&) (cheap elements)/32 -0.0178 -0.0176 51 50 51 50
std::vector<std::string>::ctor(const&) (cheap elements)/1024 +0.0119 +0.0121 1407 1424 1405 1422
std::vector<std::string>::ctor(const&) (cheap elements)/8192 -0.1112 -0.1113 12700 11287 12692 11279
std::vector<std::string>::ctor(const&) (expensive elements)/32 +0.0069 +0.0077 1108 1116 1107 1115
std::vector<std::string>::ctor(const&) (expensive elements)/1024 -0.0088 -0.0089 39814 39464 39784 39431
std::vector<std::string>::ctor(const&) (expensive elements)/8192 -0.0033 -0.0033 323495 322411 323212 322150
std::vector<std::string>::operator=(const&) (cheap elements)/32 -0.0109 -0.0108 35 35 35 35
std::vector<std::string>::operator=(const&) (cheap elements)/1024 +0.0521 +0.0527 1011 1064 1010 1063
std::vector<std::string>::operator=(const&) (cheap elements)/8192 -0.0651 -0.0651 8866 8289 8861 8284
std::vector<std::string>::operator=(const&) (expensive elements)/32 +0.0264 +0.0264 209 215 209 215
std::vector<std::string>::operator=(const&) (expensive elements)/1024 +0.0350 +0.0338 9668 10006 9667 9994
std::vector<std::string>::operator=(const&) (expensive elements)/8192 -0.0374 -0.0375 82086 79017 82052 78973
std::vector<std::string>::assign(input-iter, input-iter) (full container) (cheap elements)/32 -0.0005 -0.0006 51 51 51 51
std::vector<std::string>::assign(input-iter, input-iter) (full container) (cheap elements)/1024 -0.0553 -0.0554 1466 1385 1465 1384
std::vector<std::string>::assign(input-iter, input-iter) (full container) (cheap elements)/8192 +0.0215 +0.0216 11451 11697 11441 11688
std::vector<std::string>::assign(input-iter, input-iter) (full container) (expensive elements)/32 +0.0065 +0.0059 241 242 241 242
std::vector<std::string>::assign(input-iter, input-iter) (full container) (expensive elements)/1024 +0.0156 +0.0155 10563 10727 10556 10719
std::vector<std::string>::assign(input-iter, input-iter) (full container) (expensive elements)/8192 -0.0161 -0.0165 87753 86339 87700 86250
std::vector<std::string>::insert(begin) (cheap elements)/32 -0.0107 -0.0106 33 32 33 32
std::vector<std::string>::insert(begin) (cheap elements)/1024 +0.0011 +0.0010 1002 1004 1002 1003
std::vector<std::string>::insert(begin) (cheap elements)/8192 -0.0038 -0.0043 8433 8401 8430 8394
std::vector<std::string>::insert(begin) (expensive elements)/32 +0.0130 +0.0128 48 49 48 49
std::vector<std::string>::insert(begin) (expensive elements)/1024 +0.0036 +0.0036 1055 1059 1054 1058
std::vector<std::string>::insert(begin) (expensive elements)/8192 -0.0017 -0.0012 8454 8439 8443 8433
std::vector<std::string>::insert(middle) (cheap elements)/32 +0.0734 +0.0734 18 19 18 19
std::vector<std::string>::insert(middle) (cheap elements)/1024 +0.0004 +0.0007 501 501 501 501
std::vector<std::string>::insert(middle) (cheap elements)/8192 +0.0040 +0.0037 4195 4212 4193 4209
std::vector<std::string>::insert(middle) (expensive elements)/32 -0.0027 -0.0023 33 33 33 33
std::vector<std::string>::insert(middle) (expensive elements)/1024 +0.0062 +0.0058 517 520 517 520
std::vector<std::string>::insert(middle) (expensive elements)/8192 +0.0067 +0.0070 4225 4253 4221 4250
std::vector<std::string>::insert(begin, input-iter, input-iter) (no realloc) (cheap elements)/32 +0.0151 +0.0124 1371 1392 1375 1392
std::vector<std::string>::insert(begin, input-iter, input-iter) (no realloc) (cheap elements)/1024 +0.0130 +0.0109 4823 4886 4837 4890
std::vector<std::string>::insert(begin, input-iter, input-iter) (no realloc) (cheap elements)/8192 +0.0118 +0.0135 29882 30233 29949 30352
std::vector<std::string>::insert(begin, input-iter, input-iter) (no realloc) (expensive elements)/32 -0.0181 -0.0180 1966 1930 1983 1948
std::vector<std::string>::insert(begin, input-iter, input-iter) (no realloc) (expensive elements)/1024 -0.0259 -0.0273 27109 26406 27280 26535
std::vector<std::string>::insert(begin, input-iter, input-iter) (no realloc) (expensive elements)/8192 -0.0088 -0.0081 1032159 1023111 1030392 1022052
std::vector<std::string>::insert(begin, input-iter, input-iter) (half filled) (cheap elements)/32 -0.0034 -0.0059 1205 1201 1214 1207
std::vector<std::string>::insert(begin, input-iter, input-iter) (half filled) (cheap elements)/1024 -0.0031 -0.0029 3534 3523 3540 3529
std::vector<std::string>::insert(begin, input-iter, input-iter) (half filled) (cheap elements)/8192 -0.0031 -0.0049 20811 20746 21001 20898
std::vector<std::string>::insert(begin, input-iter, input-iter) (half filled) (expensive elements)/32 +0.0052 +0.0065 1944 1954 1963 1976
std::vector<std::string>::insert(begin, input-iter, input-iter) (half filled) (expensive elements)/1024 +0.0181 +0.0177 24967 25419 25074 25518
std::vector<std::string>::insert(begin, input-iter, input-iter) (half filled) (expensive elements)/8192 -0.0119 -0.0117 1213522 1199109 1212344 1198135
std::vector<std::string>::insert(begin, input-iter, input-iter) (near full) (cheap elements)/32 +0.0040 +0.0031 1273 1278 1280 1284
std::vector<std::string>::insert(begin, input-iter, input-iter) (near full) (cheap elements)/1024 +0.0266 +0.0259 5950 6108 5953 6107
std::vector<std::string>::insert(begin, input-iter, input-iter) (near full) (cheap elements)/8192 -0.0106 -0.0093 41340 40902 41333 40947
std::vector<std::string>::insert(begin, input-iter, input-iter) (near full) (expensive elements)/32 -0.0033 -0.0030 2026 2019 2033 2026
std::vector<std::string>::insert(begin, input-iter, input-iter) (near full) (expensive elements)/1024 +0.0170 +0.0168 28510 28995 28528 29008
std::vector<std::string>::insert(begin, input-iter, input-iter) (near full) (expensive elements)/8192 -0.0598 -0.0599 1436815 1350887 1435078 1349181
std::vector<std::string>::push_back() (growing) (cheap elements)/32 +0.0055 +0.0058 94 94 94 94
std::vector<std::string>::push_back() (growing) (cheap elements)/1024 -0.0014 -0.0019 814 813 813 811
std::vector<std::string>::push_back() (growing) (cheap elements)/8192 +0.0280 +0.0284 35454 36446 35406 36410
std::vector<std::string>::push_back() (growing) (expensive elements)/32 +0.0155 +0.0165 160 162 156 159
std::vector<std::string>::push_back() (growing) (expensive elements)/1024 +0.0212 +0.0212 2017 2059 1994 2036
std::vector<std::string>::push_back() (growing) (expensive elements)/8192 -0.0003 -0.0008 23065 23058 22979 22960
std::vector<std::string>::push_back() (with reserve) (cheap elements)/32 +0.0002 -0.0005 34 34 34 34
std::vector<std::string>::push_back() (with reserve) (cheap elements)/1024 +0.0027 +0.0023 34 34 34 34
std::vector<std::string>::push_back() (with reserve) (cheap elements)/8192 +0.0002 -0.0021 35 35 35 35
std::vector<std::string>::push_back() (with reserve) (expensive elements)/32 +0.0035 +0.0061 57 57 57 57
std::vector<std::string>::push_back() (with reserve) (expensive elements)/1024 -0.0048 -0.0033 55 55 56 56
std::vector<std::string>::push_back() (with reserve) (expensive elements)/8192 -0.0013 -0.0004 56 56 56 56
std::vector<std::string>::push_back() (many elements) (cheap elements)/32 -0.0109 -0.0117 35 35 35 35
std::vector<std::string>::push_back() (many elements) (cheap elements)/1024 -0.0141 -0.0150 2 2 2 2
std::vector<std::string>::push_back() (many elements) (cheap elements)/8192 -0.0204 -0.0227 1 1 1 1
std::vector<std::string>::push_back() (many elements) (expensive elements)/32 +0.0015 +0.0054 57 57 57 58
std::vector<std::string>::push_back() (many elements) (expensive elements)/1024 +0.0211 +0.0221 23 23 23 23
std::vector<std::string>::push_back() (many elements) (expensive elements)/8192 +0.0084 +0.0089 46 46 46 46
std::vector<std::string>::erase(begin) (cheap elements)/32 +0.0123 +0.0118 33 33 32 33
std::vector<std::string>::erase(begin) (cheap elements)/1024 +0.0079 +0.0085 975 982 974 982
std::vector<std::string>::erase(begin) (cheap elements)/8192 +0.0065 +0.0062 8413 8467 8407 8460
std::vector<std::string>::erase(begin) (expensive elements)/32 +0.0161 +0.0164 47 48 47 48
std::vector<std::string>::erase(begin) (expensive elements)/1024 -0.0052 -0.0050 1044 1038 1043 1038
std::vector<std::string>::erase(begin) (expensive elements)/8192 -0.0033 -0.0029 8427 8400 8420 8396
std::vector<std::string>::erase(middle) (cheap elements)/32 -0.0100 -0.0099 18 17 18 17
std::vector<std::string>::erase(middle) (cheap elements)/1024 -0.0001 +0.0001 488 488 488 488
std::vector<std::string>::erase(middle) (cheap elements)/8192 -0.0005 -0.0006 4198 4196 4195 4192
std::vector<std::string>::erase(middle) (expensive elements)/32 -0.0180 -0.0174 33 33 33 33
std::vector<std::string>::erase(middle) (expensive elements)/1024 -0.0024 -0.0028 512 511 512 510
std::vector<std::string>::erase(middle) (expensive elements)/8192 +0.0048 +0.0045 4231 4251 4228 4247
OVERALL_GEOMEAN +0.0011 +0.0011 0 0 0 0
$ libcxx/utils/libcxx-compare-benchmarks build-c7df8839d8f161883e5b4c3847c3470ab8e08e64 build-size-based-vector libcxx/test/benchmarks/containers/sequence/deque.bench.cpp
Requirement already satisfied: numpy in /tmp/libcxx-compare-benchmarks-venv/lib/python3.13/site-packages (from -r /tmp/llvm-project/third-party/benchmark/tools/requirements.txt (line 1)) (2.3.2)
Requirement already satisfied: scipy in /tmp/libcxx-compare-benchmarks-venv/lib/python3.13/site-packages (from -r /tmp/llvm-project/third-party/benchmark/tools/requirements.txt (line 2)) (1.16.1)
Comparing build-c7df8839d8f161883e5b4c3847c3470ab8e08e64/libcxx/test/benchmarks/containers/sequence/Output/deque.bench.cpp.dir/benchmark-result.json to build-size-based-vector/libcxx/test/benchmarks/containers/sequence/Output/deque.bench.cpp.dir/benchmark-result.json
Benchmark Time CPU Time Old Time New CPU Old CPU New
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
std::deque<int>::ctor(size)/32 -0.0239 -0.0236 64 62 64 62
std::deque<int>::ctor(size)/1024 -0.0119 -0.0126 121 119 121 119
std::deque<int>::ctor(size)/8192 -0.0059 -0.0059 663 659 662 658
std::deque<int>::ctor(size, value_type) (cheap elements)/32 -0.0102 -0.0104 49 49 49 49
std::deque<int>::ctor(size, value_type) (cheap elements)/1024 -0.0090 -0.0089 162 161 162 161
std::deque<int>::ctor(size, value_type) (cheap elements)/8192 +0.0006 +0.0006 960 961 960 960
std::deque<int>::ctor(Iterator, Iterator) (cheap elements)/32 -0.0302 -0.0298 51 49 51 49
std::deque<int>::ctor(Iterator, Iterator) (cheap elements)/1024 -0.0064 -0.0063 181 180 181 179
std::deque<int>::ctor(Iterator, Iterator) (cheap elements)/8192 -0.0170 -0.0155 1051 1033 1048 1032
std::deque<int>::ctor(Range) (cheap elements)/32 -0.0095 -0.0095 65 65 65 65
std::deque<int>::ctor(Range) (cheap elements)/1024 +0.0006 +0.0006 180 180 180 180
std::deque<int>::ctor(Range) (cheap elements)/8192 -0.0184 -0.0176 1046 1026 1045 1026
std::deque<int>::ctor(const&) (cheap elements)/32 -0.0166 -0.0161 82 81 82 81
std::deque<int>::ctor(const&) (cheap elements)/1024 +0.0081 +0.0082 737 743 736 742
std::deque<int>::ctor(const&) (cheap elements)/8192 -0.0086 -0.0078 5483 5435 5476 5434
std::deque<int>::operator=(const&) (cheap elements)/32 +0.0078 +0.0076 12 12 12 12
std::deque<int>::operator=(const&) (cheap elements)/1024 +0.0153 +0.0157 46 47 46 47
std::deque<int>::operator=(const&) (cheap elements)/8192 +0.0035 +0.0034 684 686 683 686
std::deque<int>::assign(input-iter, input-iter) (full container) (cheap elements)/32 +0.0241 +0.0243 26 26 26 26
std::deque<int>::assign(input-iter, input-iter) (full container) (cheap elements)/1024 -0.0019 -0.0018 659 658 659 658
std::deque<int>::assign(input-iter, input-iter) (full container) (cheap elements)/8192 +0.0077 +0.0079 5335 5377 5331 5373
std::deque<int>::insert(begin) (cheap elements)/32 -0.0271 -0.0263 16 16 16 16
std::deque<int>::insert(begin) (cheap elements)/1024 -0.0215 -0.0218 16 16 16 16
std::deque<int>::insert(begin) (cheap elements)/8192 -0.0195 -0.0190 16 16 16 16
std::deque<int>::insert(middle) (cheap elements)/32 +0.0161 +0.0160 37 37 37 37
std::deque<int>::insert(middle) (cheap elements)/1024 -0.0018 -0.0016 63 63 63 63
std::deque<int>::insert(middle) (cheap elements)/8192 +0.0007 +0.0003 241 241 240 240
std::deque<int>::push_back() (many elements) (cheap elements)/32 +0.0265 +0.0258 34 35 34 35
std::deque<int>::push_back() (many elements) (cheap elements)/1024 +0.0106 +0.0100 2 2 2 2
std::deque<int>::push_back() (many elements) (cheap elements)/8192 +0.0389 +0.0386 3 3 3 3
std::deque<int>::erase(begin) (cheap elements)/32 -0.0398 -0.0399 18 17 18 17
std::deque<int>::erase(begin) (cheap elements)/1024 -0.0267 -0.0270 18 18 18 18
std::deque<int>::erase(begin) (cheap elements)/8192 +0.1073 +0.1077 18 20 18 20
std::deque<int>::erase(middle) (cheap elements)/32 -0.0064 -0.0062 21 20 21 20
std::deque<int>::erase(middle) (cheap elements)/1024 -0.0032 -0.0030 44 44 44 44
std::deque<int>::erase(middle) (cheap elements)/8192 +0.0101 +0.0103 192 194 192 194
std::deque<std::string>::ctor(size)/32 -0.0831 -0.0828 109 100 109 100
std::deque<std::string>::ctor(size)/1024 -0.1551 -0.1548 1523 1287 1522 1286
std::deque<std::string>::ctor(size)/8192 +0.0038 -0.0039 47605 47788 47117 46935
std::deque<std::string>::ctor(size, value_type) (cheap elements)/32 -0.0587 -0.0589 126 119 126 119
std::deque<std::string>::ctor(size, value_type) (cheap elements)/1024 -0.1018 -0.1020 1981 1779 1979 1777
std::deque<std::string>::ctor(size, value_type) (cheap elements)/8192 +0.0289 +0.0242 51041 52518 50509 51730
std::deque<std::string>::ctor(size, value_type) (expensive elements)/32 +0.0157 +0.0152 1155 1173 1154 1172
std::deque<std::string>::ctor(size, value_type) (expensive elements)/1024 +0.0562 +0.0509 129484 136767 128459 134992
std::deque<std::string>::ctor(size, value_type) (expensive elements)/8192 +0.1013 +0.1014 1458138 1605904 1456303 1603954
std::deque<std::string>::ctor(Iterator, Iterator) (cheap elements)/32 -0.0037 -0.0039 122 121 122 121
std::deque<std::string>::ctor(Iterator, Iterator) (cheap elements)/1024 -0.1435 -0.1435 2128 1822 2126 1821
std::deque<std::string>::ctor(Iterator, Iterator) (cheap elements)/8192 -0.1078 -0.1084 17227 15370 17216 15349
std::deque<std::string>::ctor(Iterator, Iterator) (expensive elements)/32 +0.0558 +0.0551 1127 1190 1126 1188
std::deque<std::string>::ctor(Iterator, Iterator) (expensive elements)/1024 +0.0315 +0.0312 40899 42187 40864 42141
std::deque<std::string>::ctor(Iterator, Iterator) (expensive elements)/8192 +0.0492 +0.0491 1378985 1446801 1377638 1445289
std::deque<std::string>::ctor(Range) (cheap elements)/32 -0.0225 -0.0229 128 125 128 125
std::deque<std::string>::ctor(Range) (cheap elements)/1024 -0.0900 -0.0903 2148 1955 2147 1953
std::deque<std::string>::ctor(Range) (cheap elements)/8192 -0.0729 -0.0735 17528 16251 17512 16225
std::deque<std::string>::ctor(Range) (expensive elements)/32 +0.0472 +0.0471 1172 1227 1171 1226
std::deque<std::string>::ctor(Range) (expensive elements)/1024 +0.0505 +0.0488 121795 127940 121220 127141
std::deque<std::string>::ctor(Range) (expensive elements)/8192 +0.0458 +0.0452 1378127 1441236 1377209 1439413
std::deque<std::string>::ctor(const&) (cheap elements)/32 -0.0659 -0.0660 146 137 146 137
std::deque<std::string>::ctor(const&) (cheap elements)/1024 -0.1044 -0.1046 2702 2420 2700 2418
std::deque<std::string>::ctor(const&) (cheap elements)/8192 -0.2204 -0.2205 21421 16701 21402 16682
std::deque<std::string>::ctor(const&) (expensive elements)/32 +0.0941 +0.0936 1193 1306 1192 1304
std::deque<std::string>::ctor(const&) (expensive elements)/1024 +0.0196 +0.0191 41413 42223 41372 42163
std::deque<std::string>::ctor(const&) (expensive elements)/8192 -0.0159 -0.0161 1397071 1374882 1395270 1372747
std::deque<std::string>::operator=(const&) (cheap elements)/32 +0.0044 +0.0039 45 46 45 45
std::deque<std::string>::operator=(const&) (cheap elements)/1024 +0.0082 +0.0076 1051 1060 1051 1059
std::deque<std::string>::operator=(const&) (cheap elements)/8192 +0.0062 +0.0063 8440 8492 8432 8485
std::deque<std::string>::operator=(const&) (expensive elements)/32 -0.1223 -0.1224 276 242 276 242
std::deque<std::string>::operator=(const&) (expensive elements)/1024 -0.0287 -0.0287 9847 9565 9839 9557
std::deque<std::string>::operator=(const&) (expensive elements)/8192 -0.0287 -0.0282 83281 80887 83182 80836
std::deque<std::string>::assign(input-iter, input-iter) (full container) (cheap elements)/32 +0.0216 +0.0208 57 58 57 58
std::deque<std::string>::assign(input-iter, input-iter) (full container) (cheap elements)/1024 -0.0313 -0.0315 1713 1659 1712 1658
std::deque<std::string>::assign(input-iter, input-iter) (full container) (cheap elements)/8192 +0.0056 +0.0053 13346 13420 13336 13407
std::deque<std::string>::assign(input-iter, input-iter) (full container) (expensive elements)/32 -0.0090 -0.0091 252 249 251 249
std::deque<std::string>::assign(input-iter, input-iter) (full container) (expensive elements)/1024 +0.0113 +0.0113 10780 10902 10769 10890
std::deque<std::string>::assign(input-iter, input-iter) (full container) (expensive elements)/8192 -0.0085 -0.0090 90124 89359 90077 89268
std::deque<std::string>::insert(begin) (cheap elements)/32 -0.0113 -0.0113 34 34 34 34
std::deque<std::string>::insert(begin) (cheap elements)/1024 -0.0126 -0.0129 34 34 34 34
std::deque<std::string>::insert(begin) (cheap elements)/8192 -0.0200 -0.0202 34 34 34 34
std::deque<std::string>::insert(begin) (expensive elements)/32 -0.0193 -0.0195 45 44 45 44
std::deque<std::string>::insert(begin) (expensive elements)/1024 +0.0290 +0.0282 46 47 46 47
std::deque<std::string>::insert(begin) (expensive elements)/8192 +0.0049 +0.0046 46 47 46 47
std::deque<std::string>::insert(middle) (cheap elements)/32 +0.0303 +0.0298 65 67 65 67
std::deque<std::string>::insert(middle) (cheap elements)/1024 +0.0096 +0.0094 587 593 586 592
std::deque<std::string>::insert(middle) (cheap elements)/8192 +0.0047 +0.0038 4424 4445 4422 4439
std::deque<std::string>::insert(middle) (expensive elements)/32 -0.0055 -0.0059 80 80 80 80
std::deque<std::string>::insert(middle) (expensive elements)/1024 +0.0005 -0.0000 606 607 606 606
std::deque<std::string>::insert(middle) (expensive elements)/8192 +0.0022 +0.0019 4424 4434 4422 4430
std::deque<std::string>::push_back() (many elements) (cheap elements)/32 +0.0066 +0.0055 36 37 36 37
std::deque<std::string>::push_back() (many elements) (cheap elements)/1024 -0.0170 -0.0176 5 5 5 5
std::deque<std::string>::push_back() (many elements) (cheap elements)/8192 -0.0237 -0.0240 4 4 4 4
std::deque<std::string>::push_back() (many elements) (expensive elements)/32 -0.0085 -0.0077 59 59 60 59
std::deque<std::string>::push_back() (many elements) (expensive elements)/1024 +0.0025 +0.0056 25 25 25 25
std::deque<std::string>::push_back() (many elements) (expensive elements)/8192 +0.0107 +0.0099 24 24 24 24
std::deque<std::string>::erase(begin) (cheap elements)/32 -0.0131 -0.0132 23 22 23 22
std::deque<std::string>::erase(begin) (cheap elements)/1024 +0.0160 +0.0155 23 24 23 24
std::deque<std::string>::erase(begin) (cheap elements)/8192 +0.0169 +0.0165 23 23 23 23
std::deque<std::string>::erase(begin) (expensive elements)/32 -0.0049 -0.0051 37 37 37 37
std::deque<std::string>::erase(begin) (expensive elements)/1024 -0.0210 -0.0213 40 39 40 39
std::deque<std::string>::erase(begin) (expensive elements)/8192 -0.0066 -0.0067 40 40 40 40
std::deque<std::string>::erase(middle) (cheap elements)/32 +0.0029 +0.0025 48 48 48 48
std::deque<std::string>::erase(middle) (cheap elements)/1024 -0.0048 -0.0049 557 554 556 554
std::deque<std::string>::erase(middle) (cheap elements)/8192 +0.0080 +0.0075 4297 4331 4294 4326
std::deque<std::string>::erase(middle) (expensive elements)/32 -0.0025 -0.0028 59 59 59 59
std::deque<std::string>::erase(middle) (expensive elements)/1024 -0.0025 -0.0025 569 567 568 567
std::deque<std::string>::erase(middle) (expensive elements)/8192 +0.0228 +0.0225 4310 4408 4307 4404
OVERALL_GEOMEAN
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
tl;dr We can significantly improve the runtime performance of
std::vectorby changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the RFC for more information.vectordepends on__split_bufferfor inserting elements. Changing__split_bufferto matchvector's representation simplifies the model, as it eliminates the need to convert between two different representations of a contiguous buffer in the same configuration of libc++.