C++ Logo

std-discussion

Advanced search

Re: [P2786R13] replaceability and aliasing

From: Giuseppe D'Angelo <giuseppe.dangelo_at_[hidden]>
Date: Sun, 16 Mar 2025 15:40:31 +0100
On 16/03/2025 13:46, Ell via Std-Discussion wrote:
>
> On 3/13/25 20:36, Giuseppe D'Angelo via Std-Discussion wrote:
>> Concretely speaking, this requirement was introduced to allow
>> erasure/insertion in the middle of a std::vector to use (trivial)
>> relocation instead of assignment. In such a scenario both the extra
>> properties I described above hold.
> There's another quirk, which also doesn't affect moving stuff around in
> a vector, but affects the general definitions: some types are not
> replaceable, but*are* replace-relocatable. For example, an std::list
> that allocates its sentinel node (list2 in the paper), whose move
> constructor can throw.


> You can't replace move-assignment with destruction + move-construction,
> because if the constructor throws you end up with a dead list. However,
> you*can* replace move-assignment + destruction (of the source) with
> destruction (of the destination) + (trivial) relocation.

Yes, one could also refine the replacement operation with "... assuming
the move constructor doesn't throw" or something like that.

Again, the point is to signal a container that it _can_ replace move
assignments with destructions+move constructions. The container doesn't
_have to_ do such a thing, especially if move assignments are nothrow
and replacements are throwing.

Concretely speaking I'd expect an implementation of vector<T>::erase /
insert/emplace/... to have a decision tree like this:


1) Is T replaceable? If not, keep doing move assignments.

T may even be trivially relocatable. However an implementation may not
be willing to change its current implementation from move assignments to
a (trivial-)relocation-based approach, because it changes the behavior
of existing code.

(Aside: if we're talking about std::vector specifically, it may not even
be *authorized* to do so by the container requirements, which still say
things like "the assignment operator of T is called the number of times
equal to the number of elements in the vector after the erased elements"
https://eel.is/c++draft/vector#modifiers-5 or similar.

Despite a lot of discussions it is still very much unclear whether
"equal to" is a literal "equal to" or it's an upper bound as per
https://eel.is/c++draft/structure.specifications#7 , so doing 0
assignments is fine. While the Standard is not a tutorial, saying "equal
to" but meaning "up to" sounds *very* misleading IMHO.)


2) Otherwise, T is replaceable.

2a) Is T trivially relocatable? Then do trivial relocation.

2b) Is T nothrow relocatable? Then do relocation (maybe).

2c) Otherwise: keep doing move assignments. The idea here is that either
move assignments don't throw (for instance a non-TR std::list that
allocates the sentinel node); or, if they do, you have optimized your
type already for this use case as this is the current behavior from
containers. For instance, you may prefer a result where a throwing move
assignment thrown during erase/insert/... leaves "something" behind for
you, whereas a throwing relocation would wipe out all the affected elements.


2b at the moment is still a bit of a question mark. There are certainly
some types that are nothrow relocatable but not trivially relocatable
(for instance a std::string with SSO which contains a pointer into
itself). The question is whether move assignments would be faster than
destroy+move construct for these types. In the experiments I've run the
answer seems to be yes (e.g. libstdc++ string gives anywhere between 10%
and 50% speedup), but that's far from a universal metric. In any case,
if you're fine with it, then 2a+2b can be handled together by the
uninitialized relocation algorithms proposed by P3516, covered by a "is
T nothrow relocatable" guard.


My 2 c,
--
Giuseppe D'Angelo

Received on 2025-03-16 14:40:38