1. Changelog
-
R11 (pre-St Louis 2024):
-
Updated [ParlayLib] status; it conforms with P1144 since February 2024. Updated [Abseil] and [Folly] status. Added [PocketPy] status.
-
Introduce
for the benefit ofNoThrowInputIterator
.uninitialized_relocate_n -
Cross-reference to [P3279].
-
-
R10 (pre-Tokyo 2024):
-
Added implementation experience with [Abseil], [Amadeus], [HPX], [ParlayLib], [StdxError], and [Thrust]. Added §5.2 "Relevance of
".operator = -
Wording for
overloads of the specialized algorithms. Explain why there are noExecutionPolicy
overloads.ranges -
Moved "trivially relocatable class" wording into [class.prop], and increased the similarity between
and[[ trivially_relocatable ]]
.[[ no_unique_address ]]
-
-
R9 (pre-Kona 2023):
-
Added feature-test macros
and__cpp_impl_trivially_relocatable
.__cpp_lib_trivially_relocatable -
Added §3.1 "Design non-goals" and comparison to [P2785R3].
-
Replaced Appendix C "Examples of non-trivially relocatable class types" with a shorter summary.
-
Removed Appendix E "Open questions" as basically redundant with §5.3 "Confusing interactions with
". See "P1144 PMR koans" (June 2023).std :: pmr
-
-
R8 (pre-Varna 2023):
-
dcl.attr.trivreloc: Removed "If a type
is declaredT
, andtrivially_relocatable
is either not move-constructible or not destructible, the program is ill-formed." This should have been removed in R7 along with "move-constructible, destructible."T -
meta.unary.prop: Adjusted the precondition of
to matchis_trivially_relocatable_v
. Removedis_trivially_copyable_v
,is_relocatable_v
for insufficient motivation (but keptis_nothrow_relocatable_v
because it expresses semantic requirements).concept relocatable -
Marked
asstd :: relocate
; changed its return type to[[ nodiscard ]]
.remove_cv_t < T > -
Rewrote §3 "Design goals."
-
-
R7 (post-Issaquah 2023):
-
Added
, the building block ofstd :: uninitialized_relocate_backward
.vector :: insert -
Removed "move-constructible, destructible" from the requirements in basic.types.general. Now trivially relocatable types, like trivially copyable types, can be non-relocatable.
-
Added table §2.1 directly comparing this proposal to Folly, BSL, and Qt.
-
Added straw poll results from Issaquah; removed much background and discussion (leaving only notes for the interested reader to consult [P1144R6]).
-
2. Introduction and motivation
Given an object type
and memory addresses
and
,
the phrase "relocate a
from
to
" means
"move-construct
from
, and then immediately destroy the object at
."
Any type which is both move-constructible and destructible is relocatable.
A type is nothrow relocatable if its relocation operation is noexcept, and a type
is trivially relocatable if its relocation operation is trivial (which,
just like trivial move-construction and trivial copy-construction, means
"tantamount to
").
In practice, almost all relocatable types are trivially relocatable:
,
,
(on libc++ and MSVC),
(on MSVC).
Examples of non-trivially relocatable types include
(on libstdc++ and libc++)
and
(on libstdc++). See Appendix C: Examples of non-trivially relocatable class types and [InPractice].
P1144 allows the library programmer to warrant to the compiler that a resource-management type is trivially relocatable. Explicit warrants are rarely needed because the compiler can infer trivial relocatability for Rule-of-Zero types. See § 4.5 Trivially relocatable type [basic.types.general].
The most important thing about P1144 relocation is that it is backward compatible and does not break either API or ABI. P1144 intends simply to legalize the well-understood tricks that many industry codebases already do (see [BSL], [Folly], [Deque], [Abseil]), not to change the behavior of any existing source code (except to speed it up), nor to require major work from standard library vendors.
2.1. Who optimizes on this?
The following optimizations are possible according to P1144’s notion of trivial relocatability. Here’s who does these optimizations in practice:
vector realloc | type erasure | fixed-cap move | vector
| vector
|
|
| ||
Arthur’s libc++
|
| no | N/A |
(Godbolt) |
(Godbolt) | yes, uses
(Godbolt) |
(Godbolt) | |
[BSL]
|
| no | ? |
|
| , unused by
| no | |
[Folly]
|
| no |
|
|
| N/A | N/A | |
[Qt]
|
|
|
|
|
|
| N/A | |
[Abseil]
| no | N/A |
|
| no | N/A |
| |
[Amadeus]
|
| N/A |
|
|
| N/A | no |
2.1.1. Contiguous reallocation
Trivial relocation helps anywhere we do the moral equivalent of
,
such as in
.
[Bench] (presented at C++Now 2018) shows a 3x speedup on
. This Reddit thread demonstrates a similar 3x speedup using the online tool Quick-Bench.
2.1.2. Moving in-place/SBO type-erased types like any
and function
Trivial relocation can de-duplicate the code generated by type-erasing wrappers
like
,
, and
.
For these types, a move of the wrapper object is implemented in terms of a relocation of the contained object. (E.g., libc++'s
.)
In general, the relocate operation must have a different instantiation for each
different contained type
, leading to code bloat. But every trivially relocatable
of a given size can share the same instantiation.
2.1.3. Moving fixed-capacity containers like static_vector
and small_vector
The move-constructor of
can be implemented naïvely as an element-by-element move (leaving the source vector’s elements in their moved-from state),
or efficiently as an element-by-element relocate (leaving the source vector empty).
For detailed analysis, see [FixedCapacityVector].
currently implements the
naïve element-by-element-move strategy, but after LEWG feedback, [P0843R5]
does permit the faster relocation strategy.
2.1.4. Contiguous insert and erase
Trivial relocation can be used anywhere we shift a contiguous range left or right,
such as in
(i.e., destroy the erased elements and "close the window"
by memmoving left) and
(i.e., "make a window" by memmoving right and
then construct the new elements in place). [Folly]'s
does
this optimization; see
.
Bloomberg’s [BSL] also does this optimization.
2.1.5. Swap
Given a reliable way of detecting trivial relocatability,
we can optimize any routine that uses the moral equivalent of
, such as
,
, or
.
Optimizing
produces massive code-size improvements for all swap-based
algorithms, including
and
.
See [CppNow] @19:56–21:22,
and see this Godbolt. This Quick-Bench shows a 25% speedup
in
when it is allowed to use bitwise swap on a Rule-of-Zero type.
2.2. Assertions, not assumptions
Some data structures might reasonably assert the trivial relocatability of their elements, just as they sometimes assert the stronger property of trivial copyability today. This might help them guarantee reasonable performance, or guarantee exception-safety.
For an example of how
is being used this way in practice,
see [StdxError].
2.3. Eliminate manual warrants, improve safety
Many real-world codebases contain templates which require
trivial relocatability of their template parameters, but cannot today verify trivial relocatability. For example, until 2012 [Folly] required the programmer to warrant the trivial relocatability of any type stored in a
:
class Widget { std :: vector < int > lst_ ; }; folly :: fbvector < Widget > vec ; // FAIL AT COMPILE TIME for lack of warrant
This merely encouraged the programmer to add the warrant and continue. An incorrect warrant was discovered only at runtime, via undefined behavior. See [CppNow] @27:26–31:47; for real-world examples see Folly issues #889, #35, #316, #498.
class Gadget { std :: list < int > lst_ ; }; // sigh, add the warrant on autopilot template <> struct folly :: IsRelocatable < Gadget > : std :: true_type {}; folly :: fbvector < Gadget > vec ; // CRASH AT RUNTIME due to fraudulent warrant
Note: Folly’s
was patched in December 2012 to accept both trivially relocatable and non-trivially relocatable types, in line with
fbvector . Since then, the effect of an incorrect warrant remains the same — UB and crash — but a missing warrant simply disables the optimization.
std :: vector
If this proposal is adopted, then Folly can start using
resp.
in the implementation of
, and the programmer can stop writing explicit warrants.
Finally, the programmer can start writing assertions of correctness, which aids maintainability and
can even find real bugs. Example:
class Widget { std :: vector < int > lst_ ; }; static_assert ( std :: is_trivially_relocatable_v < Widget > ); // correctly SUCCEEDS class Gadget { std :: list < int > lst_ ; }; static_assert ( std :: is_trivially_relocatable_v < Gadget > ); // correctly ERRORS
The improvement in user experience and safety in real-world codebases ([Folly], [BSL], [Qt], [HPX], [Amadeus], [Abseil], etc.) is the most important benefit to be gained by this proposal.
3. Design goals
Briefly: We want to support all five of the following use-cases (Godbolt).
static_assert ( std :: is_trivially_relocatable_v < std :: unique_ptr < int >> ); // #1 struct RuleOfZero { std :: unique_ptr < int > p_ ; }; static_assert ( std :: is_trivially_relocatable_v < RuleOfZero > ); // #2 struct [[ trivially_relocatable ]] RuleOf3 { RuleOf3 ( RuleOf3 && ); RuleOf3 & operator = ( RuleOf3 && ); ~ RuleOf3 (); }; static_assert ( std :: is_trivially_relocatable_v < RuleOf3 > ); // #3 struct [[ trivially_relocatable ]] Wrap0 { boost :: container :: static_vector < int , 10 > v_ ; static_assert ( ! std :: is_trivially_relocatable_v < decltype ( v_ ) > ); // it's not annotated, but we know it's actually trivial }; static_assert ( std :: is_trivially_relocatable_v < Wrap0 > ); // #4 struct [[ trivially_relocatable ]] Wrap3 { Wrap3 ( Wrap3 && ); Wrap3 & operator = ( Wrap3 && ); ~ Wrap3 (); int i_ ; boost :: interprocess :: offset_ptr < int > p_ = & i_ ; static_assert ( ! std :: is_trivially_relocatable_v < decltype ( p_ ) > ); // it's not trivial, but we preserve our invariant correctly }; static_assert ( std :: is_trivially_relocatable_v < Wrap3 > ); // #5
3.1. Non-goals
Note: This section was new in P1144R9.
We propose special support for trivially relocatable types, but no particular support for types that are relocatable in other ways. The two most-frequently-asked scenarios are:
-
"Never-empty types," e.g.
. Such types are not movable (because by design they never enter a moved-from state), but they are swappable and could in theory be relocatable (but not via move-and-destroy, since they cannot be moved). P1144 supports the physical possibility thatgsl :: not_null < unique_ptr < int >>
, but keeps the status quo w.r.t. library support for such types; e.g. you can’tis_trivially_relocatable_v < T > && ! is_relocatable_v < T >
,resize
, orinsert
aerase
of such types. P1144’svector
rejects such types.std :: relocate_at -
Types that are "efficiently but non-trivially relocatable," e.g. libc++'s
, where the ideal relocation operation would trivially relocate the string and move-and-destroy the list; this is not trivial, but still faster than move-and-destroy’ing the wholetuple < string , list < int >>
. P1144 keeps the status quo w.r.t. such types, and doesn’t provide any way to optimize their relocation. See "Cheaply relocatable, but not trivially relocatable" (October 2018).tuple
The most promising active proposal for "non-trivial relocation" is [P2785R3]. It proposes a "relocation constructor" like this:
struct A { A ( A ) = default ; };
which the compiler deduces is trivial iff all of
’s members are trivially relocatable.
This solves both of the above "non-goal" scenarios.
However, [P2785R3] fails to support our positive goals
and
, which are
trivially relocatable despite having some non-trivial members. In other words, P1144 is
forward-compatible with (does not close the door to) [P2785R3]; and vice versa,
adopting [P2785R3] would not solve two of P1144’s five advertised use-cases. WG21 might
well want to adopt both proposals. But P1144 solves "the 99% problem"; P1144 might
not leave enough performance on the table to motivate the further adoption of [P2785R3].
Notably, P1144R10 is almost entirely a subset of [P2785R3]; the only significant difference
is that [P2785R3] doesn’t propose the
warrant itself.
(P2785 proposes that to make a type trivially relocatable, you
its relocation constructor. P1144 can’t do that, and anyway wants to support
and
.)
P1144 | P2785R3 |
---|---|
| |
| |
| |
QoI
on STL containers | Mandate relocation ctors for all STL containers |
(ends ’s lifetime) | |
|
|
| |
|
|
|
|
|
|
|
|
| |
, tag type | |
| |
etc. |
4. Proposed wording for C++26
The wording in this section is relative to the current working draft.
Note: There is no difficulty in changing the attribute syntax to a contextual-keyword syntax;
the only difference is aesthetic. We can defer that decision to the last minute. This wording
is patterned on the precedent set by
.
Note: Our feature-test macros follow the pattern set by
+
and
+
.
4.1. Predefined macro names [cpp.predefined]
Add a feature-test macro to the table in [cpp.predefined]:
__cpp_impl_three_way_comparison 201907L __cpp_impl_trivially_relocatable YYYYMML __cpp_implicit_move 202207L
4.2. Header < version >
synopsis [version.syn]
Add a feature-test macro to [version.syn]/2:
#define __cpp_lib_transparent_operators 201510L // freestanding, also in <memory>, <functional> #define __cpp_lib_trivially_relocatable YYYYMML // freestanding, also in <memory>, <type_traits> #define __cpp_lib_tuple_element_t 201402L // freestanding, also in <tuple>
4.3. Relocation operation [defns.relocation]
Add a new section in [intro.defs]:
relocation operation [defns.relocation]the homogeneous binary operation performed by
, consisting of a move construction immediately followed by a destruction of the source object
std :: relocate_at
4.4. Trivially relocatable class [class.prop]
Note: For the "if supported" wording, compare [dcl.attr.nouniqueaddr]/2 and [cpp.cond]/5.
Note: The wording proposed here deliberately echoes the existing "trivially copyable" wording. "Copyable" and "relocatable" are siblings; every trivially copyable type is trivially relocatable by definition. However, CWG already knows the wording for "trivially copyable" does not match library-writers' expectations; see [P3279] for examples and a possible direction. If that direction is taken, then we’d certainly update the proposed wording of "trivially relocatable" to follow the new wording of "trivially copyable."
Modify [class.prop] as follows:
1․ A trivially copyable class is a class:
that has at least one eligible copy constructor, move constructor, copy assignment operator, or move assignment operator ([special], [class.copy.ctor], [class.copy.assign]),
where each eligible copy constructor, move constructor, copy assignment operator, and move assignment operator is trivial, and
that has a trivial, non-deleted destructor ([class.dtor]).
2․ A trivial class is a class that is trivially copyable and has one or more eligible default constructors ([class.default.ctor]), all of which are trivial. [Note: In particular, a trivially copyable or trivial class does not have virtual functions or virtual base classes. — end note]
x․ A trivially relocatable class is a class:
or a class that is declared with a
- where no eligible copy constructor, move constructor, copy assignment operator, move assignment operator, or destructor is user-provided,
- which has no virtual member functions or virtual base classes,
- all of whose non-static data members are either of reference type or of trivially relocatable type ([basic.types.general]), and
- all of whose base classes are of trivially relocatable type;
attribute with value
trivially_relocatable true
([dcl.attr.trivreloc]) if that attribute is supported by the implementation ([cpp.cond]).3․ A class
is a standard-layout class if it: [...]
S
4.5. Trivially relocatable type [basic.types.general]
Add a new section in [basic.types.general]:
9․ Arithmetic types ([basic.fundamental]), enumeration types, pointer types, pointer-to-member types ([basic.compound]),, and cv-qualified versions of these types are collectively called scalar types. Scalar types, trivially copyable class types ([class.prop]), arrays of such types, and cv-qualified versions of these types are collectively called trivially copyable types. Scalar types, trivial class types ([class.prop]), arrays of such types, and cv-qualified versions of these types are collectively called trivial types. Scalar types, standard-layout class types ([class.prop]), arrays of such types, and cv-qualified versions of these types are collectively called standard-layout types. Scalar types, implicit-lifetime class types ([class.prop]), array types, and cv-qualified versions of these types are collectively called implicit-lifetime types.
std :: nullptr_t x․ Trivially copyable types, trivially relocatable class types ([class.prop]), arrays of such types, and cv-qualified versions of these types are collectively called trivially relocatable types.
[Note: For a trivially relocatable type, the relocation operation ([defns.relocation]) as performed by, for example,
or
std :: swap_ranges , is tantamount to a simple copy of the underlying bytes. —end note]
std :: vector :: reserve [Note: It is intended that most standard library types be trivially relocatable types. —end note]
10․ A type is a literal type if it is: [...]
4.6. Trivially relocatable attribute [dcl.attr.trivreloc]
Note: For the "Recommended practice" wording, compare [dcl.attr.nouniqueaddr]/2.
Add a new section after [dcl.attr.nouniqueaddr]:
1․ The attribute-tokenspecifies that a class type’s relocation operation has no visible side-effects other than a copy of the underlying bytes, as if by the library function
trivially_relocatable . It may be applied to the definition of a class. It shall appear at most once in each attribute-list. An attribute-argument-clause may be present and, if present, shall have the form
std :: memcpy The constant-expression shall be an integral constant expression of type( constant - expression ) . If no attribute-argument-clause is present, it has the same effect as an attribute-argument-clause of
bool .
( true) 2․ If any definition of a class type has a
attribute with value V, then each definition of the same class type shall have a
trivially_relocatable attribute with value V. No diagnostic is required if definitions in different translation units have mismatched
trivially_relocatable attributes.
trivially_relocatable 3․ If a class type is declared with the
attribute, and the program relies on observable side-effects of its relocation other than a copy of the underlying bytes, the behavior is undefined.
trivially_relocatable 4․ Recommended practice: The value of a has-attribute-expression for the
attribute should be
trivially_relocatable for a given implementation unless this attribute can cause a class type to be trivially relocatable ([class.prop]).
0
4.6.1. __has_cpp_attribute
entry [cpp.cond]
Add a new entry to the table of supported attributes in [cpp.cond]:
noreturn 200809L trivially_relocatable YYYYMML unlikely 201803L
4.7. relocatable
concept [concept.relocatable]
Add a new section after [concept.copyconstructible]:
concept [concept.relocatable]
relocatable template < class T > concept relocatable = move_constructible < T > ; 1․ If
is an object type, then let
T be an rvalue of type
rv ,
T an lvalue of type
lv equal to
T , and
rv a distinct object of type
u2 equal to
T .
rv models
T only if
relocatable
- After the definition
,
T u = rv ; is equal to
u .
u2 is equal to
T ( rv ) .
u2 - If the expression
is well-formed, then the expression has the same semantics as
u2 = rv
u2 . ~ T (); :: new (( void * ) std :: addressof ( u2 )) T ( rv ); - If the definition
is well-formed, then after the definition
T u = lv ; is equal to
u .
u2 - If the expression
is well-formed, then the expression’s result is equal to
T ( lv ) .
u2 - If the expression
is well-formed, then the expression has the same semantics as
u2 = lv
u2 . ~ T (); :: new (( void * ) std :: addressof ( u2 )) T ( lv );
Note: We intend that a type may be relocatable
regardless of whether it is copy-constructible; but, if it is copy-constructible then copy-and-destroy
must have the same semantics as move-and-destroy. We intend that a type may be relocatable regardless of
whether it is assignable; but, if it is assignable then assignment must have the same semantics as
destroy-and-copy or destroy-and-move.
The semantic requirements on assignment help us optimize
and
.
satisfies
, but it models
only when all relevant objects have equal allocators.
4.8. Type trait is_trivially_relocatable
[meta.unary.prop]
Add a new entry to Table 47 in [meta.unary.prop]:
Template Condition Preconditions
template < class T > struct is_trivially_copyable ; is a trivially copyable type ([basic.types.general])
T shall be a complete type or cv
remove_all_extents_t < T > .
void
template < class T > struct is_trivially_relocatable ; is a trivially relocatable type ([basic.types.general])
T shall be a complete type or cv
remove_all_extents_t < T > .
void
template < class T > struct is_standard_layout ; is a standard-layout type ([basic.types.general])
T shall be a complete type or cv
remove_all_extents_t < T > .
void
4.9. relocate_at
and relocate
Note: These functions have both been implemented in my libc++ fork; for
, see this Godbolt and [StdRelocateIsCute]. My implementation of their "as-if-by-memcpy" codepaths relies on
Clang’s
; vendors can use any vendor-specific means to implement them.
The wording also deliberately permits a low-quality implementation with no such codepath at all.
See [CppNow] @45:23–48:39.
Add a new section after [specialized.destroy]:
[specialized.relocate]
relocate template < class T > T * relocate_at ( T * source , T * dest ); 1․ Mandates:
is a complete non-array object type.
T 2․ Effects: Equivalent to:
except that ifstruct guard { T * t ; ~ guard () { destroy_at ( t ); } } g ( source ); return :: new ( voidify ( * dest )) T ( std :: move ( * source )); is trivially relocatable ([basic.types.general]), side effects associated with the relocation of the value of
T might not happen.
* source template < class T > [[ nodiscard ]] remove_cv_t < T > relocate ( T * source ); 3․ Mandates:
is a complete non-array object type.
T 4․ Effects: Equivalent to:
except that ifremove_cv_t << T > t = std :: move ( source ); destroy_at ( source ); return t ; is trivially relocatable ([basic.types]), side effects associated with the relocation of the object’s value might not happen.
T
4.10. Nothrow bidirectional iterator [algorithms.requirements]
Modify [algorithms.requirements] as follows:
If an algorithm’s template parameter is named
,
InputIterator ,
InputIterator1 or, or
InputIterator2 , the template argument shall meet the Cpp17InputIterator requirements ([input.iterators]).
NoThrowInputIterator If an algorithm’s template parameter is named
,
OutputIterator , or
OutputIterator1 , the template argument shall meet the
OutputIterator2 requirements ([output.iterators]).
Cpp17OutputIterator If an algorithm’s template parameter is named
,
ForwardIterator ,
ForwardIterator1 ,
ForwardIterator2 or,
NoThrowForwardIterator , or
NoThrowForwardIterator1 , the template argument shall meet the Cpp17ForwardIterator requirements ([forward.iterators]) if it is required to be a mutable iterator, or model
NoThrowForwardIterator2 ([iterator.concept.forward]) otherwise.
forward_iterator If an algorithm’s template parameter is named
,
NoThrowInputIterator ,
NoThrowForwardIterator , or
NoThrowForwardIterator1 , the template argument is also required to have the property that no exceptions are thrown from increment, assignment, or comparison of, or indirection through, valid iterators.
NoThrowForwardIterator2 If an algorithm’s template parameter is named
,
BidirectionalIterator ,
BidirectionalIterator1 or,
BidirectionalIterator2 , or
NoThrowBidirectionalIterator1 , the template argument shall meet the Cpp17BidirectionalIterator requirements ([bidirectional.iterators]) if it is required to be a mutable iterator, or model
NoThrowBidirectionalIterator2 ([iterator.concept.bidir]) otherwise.
bidirectional_iterator - If an algorithm’s template parameter is named
or
NoThrowBidirectionalIterator1 , the template argument is also required to have the property that no exceptions are thrown from increment, decrement, assignment, or comparison of, or indirection through, valid iterators.
NoThrowBidirectionalIterator2
4.11. uninitialized_relocate
, uninitialized_relocate_n
, uninitialized_relocate_backward
[uninitialized.relocate]
Note: Compare to [uninitialized.move] and [alg.copy]. The Remarks allude to blanket wording in [specialized.algorithms.general]/2.
Note: I don’t propose
, because if it worked like
then it would take two ranges (of possibly different lengths). On success, it would relocate-out-of only
elements of
; but if an exception were thrown, it would destroy all the elements of
.
That’s a bad contract. Therefore, we omit the
overloads until someone presents a suitable design.
Modify [memory.syn] as follows:
template < class InputIterator , class NoThrowForwardIterator > NoThrowForwardIterator uninitialized_move ( InputIterator first , // freestanding InputIterator last , NoThrowForwardIterator result ); template < class ExecutionPolicy , class ForwardIterator , class NoThrowForwardIterator > NoThrowForwardIterator uninitialized_move ( ExecutionPolicy && exec , // see [algorithms.parallel.overloads] ForwardIterator first , ForwardIterator last , NoThrowForwardIterator result ); template < class InputIterator , class Size , class NoThrowForwardIterator > pair < InputIterator , NoThrowForwardIterator > uninitialized_move_n ( InputIterator first , Size n , // freestanding NoThrowForwardIterator result ); template < class ExecutionPolicy , class ForwardIterator , class Size , class NoThrowForwardIterator > pair < ForwardIterator , NoThrowForwardIterator > uninitialized_move_n ( ExecutionPolicy && exec , // see [algorithms.parallel.overloads] ForwardIterator first , Size n , NoThrowForwardIterator result ); namespace ranges { template < class I , class O > using uninitialized_move_result = in_out_result < I , O > ; // freestanding template < input_iterator I , sentinel_for < I > S1 , nothrow - forward - iterator O , nothrow - sentinel - for < O > S2 > requires constructible_from < iter_value_t < O > , iter_rvalue_reference_t < I >> uninitialized_move_result < I , O > uninitialized_move ( I ifirst , S1 ilast , O ofirst , S2 olast ); // freestanding template < input_range IR , nothrow - forward - range OR > requires constructible_from < range_value_t < OR > , range_rvalue_reference_t < IR >> uninitialized_move_result < borrowed_iterator_t < IR > , borrowed_iterator_t < OR >> uninitialized_move ( IR && in_range , OR && out_range ); // freestanding template < class I , class O > using uninitialized_move_n_result = in_out_result < I , O > ; // freestanding template < input_iterator I , nothrow - forward - iterator O , nothrow - sentinel - for < O > S > requires constructible_from < iter_value_t < O > , iter_rvalue_reference_t < I >> uninitialized_move_n_result < I , O > uninitialized_move_n ( I ifirst , iter_difference_t < I > n , // freestanding O ofirst , S olast ); } template < class NoThrowInputIterator , class NoThrowForwardIterator > NoThrowForwardIterator uninitialized_relocate ( NoThrowInputIterator first , NoThrowInputIterator last , NoThrowForwardIterator result ); // freestanding template < class ExecutionPolicy , class NoThrowForwardIterator1 , class NoThrowForwardIterator2 > NoThrowForwardIterator2 uninitialized_relocate ( ExecutionPolicy && exec , // see [algorithms.parallel.overloads] NoThrowForwardIterator1 first , NoThrowForwardIterator1 last , NoThrowForwardIterator2 result ); template < class NoThrowInputIterator , class Size , class NoThrowForwardIterator > pair < NoThrowInputIterator , NoThrowForwardIterator > uninitialized_relocate_n ( NoThrowInputIterator first , Size n , NoThrowForwardIterator result ); // freestanding template < class ExecutionPolicy , class NoThrowForwardIterator1 , class Size , class NoThrowForwardIterator2 > pair < NoThrowForwardIterator1 , NoThrowForwardIterator2 > uninitialized_relocate_n ( ExecutionPolicy && exec , // see [algorithms.parallel.overloads] NoThrowForwardIterator1 first , Size n , NoThrowForwardIterator2 result ); template < class NoThrowBidirectionalIterator1 , class NoThrowBidirectionalIterator2 > NoThrowBidirectionalIterator2 uninitialized_relocate_backward ( NoThrowBidirectionalIterator1 first , BidirectionalIterator1 last , NoThrowBidirectionalIterator2 result ); // freestanding template < class ExecutionPolicy , class NoThrowBidirectionalIterator1 , class NoThrowBidirectionalIterator2 > NoThrowBidirectionalIterator2 uninitialized_relocate_backward ( ExecutionPolicy && exec , NoThrowBidirectionalIterator1 first , NoThrowBidirectionalIterator1 last , NoThrowBidirectionalIterator2 result ); // freestanding template < class NoThrowForwardIterator , class T > void uninitialized_fill ( NoThrowForwardIterator first , // freestanding NoThrowForwardIterator last , const T & x );
Add a new section after [uninitialized.move]:
[uninitialized.relocate]
uninitialized_relocate template < class NoThrowInputIterator , class NoThrowForwardIterator > NoThrowForwardIterator uninitialized_relocate ( NoThrowInputIterator first , NoThrowInputIterator last , NoThrowForwardIterator result ); 1․ Effects: Equivalent to:
except that if the iterators' common value type is trivially relocatable, side effects associated with the relocation of the object’s value might not happen.try { for (; first != last ; ++ result , ( void ) ++ first ) { :: new ( voidify ( * result )) typename iterator_traits < NoThrowForwardIterator >:: value_type ( std :: move ( * first )); destroy_at ( addressof ( * first )); } return result ; } catch (...) { destroy ( ++ first , last ); throw ; } 2․ Remarks: If an exception is thrown, all objects in both the source and destination ranges are destroyed.
template < class NoThrowInputIterator , class Size , class NoThrowForwardIterator > pair < NoThrowInputIterator , NoThrowForwardIterator > uninitialized_relocate_n ( NoThrowInputIterator first , Size n , NoThrowForwardIterator result ); 3․ Effects: Equivalent to:
except that if the iterators' common value type is trivially relocatable, side effects associated with the relocation of the object’s value might not happen.try { for (; n > 0 ; ++ result , ( void ) ++ first , -- n ) { :: new ( voidify ( * result )) typename iterator_traits < NoThrowForwardIterator >:: value_type ( std :: move ( * first )); destroy_at ( addressof ( * first )); } return { first , result }; } catch (...) { destroy_n ( ++ first , -- n ); throw ; } 4․ Remarks: If an exception is thrown, all objects in both the source and destination ranges are destroyed.
5․ Effects: Equivalent to:template < class NoThrowBidirectionalIterator1 , class NoThrowBidirectionalIterator2 > NoThrowBidirectionalIterator2 uninitialized_relocate_backward ( NoThrowBidirectionalIterator1 first , NoThrowBidirectionalIterator1 last , NoThrowBidirectionalIterator2 result ); except that if the iterators' common value type is trivially relocatable, side effects associated with the relocation of the object’s value might not happen.try { for (; last != first ; ) { -- last ; -- result ; :: new ( voidify ( * result )) typename iterator_traits < NoThrowBidirectionalIterator2 >:: value_type ( std :: move ( * last )); destroy_at ( addressof ( * last )); } return result ; } catch (...) { destroy ( first , ++ last ); throw ; } 6․ Remarks: If an exception is thrown, all objects in both the source and destination ranges are destroyed.
5. Rationale and alternatives
5.1. Attribute [[ maybe_trivially_relocatable ]]
My Clang implementation, currently available on Godbolt, supports both
and another attribute called
,
as suggested by John McCall in 2018 and also explored by P2786R0 in 2023.
Where
is a "sharp knife" that always cuts what you aim it at,
is a "dull knife" that refuses to cut certain materials.
-
fails to support § 3 Design goals examples #4 and #5.[[ maybe_trivially_relocatable ]] -
See "Should the compiler sometimes reject a
warrant?" (2023-03-10).[[ trivially_relocatable ]] -
See P1144R4 §6.2.
In Issaquah (February 2023), P2786R0 suggested a "dull knife" design similar to
.
EWGI took a three-way straw poll on
versus
,
with an inconclusive 7–5–6 vote (the author of P1144 voting "For" and the three representatives of P2786
voting "Against"; i.e. the vote sans authors was 6–5–3).
5.2. Relevance of operator =
Here’s how current implementations define "is trivially relocatable":
Mainline Clang
: Trivially move-constructible and trivially destructible, or has__is_trivially_relocatable ( T ) [[ clang :: trivial_abi ]] Arthur’s Clang (P1144)
: Trivially copyable, or has__is_trivially_relocatable ( T )
, or has[[ clang :: trivial_abi ]] [[ trivially_relocatable ]] Facebook [Folly]'s
:folly :: IsRelocatable < T >
or has member typedefis_trivially_copyable < T > T :: IsRelocatable Bloomberg [BSL]'s
: Has a conversion tobslmf :: IsBitwiseMoveable < T >
, or has a conversion tobslmf :: NestedTraitDeclaration < T , bslmf :: IsBitwiseMoveable , true>
, orbslmf :: NestedTraitDeclaration < T , bslmf :: IsBitwiseCopyable , true>
, oris_trivially_copyable < T > sizeof ( T ) == 1 Google [Abseil]'s
:absl :: is_trivially_relocatable < T > is_trivially_copyable < T > [Amadeus] AMC’s
:amc :: is_trivially_relocatable < T >
or has member typedefis_trivially_copyable < T > T :: trivially_relocatable Nvidia [Thrust]'s
:thrust :: is_trivially_relocatable < T >
, oris_trivially_copyable < T >
is specialized forproclaim_trivially_relocatable T [HPX]'s
:hpx :: experimental :: is_trivially_relocatable < T >
, or the trait is specialized foris_trivially_copyable < T > T [ParlayLib]'s
:parlay :: is_trivially_relocatable < T >
, oris_trivially_copyable < T >
on Clang; or the trait is specialized for__is_trivially_relocatable ( T ) T [PocketPy]'s
:pkpy :: is_trivially_relocatable_v < T >
andis_trivially_copyable < T >
, oris_trivially_destructible < T >
is specialized forTriviallyRelocatable T
Notice that all library implementors (except Parlay on Clang, due to the Clang builtin’s current behavior) agree that a type with trivial move-constructor, trivial destructor, and non-trivial assignment operator is considered non-trivially relocatable. That is, the assignment operator is relevant!
P1144 preserves that behavior, and justifies it by pointing out that relocation
can replace assignment in
and
, among other algorithms. Existing codebases (most notably [Folly], [Amadeus], and [BSL])
have written a lot of code that branches on
, taking an optimized codepath when
and an unoptimized codepath otherwise. P1144 carefully proposes a definition for
that keeps
those codebases safe, and that never reports a type
as
when it’s not physically safe
to use
with such an optimized codepath.
Here’s a worked example showing why [BSL] pays attention to the assignment operator:
#include <bsl_vector.h>using namespace BloombergLP :: bslmf ; struct T : NestedTraitDeclaration < T , IsBitwiseMoveable > { int i_ ; T ( int i ) : i_ ( i ) {} T ( const T & ) = default ; void operator = ( const T & ) noexcept { puts ( "Called operator=" ); } ~ T () = default ; }; int main () { bsl :: vector < T > v = { 1 , 2 }; v . erase ( v . begin ()); // prints nothing; bsl::vector::erase is optimized } struct U { int i_ ; U ( int i ) : i_ ( i ) {} U ( const U & ) = default ; void operator = ( const U & ) noexcept { puts ( "Called operator=" ); } ~ U () = default ; }; int main () { bsl :: vector < U > v = { 1 , 2 }; v . erase ( v . begin ()); // prints "Called operator="; BSL believes that a non-defaulted // assignment operator makes U non-trivially relocatable. // P1144 agrees. std::is_trivially_relocatable_v<U> // must remain false, so as not to change the // behavior of bsl::vector<U>. }
5.3. Confusing interactions with std :: pmr
Note: See "P1144 PMR koans" (June 2023) for additional analysis of the problem cases.
Note: This section was added in P1144R5, revised in R7, R8, and R10.
Here I assume libc++, where
is trivially relocatable.
P1144 treats move as an optimization of copy; thus we assume that it always ought to be
safe to replace "copy and destroy" with "move and destroy" (and thus with "relocate").
This is informed by Arthur’s experience standardizing "implicit move" in P1155 (C++20) and P2266 (C++23).
"Implicit move" affects
types because their copy differs from their move. Example:
struct ByValueSink { ByValueSink ( std :: pmr :: vector < int > v ) : v_ ( std :: move ( v )) {} std :: pmr :: vector < int > v_ ; }; ByValueSink f ( std :: pmr :: memory_resource * mr ) { auto v = std :: pmr :: vector < int > ( mr ); return v ; // C++17, Clang 12-: Copies (changes allocator) // C++20, GCC, Clang 13+: Moves (preserves allocator) }
We didn’t care about this when fiddling with implicit move; P1144 implicitly believes we shouldn’t care about it now. (This position might be debatable, but it’s definitely part of the worldview that led to P1144’s specific proposed semantics, so it’s good to have this background in mind.)
Some types invariably model
; that is, their assignment is naturally tantamount to construct-and-destroy.
But for
types and polymorphic types, assignment is not tantamount to construct-and-destroy, except under certain conditions. For
types, the condition is "both objects have the same
allocator." For polymorphic types, the condition is "both objects have the same dynamic type."
std :: vector < Derived > dv = { ~~~ }; dv . erase ( dv . begin ()); // Every object in the vector certainly has the same dynamic type. std :: pmr :: vector < std :: pmr :: string > pv = { ~~~ }; pv . erase ( pv . begin ()); // Every string in the vector certainly has the same allocator. Derived da [ 5 ] = { ~~~ }; std :: rotate ( da , da + 2 , da + 5 ); // Every object in the contiguous range certainly has the same dynamic type. std :: pmr :: string pa [ 5 ] = { ~~~ }; std :: rotate ( pa , pa + 2 , pa + 5 ); // Objects in the contiguous range might have different allocators?
P1144 aims to permit efficient insertion and erasure in
. Example:
std :: vector < std :: string > vs ( 501 ); vs . erase ( vs . begin ());
This
requires us to shift down 500
objects. We can do this
by 500 calls to
followed by one call to
, or by
one call to
followed by a
, as in [BSL] (also [Folly], [Amadeus];
see table §2.1). We want to permit BSL’s implementation.
That’s why the definition of
in §4.8 places semantic requirements on
’s assignment operators (if they exist) as well as on
’s constructors and destructors.
If
is considered trivially relocatable, this will trickle down into all Rule-of-Zero
types with a
member. (Godbolt.)
static_assert ( std :: is_trivially_relocatable_v < std :: pmr :: string > ); // Before: not true, of course // After: suppose this is true struct A { std :: pmr :: string ps ; }; static_assert ( std :: is_trivially_relocatable_v < A > ); // After: then this will also be true, by the Rule of Zero std :: vector < A > v ; v . push_back ({ std :: pmr :: string ( "one" , & mr1 )}); v . push_back ({ std :: pmr :: string ( "two" , & mr2 )}); v . erase ( v . begin ()); // Before: Well-defined behavior, acts as-if by assignment // After: Do we somehow make this a precondition violation? assert ( v [ 0 ]. ps . get_allocator (). resource () == & mr1 ); // Before: Succeeds // After: Might fail (and on a quality implementation, *will* fail)
If we (1) advertise
as
; (2) propagate
trivial relocatability in the core language as both P1144 and P2786 propose to do; and
(3) optimize vector insert and erase for trivially relocatable types; then we inevitably
arrive here. Arthur’s solution is to impose preconditions on user-defined types
used within certain parts of the STL: Just as their destructors are forbidden to (dynamically)
throw exceptions, and their copy constructors are forbidden to (dynamically) make things that aren’t copies,
their assignment operators ought to be forbidden to (dynamically) violate
’s semantic requirements.
The proximate conclusion, as far as P1144 is concerned, is that
should not be warranted trivially relocatable by any library vendor unless they’re
willing to place preconditions on how the user can use it in STL containers and algorithms
(which probably wouldn’t be conforming, before further evolution in this space).
The further evolution is out of scope for P1144, but see [P2959R0] for further elaboration of the problem, and [P3055R1] for a proposed solution.
6. Acknowledgements
Thanks to Pablo Halpern for [N4158], to which this paper bears a striking resemblance —including the meaning assigned to the word "trivial," and the library-algorithm approach to avoiding the problems with "lame duck objects" discussed in the final section of [N1377]. See discussion of N4034 at Rapperswil (June 2014) and discussion of N4158 at Urbana (November 2014).
Significantly different approaches to this problem have previously appeared in Rodrigo Castro Campos’s [N2754], Denis Bider’s [P0023R0] (introducing a core-language "relocation" operator), and Niall Douglas’s [P1029R3] (treating trivial relocatability as an aspect of move-construction in isolation, rather than an aspect of the class type as a whole).
A less different approach is taken by Mungo Gill & Alisdair Meredith’s [P2786R5]. [P2814R1] compares P2786R0 against P1144R8.
Thanks to Elias Kosunen, Niall Douglas, John Bandela, and Nicolas Lesser for their feedback on early drafts of P1144R0. Thanks to Jens Maurer for his feedback on P1144R3 at Kona 2019, and to Corentin Jabot for championing P1144R4 at Prague 2020.
Many thanks to Matt Godbolt for allowing me to install my Clang fork on Compiler Explorer (godbolt.org). See also [Announcing].
Thanks to Nicolas Lesser and John McCall for their review comments on the original Clang pull request [D50119]. Thanks to Amirreza Ashouri for reviving the Clang effort in 2024 as #84621.
Thanks to Howard Hinnant for appearing with me on [CppChat], and to Jon Kalb and Phil Nash for hosting us.
Thanks to Marc Glisse for his work integrating a "trivially relocatable" trait into GNU libstdc++ (see [Deque]) and for answering my questions on GCC bug 87106.
Thanks to Dana Jansens for her contributions re overlapping and non-standard-layout types (see [Subspace]), to Alisdair Meredith for our extensive discussions during the February 2023 drafting of P2786R0, to Giuseppe D’Angelo and Thiago Maceira for contributing the Qt entries in table §2.1, and to Giuseppe D’Angelo for extensive review comments and discussion.
Thanks to Charles Salvia (
), Isidoros Tsaousis-Seiras (HPX), Orvid King (Folly),
Daniel Anderson (Parlay), and Derek Mauro (Abseil) for their work integrating P1144 into their
respective libraries.
Thanks to Giuseppe D’Angelo for [P3233]. Thanks to Alan de Freitas, Daniel Liam Anderson, Giuseppe D’Angelo, Hans Goudey, Hartmut Kaiser, Isidoros Tsaousis, Jacques Lucke, Krystian Stasiowski, Shreyas Atre, Stéphane Janel, and Thiago Maciera for [P3236].
Appendix A: Straw polls
Polls taken at EWGI at Issaquah on 2023-02-10
Arthur O’Dwyer presented [P1144R6]. Alisdair Meredith presented P2786R0 (which proposed a
-style facility, and expressed it as a contextual keyword instead
of an attribute). EWGI took the following straw polls (as well as polls on attribute syntax and on both papers' readiness for EWG).
SF | F | N | A | SA | |
---|---|---|---|---|---|
The problem presented in P1144/P2786 is worth solving. | 10 | 8 | 0 | 0 | 0 |
The problem being introduced in P1144/P2786 should be solved in a more general way instead of as proposed. | 3 | 0 | 5 | 6 | 4 |
The annotation should "trust the user" as in P1144R6’s ("sharp knife"),
instead of diagnosing as in P1144R6’s and P2786R0’s ("dull knife"). Three-way poll.
| — | 7 | 5 | 6 | — |
Forward P1144 to EWG. | 0 | 7 | 4 | 3 | 1 |
Polls taken at EWGI at Prague on 2020-02-13
Corentin Jabot championed P1144R4. EWGI discussed P1144R4 and Niall Douglas’s [P1029R3] consecutively, then took the following straw polls (as well as a poll on the attribute syntax).
SF | F | N | A | SA | |
---|---|---|---|---|---|
We believe that P1029 and P1144 are sufficiently different that they should be advanced separately. | 7 | 3 | 2 | 0 | 0 |
EWGI is ok to have the spelling as an attribute with an expression argument. | 3 | 5 | 1 | 1 | 0 |
EWGI thinks the author should explore P1144 as a customizable type trait. | 0 | 0 | 0 | 9 | 2 |
Forward P1144 to EWG. | 1 | 3 | 4 | 1 | 0 |
For polls taken September–November 2018, see [P1144R6].
Appendix B: Sample code
See [P1144R6]'s Appendix B for reference implementations of
,
, and
P1144R6’s version of the
library algorithm, plus
a conditionally trivially relocatable
.
Appendix C: Examples of non-trivially relocatable class types
See [P1144R6]'s Appendix C for compilable examples of types that are not trivially relocatable, for each of the following reasons:
-
Class contains pointer to self (e.g. libstdc++'s
)std :: string -
Allocated memory contains pointer to self (e.g. libstdc++'s
)std :: list -
Class invariant depends on
(e.g.this
)boost :: interprocess :: offset_ptr -
Program invariant depends on
(e.g. a global registry ofthis
addresses)Widget -
Polymorphic object effectively relies on offset-into-self (see also [Polymorphic])
Appendix D: Implementation experience
Core-language implementations
Clang trunk provides a compiler builtin
(see [D114732]), which is largely the same as the trait proposed in this paper.
There remain slight differences; the only major one is that Clang still incorrectly reports
types with user-provided assignment operators (and, on Windows, destructors) as "trivially relocatable."
See the recently fixed Clang #67498 and Clang #77091, as well as Abseil 6b4af24.
As of February 2024, Clang trunk has no equivalent of the
attribute, so
is true only when
is
trivially copyable and/or trivial for purposes of calls. But Clang’s current status
is compatible with P1144, modulo the few unintentional differences listed in the
previous paragraph.
Arthur’s fork of Clang implements all of P1144 (since 2018), and has been kept up-to-date with the latest P1144. See it in action on godbolt.org, under the name "x86-64 clang (experimental P1144)."
Library implementations
Since 2018, Arthur maintains a fork of libc++ with a fully optimizing implementation of P1144. See it in action on godbolt.org, under the name "x86-64 clang (experimental P1144)." (Here is another example showing P1144’s interaction with fancy allocators.)
Since 2023, Arthur maintains a fork of libstdc++ with a conforming implementation of P1144, although it omits some optimizations. For example,
never
lowers to
, and (as of February 2024)
reallocation never relocates. See it in action on godbolt.org, under the name "x86-64 clang (experimental P1144),"
by passing
on the command line.
Since at least December 2018, Nvidia’s [Thrust] implements
, but uses it only as
a detail of device-to-device copy. No relevant algorithms or container optimizations are provided.
Since October 2020, Carnegie Mellon’s [ParlayLib] implements
in the
namespace.
Since 2021, [Amadeus] AMC provides perhaps the most comprehensively optimizing
,
, and
implementations, as well as P1144-compatible
and
in the
namespace.
Since September 2023, Stellar [HPX] implements
and
in the
namespace. This was a GSoC project.
[Qt] implements
in the
namespace, but (unlike P1144’s
)
does not support overlap; it optimizes to
. Qt also provides
, which optimizes to
.
Since November 2018, libstdc++ optimizes
for types that manually specialize
.
(Godbolt.)
As of February 2024, the only libstdc++ library type for which
has
been specialized is
. See [Deque].
[ParlayLib], [PocketPy], [HPX], [Thrust], [Qt], [Folly], and [BSL] all provide "type traits" that are intended to be manually specialized by the client programmer. When compiled with a P1144-compliant compiler, [HPX] and [ParlayLib] do not require (in fact, they forbid) the client programmer to specialize these type traits.
See table §2.1 for more details on most of these library implementations.