This was previously not required, but the patch to introduce a new
size-based vector layout unintentionally added this new requirement. We
almost certainly not want to promise this guarantee going forward, but
we should actually land this change explicitly and consider the
transition story, not do it as a fallout of another refactoring.
Fixes#210732
LWG2210 was a patch to N2554 (C++11) which added missing
allocator-extended constructors to various containers. When LWG2210 was
implemented, the constructors were gated with C++14. However, we
normally apply LWG issue resolutions as DRs.
This patch enables these constructors in C++11 mode too.
Fixes#204843
---------
Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
Co-authored-by: A. Jiang <de34@live.cn>
The closing #endif comment was using _LIBCPP_ABI_SIZE_BASED_VECTOR,
which was the name of the macro in previous iterations of the size-based
vector patch. We ended up landing on _LIBCPP_ABI_VECTOR_LAYOUT_SIZE_BASED
instead.
This commit adds an alternative representation for `std::vector` in a similar
manner to `__split_buffer` in #139632. This alternative representation was
measured to provide significant performance gains over the classic representation.
To do so, 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`.
This new vector representation can be opted into by defining the
_LIBCPP_ABI_VECTOR_LAYOUT_SIZE_BASED macro when configuring the
library's ABI.
This change was the target of this RFC: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi
This patch introduces a new `__in_out_result`, which is an internal
back-ported version of `in_out_result`, and is convertible to that when
it exists. This improves the readability of the code, since it replaces
uses of `first` and `second` with `__in_` and `__out_`, making it clear
which iterator is accessed.
Other algorithms will be updated in separate patches.
`std::exchange` is helpful for simplifying move operations because we
can couple the resetting component with the move operation. This both
halves the number of necessary lines for each move, and also ensures we
haven't forgotten to reset the moved-from object. Since `std::exchange`
is a C++14 feature, we'll need to use `__exchange` for anything that's
from C++11.
This commit also applies `std::__exchange` to a some trivial use-cases
to show its utility. Applying this project-wide requires a census over
all of our types. It's hoped that this will start a community-wide
clean-up that happens over time.
This addresses reviewer feedback on #180102.
We've seen
```
error: No debug information found in function
_ZNSt4__Cr6vectorIN4bssl3der5InputENS_9allocatorIS3_EEE14__swap_layoutsERNS_14__split_bufferIS3_S5_NS_29__split_buffer_pointer_layoutEEE:
Function profile not used [-Werror,-Wbackend-plugin]
```
on an internal bot due to the _LIBCPP_NODEBUG.
There is no reason to double-wrap iterators, since we can already
achieve anything we want within `__bounded_iter`itself.
This is technically ABI breaking, but people using bounded iterators
shouldn't require ABI stability currently.
Fixes#178521
Currently `vector::append_range` grows even when appending a number of
elements that is exactly equal to its spare capacity, which is
guaranteed by the standard to _not_ happen.
Fixes#183256
`-Wchanges-meaning` is a GCC warning that catches shadowing in more
contexts. While a bit annoying here, it's a helpful warning. As such, we
need to rename the `__split_buffer` alias template in `std::vector` so
that we don't trip it up.
`__add_alignment_assumption` unilaterally returned a `pointer`, even
when passed a `const_pointer`. This was surfaced by some (but not all)
CI jobs when rebasing `std::vector` to have a layout type.
Currently, `deque` and `vector`'s `append_range` is implemented in terms
of `insert_range`. The problem with that is that `insert_range` has more
preconditions, resulting in us rejecting valid code.
This also significantly improves performance for `deque` in some cases.
This both simplifies the implementation and improves the performance,
since the compiler is better able to see through what's going on.
```
Benchmark old new Difference % Difference
-------------------------------------------------------------------------- -------------- -------------- ------------ --------------
vector<bool>(const_vector<bool>&) 11.99 12.26 0.27 2.25%
vector<bool>(size_type,_const_value_type&) 9.24 9.29 0.05 0.54%
vector<bool>(vector<bool>&&,_const_allocator_type&)_(different_allocators) 14.26 14.35 0.09 0.65%
vector<bool>(vector<bool>&&,_const_allocator_type&)_(equal_allocators) 2.67 2.67 -0.01 -0.29%
vector<bool>::reserve() 9.30 9.29 -0.01 -0.12%
vector<bool>::resize() 15.14 13.43 -1.71 -11.28%
Geomean 9.17 9.03 -0.14 -1.48%
Allocators should be extremely cheap, if not free, to copy. Furthermore,
we have requirements on allocator types that copies must compare equal,
and that move and copy must be the same.
Hence, taking an allocator by reference should not provide benefits
beyond making a copy of it. However, taking the allocator by reference
leads to complexity in __split_buffer, which can be removed if we stop
using that pattern.
This reduces the amount of code we have to maintain a bit.
This also simplifies `vector` by using the internal API instead of
`#if`s to switch based on language dialect.
The Trivial Relocation feature has been removed from the C++26 working
draft. Based on discussions in Kona, it is unlikely that the
"replaceable" type concept will come back in the C++29 time frame.
Since we don't have a use for the type trait in the library at the
moment, remove the code associated to it. If we end up needing something
like it in the future, we can always add it back.
#119632 introduced a code size and performance regression. This was
verified by running the included benchmark against trunk and trunk with
#119632 reverted. Instead of actually reverting that patch, we can
inline `__construct_at_end` into the few places it's used instead,
simplifying the implementation further (by not handling special cases we
never actually encounter).
```
Benchmark Baseline Candidate Difference % Difference
------------------------ ---------- ----------- ------------ --------------
BM_vector_bool_size_ctor 29.91 8.56 -21.35 -71.37
```
This reverts commit 1bafd020c7.
This breaks the LLDB data formatters which means these failures show up
on every premerge run. Reverting for now until fixing the LLDB
formatters can be coordinated with a relanding.
**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]: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306
---------
Co-authored-by: Jorge Gorbe Moya <jgorbe@google.com>
These are almost certainly intended to not be inlined. This
significantly reduces code size when `push_back` and `emplace_back` are
used heavily.
Fixes#94360
We've built up quite a few links directly to github within the code
base. We should instead use `llvm.org/PR<issue-number>` to link to bugs,
since that is resilient to the bug tracker changing in the future. This
is especially relevant for tests linking to bugs, since they will
probably be there for decades to come. A nice side effect is that these
links are significantly shorter than the GH links, making them much less
of an eyesore.
This patch also replaces a few links that linked to the old bugzilla
instance on llvm.org.
This is brought up in the LWG reflector. We currently call `reserve` if
the underlying container has one. But the spec does not specify what
`reserve` should do for Sequence Container. So in theory if the
underlying container is user defined type and it can have a function
called `reserve` which does something completely different.
The fix is to just call `reserve` for STL containers if it has one
libc++ makes the `hash<vector<bool, A>>::operator()` `constexpr` since
C++20, which is a conforming extension, but it was unintended.
This patch removes the extension, with an escape hatch macro for it, and
the escape hatch will be removed in the future. Test cases for
`constexpr` along with the assumption of hash values are moved to the
`libcxx/test/libcxx/` subdirectory.
---------
Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
That type trait represents whether move-assigning an object is
equivalent to destroying it and then move-constructing a new one from
the same argument. This will be useful in a few places where we may want
to destroy + construct instead of doing an assignment, in particular
when implementing some container operations in terms of relocation.
This is effectively adding a library emulation of P2786R12's
is_replaceable trait, similarly to what we do for trivial relocation.
Eventually, we can replace this library emulation by the real
compiler-backed trait.
This is building towards #129328.
There are currently lots of `_LIBCPP_HAS_ASAN` and
`__libcpp_is_constant_evaluated()` checks which aren't needed, since it
is centrally checked inside `__debug_utils/sanitizers.h`.
The current implementation of `{std, ranges}::equal` fails to correctly
compare `vector<bool>`s when the underlying storage type is smaller than
`int` (e.g., `unsigned char`, `unsigned short`, `uint8_t` and
`uint16_t`). See [demo](https://godbolt.org/z/j4s87s6b3)). The problem
arises due to integral promotions on the intermediate bitwise
operations, leading to incorrect final equality comparison results. This
patch fixes the issue by ensuring that `{std, ranges}::equal` operate
properly for both aligned and unaligned bits.
Fixes#126369.
