D1144R0
Object relocation in terms of move plus destroy

1. Introduction and motivation

If you are reading this paper, and you have not yet watched Arthur’s session from C++Now 2018 on "The Best Type Traits C++ Doesn’t Have," it will help if you immediately stop reading and go watch the first 30 minutes of that video at 2x speed with the captions turned on. It’s going to be worth your 15 minutes. I’ll wait.

In the video, besides showing implementation techniques and benchmark results, we defined our terms. These terms are summarized briefly below.

C++17 knows the verbs "move," "copy," "destroy," and "swap," where "swap" is a higher-level operation composed of several lower-level operations. To this list we propose to add the verb "relocate," which is a higher-level operation composed of exactly two lower-level operations. Given an object type T and memory addresses src and dst, the phrase "relocate a T from src to dst" means no more and no less than "move-construct dst from src, and then immediately destroy the object at src."

Just as the verb "swap" produces the adjective "swappable," the verb "relocate" produces the adjective "relocatable." Any type which is both move-constructible and destructible is relocatable. The notion can be modified by adverbs: we say that a type is nothrow relocatable if its relocation operation is noexcept, and we say that a type is trivially relocatable if its relocation operation is trivial (which, just like trivial move-construction and trivial copy-construction, means "the operation is tantamount to a memcpy").

Almost all relocatable types are trivially relocatable: std::unique_ptr<int>, std::vector<int>, std::string, std::any. Non-trivially relocatable types exist but are rare: boost::interprocess::offset_ptr<int>, for example. See Appendix C: Examples of non-trivially relocatable class types.

Arthur has established (see [Bench]) that if standard library code had a reliable way of detecting "trivial relocatability," we could optimize that case and get a speed boost of up to 3x on routines that perform reallocation, such as

    std::vector<R>::resize
    std::vector<R>::reserve
    std::vector<R>::emplace_back
    std::vector<R>::push_back

Furthermore, Mingxin Wang points out that we can use the same "trivial relocatability" property to shrink the code generated by small-buffer-optimized (SBO) type-erasing wrappers such as std::function and std::any. For these types, a move of the wrapper object is implemented in terms of a relocation of the contained object. (See for example libc++'s std::any, where the function that performs the relocation operation is confusingly named __move.) In general, the relocate operation for a contained type C involves calls to C's move constructor and destructor, which must be uniquely codegenned for each different C; the number of instantiations of relocate scales linearly with the count of distinct types C in the program. But for any trivially relocatable C, its relocate operation depends only on the number of bytes being memcpyed, and so the number of instantiations of relocate scales linearly with the count of distinct sizes of C being used in the program; or indeed, linearly with the count of distinct sizes of SBO buffer being used in the program.

A smaller number of instantiations means faster compile times, a smaller text section, and perhaps "hotter" code (because a relatively higher proportion of your code now fits in icache).

In between these two scenarios, we also find the move-constructor of fixed_capacity_vector<R,N>, which can be implemented as an element-by-element move (leaving the source vector’s elements in their moved-from state), or can be implemented more efficiently as an element-by-element relocate (leaving the source vector empty).

Note: The name fixed_capacity_vector is my preferred name for the type that Boost.Container calls static_vector. boost::container::static_vector<R,N> implements the less efficient element-by-element-move strategy. Moving-out-of a boost::container::static_vector will not make the source vector empty().

2. Design goals

Every C++ type already is or is not trivially relocatable. This proposal is not about "making more types trivially relocatable."

The optimizations discussed above are purely in the domain of library vendors. If you’re writing a vector, and you detect that your element type T is trivially relocatable, then whether you do any special optimization in that case is merely a Quality of Implementation (QoI) issue. This proposal is not about "standardizing certain library optimizations."

What C++ lacks is a standard way for library vendors to detect the (existing) trivial relocatability of a type T, so that they can reliably apply their (existing) optimizations. All we really need is to add detection, and then all the optimizations described above will naturally emerge without any further special effort by WG21.

Library vendors today often (correctly) infer that any trivially copyable type is trivially relocatable. However, we would like to do even better. The following three use-cases are important for improving the performance of real programs:

2.1. Standard library types such as std::string

In order to optimize std::vector<std::string>::resize, we must come up with a way to achieve

    #include <string>
    static_assert(is_trivially_relocatable< std::string >::value);

That is, we can in principle solve §2.1 while confining our "magic" to the headers of the implementation itself. The programmer doesn’t have to learn anything new, so far.

2.2. Program-defined types that follow the Rule of Zero

Note: The term "program-defined types" is defined in [LWG2139] and [LWG3119].

In order to optimize the SBO std::function in any meaningful sense, we must come up with a way to achieve

    #include <string>
    auto lam2 = [x=std::string("hello")]{};
    static_assert(is_trivially_relocatable< decltype(lam2) >::value);

    #include <string>
    struct A {
        std::string s;
    };
    static_assert(is_trivially_relocatable< A >::value);

§2.2 asks specifically that we make the static_assert succeed without breaking the "Rule of Zero." We do not want to require the programmer to annotate struct A with a special attribute, or a special member typedef, or anything like that. We want it to Just Work. Even for lambda types. This is a much harder problem than §2.1; it requires standard support in the core language. But it still does not require any new syntax.

2.3. Program-defined types with non-defaulted special members

In order to optimize std::vector<boost::shared_ptr<T>>::resize, we must come up with a way to achieve

    struct B {
        B(B&&);  // non-trivial
        ~B();  // non-trivial
    };
    static_assert(is_trivially_relocatable< B >::value);

Note: We cannot possibly do it without annotation, because there exist examples of types that look just like B and are trivially relocatable (for example, libstdc++'s std::function) and there exist types that look just like B and are not trivially relocatable (for example, libc++'s std::function). The compiler cannot "crack open" the definitions of B(B&&) and ~B() to see if they combine to form a trivial operation. One, that’s the Halting Problem. Two, the definitions of B(B&&) and ~B() might not be available in this translation unit. Three, the definitions might actually be available and "crackable" in this translation unit, but unavailable in some other translation unit! This would lead to ODR violations and generally really bad stuff. So we cannot achieve our goal by avoiding annotation.

This use-case is the only one that requires us to design the "opt-in" syntax. In §2.1 Standard library types such as std::string, any special syntax is hidden inside the implementation’s own headers. In §2.2 Program-defined types that follow the Rule of Zero, our design goal is to avoid special syntax. In §2.3 Program-defined types with non-defaulted special members, WG21 must actually design user-facing syntax.

Therefore, I believe it would be acceptable to punt on §2.3 and come back to it later. We say, "Sure, that would be nice, but there’s no syntax for it. Be glad that it works for core-language and library types. Ask again in three years." And as long as we leave the design space open, I believe we wouldn’t lose anything by delaying a solution to §2.3.

This paper does propose a standard syntax for §2.3 — an attribute — which in turn provides a simple and portable solution to §2.1 for library vendors. However, our attribute-based syntax is severable from the rest of this paper. With extremely minor surgery, WG21 could reject our new attribute and still solve §2.1 and §2.2 for C++20.

3. Proposed language and library features

This paper proposes five separate additions to the C++ Standard. These additions introduce "relocate" as a well-supported C++ notion on par with "swap," and furthermore, successfully communicate trivial relocatability in each of the three use-cases above.

• A new standard algorithm, uninitialized_relocate(first, last, d_first), in the <memory> header.

• Additional type traits, is_relocatable<T> and is_nothrow_relocatable<T>, in the <type_traits> header.

• A new type trait, is_trivially_relocatable<T>, in the <type_traits> header. This is the detection mechanism.

• A new core-language rule by which a class type’s "trivial relocatability" is inherited according to the Rule of Zero.

• A new attribute, [[trivially_relocatable]], in the core language. This is the opt-in mechanism for program-defined types.

These five bullet points are severable to a certain degree. For example, if the [[trivially_relocatable]] attribute (points 4 and 5) is adopted, library vendors will certainly use it in their implementations; but if the attribute is rejected, library vendors could still indicate the trivial relocatability for certain standard library types by providing library specializations of is_trivially_relocatable (point 3).

Points 1 and 2 are completely severable from points 3, 4, and 5; but we believe these algorithms should be provided for symmetry with the other uninitialized-memory algorithms in the <memory> header (uninitialized_copy, uninitialized_move, and destroy) and the other trios of type-traits in the <type_traits> header (one such trio being is_destructible, is_nothrow_destructible, is_trivially_destructible). I do not expect these templates to be frequently useful, but I believe they must be provided, so as not to unpleasantly surprise the programmer by their absence.

Points 3 and 4 together motivate point 5. In order to achieve the goal of §2.2 Program-defined types that follow the Rule of Zero, we must define a core-language mechanism by which we can "inherit" trivial relocatability. This is especially important for the template case.

    template<class T>
    struct D {
        T t;
    };

    // class C comes in from outside, already marked, via whatever mechanism
    constexpr bool c = is_trivially_relocatable< C >::value;
    constexpr bool dc = is_trivially_relocatable< D<C> >::value;
    static_assert(dc == c);

We expect that the library vendor will implement std::is_trivially_relocatable, just like std::is_trivially_destructible, in terms of a non-standard compiler builtin whose natural spelling is __is_trivially_relocatable(T). The compiler computes the value of __is_trivially_relocatable(T) by inspecting the definition of T (and the definitions of its base classes and members, recursively, in the case that both of its special members are defaulted). This recursive process "bottoms out" at primitive types, or at any type with a user-provided move or destroy operation. Classes with user-provided move or destroy operations must conservatively be assumed not to be trivially relocatable. To achieve the goal of §2.3 Program-defined types with non-defaulted special members, we must provide a way for such a class to "opt in" and warrant to the implementation that it is in fact trivially relocatable (despite being non-trivially move-constructible and/or non-trivially destructible).

In point 5 we propose that the opt-in mechanism should be an attribute. The programmer of a trivially relocatable but non-trivially destructible class C will mark it for the compiler using the attribute:

    struct [[trivially_relocatable]] C {
        C(C&&);  // defined elsewhere
        ~C(); // defined elsewhere
    };
    static_assert(is_trivially_relocatable< C >::value);

4. Proposed wording for C++20

The wording in this section is relative to WG21 draft N4750, that is, the current draft of the C++17 standard.

4.1. Relocation operation

Add a new section in [definitions]:

[definitions] is probably the wrong place for the core-language definition of "relocation operation"

relocation operation

the homogeneous binary operation performed on a range by std::uninitialized_relocate, consisting of a move-construction immediately followed by a destruction of the source object

this definition of "relocation operation" is not good

4.2. Algorithm uninitialized_relocate

Add a new section after [uninitialized.move]:

template<class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_relocate(InputIterator first, InputIterator last,
                                       ForwardIterator result);

Effects: Equivalent to:

for (; first != last; (void)++result, ++first) {
  ::new (static_cast<void*>(addressof(*result)))
    typename iterator_traits<ForwardIterator>::value_type(std::move(*first));
  destroy_at(addressof(*first));
}
return result;

4.3. Algorithm uninitialized_relocate_n

template<class InputIterator, class Size, class ForwardIterator>
  pair<InputIterator, ForwardIterator>
    uninitialized_relocate_n(InputIterator first, Size n, ForwardIterator result);

Effects: Equivalent to:

for (; n > 0; ++result, (void) ++first, --n) {
  ::new (static_cast<void*>(addressof(*result)))
    typename iterator_traits<ForwardIterator>::value_type(std::move(*first));
  destroy_at(addressof(*first));
}
return {first,result};

4.4. Trivially relocatable type

Where in the Standard should we place the definition of "trivially relocatable"?

Add a new section somewhere:

A move-constructible, destructible object type T is a trivially relocatable type if it is:

• a trivially copyable type, or

• a (possibly cv-qualified) class type declared with the [[trivially_relocatable]] attribute, or

• a (possibly cv-qualified) class type which:

  • has either a defaulted, non-deleted move constructor or no move constructor and a defaulted, non-deleted copy constructor,

  • has a defaulted, non-deleted destructor,

  • either is final, or has a final destructor, or has a non-virtual destructor,

  • has no virtual base classes,

  • has no mutable members,

  • all of whose members are either of reference type or of trivially relocatable type, and

  • all of whose base classes are trivially relocatable.

[Note: For a trivially relocatable type, the relocation operation (such as the relocation operations performed by the library functions std::swap and std::vector::resize) is tantamount to a simple copy of the underlying bytes. —end note]

[Note: It is intended that most standard library types be trivially relocatable types. —end note]

Note: We could simplify the wording by removing the words "either is final, or has a final destructor, or". However, this would lead to the compiler’s failing to identify certain (unrealistic) class types as trivially relocatable, when in fact it has enough information to infer that they are trivially relocatable in practice. This would leave room for a "better" implementation beneath ours. I tentatively prefer to optimize for maximum performance over spec simplicity.

Note: There is no special treatment for volatile subobjects. Using memmove on volatile subobjects can cause tearing of reads and writes. Issues [CWG496] and [CWG1746] aimed to evict volatile objects and subobjects from the set of "trivially copyable types," but these changes were reverted by [CWG2094] (2016). As of C++17, bytewise copying of volatile subobjects is permitted by [basic.types]. Arthur has a paper coming for this.

Note: There is no special treatment for possibly overlapping subobjects. Using memmove on possibly overlapping subobjects can overwrite unrelated objects in the vicinity of the destination. This paper introduces no new issues in this area. See [Subobjects].

Must we also say that the relevant move constructor (resp. copy constructor) must be public and unambiguous?

    struct M {
        M() = default;
        M(M&) { puts("evil"); }
        M(const M&) = default;
    };
    struct T {
        mutable M m;
        ~T() = default;
    };
    static_assert( std::is_trivially_relocatable_v<M> );
    static_assert( !std::is_trivially_relocatable_v<T> );

4.5. [[trivially_relocatable]] attribute

Add a new section after [dcl.attr.nouniqueattr]:

The attribute-token trivially_relocatable specifies 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 std::memcpy. It shall appear at most once in each attribute-list and no attribute-argument-clause shall be present. It may be applied to the declaration of a class. The first declaration of a type shall specify the trivially_relocatable attribute if any declaration of that type specifies the trivially_relocatable attribute. If a type is declared with the trivially_relocatable attribute in one translation unit and the same type is declared without the trivially_relocatable attribute in another translation unit, the program is ill-formed, no diagnostic required.

If a type T is declared with the trivially_relocatable attribute, and T is either not move-constructible or not destructible, the program is ill-formed.

If a class type is declared with the trivially_relocatable attribute, the implementation may replace relocation operations involving that type (such as those performed by the library functions std::swap and std::vector::resize) with simple copies of the underlying bytes.

If a class type is declared with the trivially_relocatable attribute, and the program relies on observable side-effects of relocation other than a copy of the underlying bytes, the behavior is undefined.

4.6. Type traits is_relocatable etc.

Add new entries to Table 46 in [meta.unary.prop]:

Template	Condition	Preconditions
template<class T> struct is_relocatable;	is_move_constructible_v<T> is true and is_destructible_v<T> is true	T shall be a complete type, cv void, or an array of unknown bound.
template<class T> struct is_nothrow_relocatable;	is_relocatable_v<T> is true and both the indicated move-constructor and the destructor are known not to throw any exceptions.	T shall be a complete type, cv void, or an array of unknown bound.
template<class T> struct is_trivially_relocatable;	T is a trivially relocatable type.	T shall be a complete type, cv void, or an array of unknown bound.

4.7. Relocatable concept

Add a new section after [concept.moveconstructible]:

template<class T>
  concept Relocatable = MoveConstructible<T> && Destructible<T>;

Note: This concept is exactly equivalent to MoveConstructible<T>.

5. Further considerations and directions

5.1. Trivially swappable types

Mingxin Wang has proposed that "swap" could be expressed in terms of "relocate". std::swap today is typically implemented in terms of one move-construction, two move-assignments, and one destruction; but there is nothing in the Standard that prevents a library vendor from implementing it as three relocations, which in the trivially-relocatable case (the usual case for most types) could be optimized into three calls to memcpy.

For reasons described elsewhere, it seems reasonable to claim that move-assignment must always "do the sane thing," and therefore we might propose to define

template<class T>
struct is_trivially_swappable : bool_constant<
    is_trivially_relocatable_v<T> &&
    is_move_assignable_v<T>
> {};

However, we do not propose "trivially swappable" at the present time. It can easily be added in a later paper.

5.2. Heterogeneous relocation

Consider that is_relocatable_v<T> means is_constructible_v<T,T&&> and is_destructible_v<T>. We have access to a heterogeneous is_constructible<T, Us...>. Should we add a heterogeneous is_relocatable_from<T, U>?

Notice that uninitialized_copy and uninitialized_move are already heterogeneous. Here is what a heterogeneous uninitialized_relocate would look like.

template<class FwdIt, class OutIt>
void uninitialized_relocate(FwdIt first, FwdIt last, OutIt d_first) {
    using SrcT = remove_cvref_t<decltype(*first)>;
    using DstT = remove_cvref_t<decltype(*d_first)>;
    static_assert(is_relocatable_from_v<DstT, SrcT>);
    if constexpr (is_trivially_relocatable_from_v<DstT, SrcT>) {
        static_assert(sizeof (SrcT) == sizeof(DstT));
        if constexpr (is_pointer_v<FwdIt> && is_pointer_v<OutIt>) {
            // Trivial relocation + contiguous iterators = memcpy
            size_t n = last - first;
            if (n) memcpy(d_first, first, n * sizeof (SrcT));
            d_first += n;
        } else {
            while (first != last) {
                memcpy(addressof(*d_first), addressof(*first), sizeof (SrcT));
                ++d_first; ++first;
            }
        }
    } else {
        while (first != last) {
            ::new ((void*)addressof(*d_first)) DstT(move(*first));
            (*first).~SrcT();
            ++d_first; ++first;
        }
    }
    return d_first;
}

This implementation could be used to quickly relocate an array of int* into an array of unique_ptr<int> (but not vice versa). It could also be used to quickly relocate an array of T into an array of tombstone::optional<T>. (The concept of "tombstone optional" is described in [Best].) All we’d need is for somebody to set the value of is_trivially_relocatable_from appropriately for each pair of types in the program.

I think this is a very intriguing idea. The detection syntax (is_trivially_relocatable_from) is fairly obvious. But I don’t see what the opt-in syntax would look like on a program-defined class such as tombstone::optional. Let’s leave that problem alone for a few years and see what develops.

We could conceivably provide the detection trait today, with deliberately curtailed semantics, e.g.:

    template<class T, class U>
    struct is_trivially_relocatable_from : bool_constant<
        is_trivially_relocatable_v<T> and
        is_same_v<U, remove_cvref_t<T>>
    > {};
    template<class T, class U>
    struct is_trivially_relocatable_from<T, U&> : is_trivially_relocatable_from<T, U> {};
    template<class T, class U>
    struct is_trivially_relocatable_from<T, U&&> : is_trivially_relocatable_from<T, U> {};

plus permission for vendors to extend the trait via partial specializations on a QoI basis:

    template<class T>
    struct is_trivially_relocatable_from<unique_ptr<T>, T*> : true_type {};
    template<class T>
    struct is_trivially_relocatable_from<const T*, T*> : true_type {};
    struct is_trivially_relocatable_from<int, unsigned> : true_type {};
    // and so on

However, if we do this, we may soon find that programmers are adding specializations of is_trivially_relocatable_from to their own programs, because they find it makes their code run faster. It will become a de-facto customization point, and we will never be able to "fix it right" for fear of breaking programmers' existing code.

Therefore, I believe that we should not pursue "heterogeneous" relocation operations at the present time.

Note that vendors are already free to optimize heterogeneous operations inside library algorithms, under the as-if rule. We lack a portable and generic detection trait, but vendors are presumably well aware of specific special cases that they could detect and optimize today —for example, a std::copy from an array of int* into an array of const int*, or from an array of 64-bit long into an array of 64-bit long long (see [TCF]). Today vendors generally choose not to perform these optimizations.

6. Acknowledgements

Thanks to Elias Kosunen and Niall Douglas for their feedback on early drafts of this paper.

Thanks to Pablo Halpern for [N4158], to which this paper bears a striking and coincidental 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].

Many thanks to Matt Godbolt for allowing me to place the prototype implementation on Compiler Explorer Beta (a.k.a. godbolt.org/beta).

Appendix A: Straw polls requested

Polls for LEWG

Polls for EWG

Appendix B: Sample code

Defining a trivially relocatable function object

The following sample illustrates §2.2 Program-defined types that follow the Rule of Zero. Here A is a program-defined type following the Rule of Zero. Because all of its bases and members are warranted as trivially relocatable, and its move-constructor and destructor are both defaulted, the compiler concludes that A itself is trivially relocatable.

    #include <string>
    #include <type_traits>

    // Assume that the library vendor has taken care of this part.
    static_assert(std::is_trivially_relocatable_v< std::string >);

    struct A {
        std::string s;
        std::string operator()(std::string t) const { return s + t; }
    };

    static_assert(std::is_trivially_relocatable_v< A >);

The following sample, involving an implementation-defined closure type, also illustrates §2.2 Program-defined types that follow the Rule of Zero.

    #include <string>
    #include <type_traits>

    // Assume that the library vendor has taken care of this part.
    static_assert(std::is_trivially_relocatable_v< std::string >);

    auto a = [s = std::string("hello")](std::string t) {
        return s + t;
    };

    static_assert(std::is_trivially_relocatable_v< decltype(a) >);

Warranting that a user-defined relocation operation is equivalent to memcpy

The following sample illustrates §2.3 Program-defined types with non-defaulted special members. The rules proposed in this paper ensure that any type with non-trivial user-defined move and destructor operations will be considered non-trivially relocatable by default.

    #include <type_traits>

    struct C {
        const char *s = nullptr;
        C(const char *s) : s(s) {}
        C(C&& rhs) : s(rhs.s) { rhs.s = nullptr; }
        ~C() { delete s; }
    };

    static_assert(not std::is_trivially_relocatable_v< C >);

    struct D : C {};

    static_assert(not std::is_trivially_relocatable_v< D >);

The programmer may apply the [[trivially_relocatable]] attribute to override the compiler’s default behavior and warrant (under penalty of undefined behavior) that this type is in fact trivially relocatable.

    #include <type_traits>

    struct [[trivially_relocatable]] E {
        const char *s = nullptr;
        E(const char *s) : s(s) {}
        E(C&& rhs) : s(rhs.s) { rhs.s = nullptr; }
        ~E() { delete s; }
    };

    static_assert(std::is_trivially_relocatable_v< E >);

    struct F : E {};

    static_assert(std::is_trivially_relocatable_v< F >);

Reference implementation of std::uninitialized_relocate

template<class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_relocate(InputIterator first, InputIterator last,
                                       ForwardIterator result)
{
    using T = typename iterator_traits<ForwardIterator>::value_type;
    using U = std::remove_ref_t<decltype(std::move(*first))>;
    constexpr bool memcpyable = (std::is_same_v<T, U> && std::is_trivially_relocatable_v<T>);
    constexpr bool both_contiguous = (std::is_pointer_v<InputIterator> && std::is_pointer_v<ForwardIterator>);

    if constexpr (memcpyable && both_contiguous) {
        std::size_t nbytes = (char *)last - (char *)first;
        if (nbytes != 0) {
            std::memmove(std::addressof(*result), std::addressof(*first), nbytes);
            result += (last - first);
        }
    } else if constexpr (memcpyable) {
        for (; first != last; (void)++result, ++first) {
            std::memmove(std::addressof(*result), std::addressof(*first), sizeof (T));
        }
    } else {
        for (; first != last; (void)++result, ++first) {
            ::new (static_cast<void*>(std::addressof(*result))) T(std::move(*first));
            std::destroy_at(std::addressof(*first));
        }
    }
    return result;
}

The code in the first branch must use memmove, rather than memcpy, to preserve the formally specified behavior in the case that the source range overlaps the destination range.

The code in the second branch, which performs one memmove per element, probably doesn’t have much of a performance benefit, and might be eliminated by library vendors.

Conditionally trivial relocation

We expect, but do not require, that std::optional<T> should be trivially relocatable if and only if T itself is trivially relocatable. We propose no dedicated syntax for conditional [[trivially_relocatable]].

The following abbreviated implementation shows how to achieve an optional<T> which has the same trivial-move-constructibility as T, the same trivial-destructibility as T, and the same trivial-relocatability as T.

template<class T>
class optional :
    optional_a<T, is_trivially_relocatable<T>>
{
    using optional_a<T, is_trivially_relocatable<T>>::optional_a;
};

template<class T, bool R>
class optional_a :
    optional_b<T, is_trivially_destructible<T>, is_trivially_move_constructible<T>>
{
    using optional_b<T, is_trivially_destructible<T>,
        is_trivially_move_constructible<T>>::optional_b;
};

template<class T>
class [[trivially_relocatable]] optional_a<T, true> :
    optional_b<T, is_trivially_destructible<T>, is_trivially_move_constructible<T>>
{
    using optional_b<T, is_trivially_destructible<T>,
        is_trivially_move_constructible<T>>::optional_b;
};

template<class T, bool D, bool M>
class optional_b {
    union {
        char dummy_;
        T value_;
    };
    bool engaged_ = false;

    optional_b() = default;
    optional_b(inplace_t, Args&& args...) :
        engaged_(true), value_(std::forward<Args>(args)...) {}
    optional_b(optional_b&& rhs) {
        if (rhs.engaged_) {
            engaged_ = true;
            ::new (std::addressof(value_)) T(std::move(rhs.value_));
        }
    }
    ~optional_b() {
        if (engaged_) value_.~T();
    }
};

template<class T>
class optional_b<T, false, true> {
    union {
        char dummy_;
        T value_;
    };
    bool engaged_ = false;

    optional_b() = default;
    optional_b(inplace_t, Args&& args...) :
        engaged_(true), value_(std::forward<Args>(args)...) {}
    optional_b(optional_b&&) = default;
    ~optional_b() {
        if (engaged_) value_.~T();
    }
};

template<class T>
class optional_b<T, true, false> {
    union {
        char dummy_;
        T value_;
    };
    bool engaged_ = false;

    optional_b() = default;
    optional_b(inplace_t, Args&& args...) :
        engaged_(true), value_(std::forward<Args>(args)...) {}
    optional_b(optional_b&& rhs) {
        if (rhs.engaged_) {
            engaged_ = true;
            ::new (std::addressof(value_)) T(std::move(rhs.value_));
        }
    }
    ~optional_b() = default;
};

template<class T>
class optional_b<T, true, true> {
    union {
        char dummy_;
        T value_;
    };
    bool engaged_ = false;

    optional_b() = default;
    optional_b(inplace_t, Args&& args...) :
        engaged_(true), value_(std::forward<Args>(args)...) {}

    optional_b(optional_b&&) = default;
    ~optional_b() = default;
};

Appendix C: Examples of non-trivially relocatable class types

Class contains pointer to self

This fictional short_string illustrates a mechanism that can apply to any small-buffer-optimized class. libc++'s std::function uses this mechanism (on a 24-byte buffer) and is thus not trivially relocatable.

However, different mechanisms for small-buffer optimization exist. libc++'s std::any also achieves small-buffer optimization on a 24-byte buffer, without sacrificing trivial relocatability.

struct short_string {
    char *data_ = buffer_;
    size_t size_ = 0;
    char buffer_[8] = {};

    const char *data() const { return data_; }

    short_string() = default;
    short_string(const char *s) : size_(strlen(s)) {
        if (size_ < sizeof buffer_)
            strcpy(buffer_, s);
        else
            data_ = strdup(s);
    }
    short_string(short_string&& s) {
        memcpy(this, &s, sizeof(*this));
        if (s.data_ == s.buffer_)
            data_ = buffer_;
        else
            s.data_ = nullptr;
    }
    ~short_string() {
        if (data_ != buffer_)
            free(data_);
    }
};

Class invariant depends on this

The offset_ptr provided by [Boost.Interprocess] is an example of this category.

struct offset_ptr {
    uintptr_t value_;

    uintptr_t here() const { return uintptr_t(this); }
    uintptr_t distance_to(void *p) const { return uintptr_t(p) - here(); }
    void *get() const { return (void*)(here() + value_); }

    offset_ptr() : value_(distance_to(nullptr)) {}
    offset_ptr(void *p) : value_(distance_to(p)) {}
    offset_ptr(const offset_ptr& rhs) : value_(distance_to(rhs.get())) {}
    offset_ptr& operator=(const offset_ptr& rhs) {
        value_ = distance_to(rhs.get());
        return *this;
    }
    ~offset_ptr() = default;
};

Program invariant depends on this

This example was suggested by Mingxin Wang. In the following snippet, struct Widget is relocatable, but not trivially relocatable, because the relocation operation of destroying a Widget at point A and constructing a new Widget at point B has behavior that is observably different from a simple memcpy.

std::set<void *> registry;

struct registered_object {
    registered_object() { registry.insert(this); }
    registered_object(registered_object&&) = default;
    registered_object(const registered_object&) = default;
    registered_object& operator=(registered_object&&) = default;
    registered_object& operator=(const registered_object&) = default;
    ~registered_object() { registry.erase(this); }
};

struct Widget : registered_object {};

Appendix D: Implementation and benchmarks

A prototype Clang/libc++ implementation is at

• github.com/Quuxplusone/clang/tree/trivially-relocatable

• github.com/Quuxplusone/libcxx/tree/trivially-relocatable

no benchmarks yet