P1144 "Trivially relocatable" (3/3): optimize std::vector reallocate/insert and std::swap for trivially relocatable types

[Mordante]

Summary

Part 0/3 is D50119: it adds __has_extension(__is_trivially_relocatable) to the compiler.
Part 1/3 is D61761: it implements the library traits and algorithms mandated by P1144.
Part 2/3 is D63620: it implements Quality-of-Implementation features to warrant certain std library types as "trivially relocatable."
Part 3/3 is D67524: it implements Quality-of-Implementation features to optimize certain std library functions for better performance on types that have been warranted "trivially relocatable."

This patch has no ABI implications (or if it does, that's a bug, please tell me about it).

Notes on optimizations that I've made for https://p1144.godbolt.org/z/q2N_Ln but which are not part of this patch:

• std::any can be made trivially relocatable, by changing _IsSmallObject to be false for non-trivially-relocatable types. However, that would break ABI.

[zoecarver]

Note: std::is_constant_evaluated() is implemented and you can use __libcpp_is_constant_evaluated before C++2a.

I'm going to play around with this patch (and the others) a bit. Then, I can give a more full review.

include/memory

1614 ↗

(On Diff #220005)

Maybe leave a comment about what the various overloads mean.

Also, maybe add a default value (in case we want to use this outside of std::vector in the future).

5760 ↗

(On Diff #220005)

Nit: it might be less confusing to just use ::allocator_type.

5770 ↗

(On Diff #220005)

The more we can use _And the better. That way, at some point in the future, we can create an __and builtin type trait and improve build performance a bit.

include/vector

479 ↗

(On Diff #220005)

We don't need to do this anymore! Every compiler that we support supports rvalues (I think).

[• Quuxplusone]

include/memory

1614 ↗

(On Diff #220005)

Defaulted function arguments are the devil.
I consider it a benefit that now it's impossible to call __construct_forward without explicitly saying whether you want to use memcpy or not; this is because the call to __construct_forward will usually be followed by a call to __destroy_at_end, and the final parameter to both calls must agree (or else you might call a constructor without the matching destructor, or vice versa).

Adding a comment is a good idea, but I'm not sure the best place to put it. Incidentally, in a previous revision I'd had something like

template<class X, class UseMemcpy>
static void foo(X x, UseMemcpy) { ... }
template<class X>
static void foo(X x, false_type) { ... }

where the first overload matches true_type; but that was unnecessary, error-prone, and not really any less confusing, so I trashed it.

5760 ↗

(On Diff #220005)

This is actually doing SFINAE on the value of __is_uncustomized — which in user-defined specializations of allocator_traits will either be absent (if they went from scratch) or have the wrong value (if they derived from allocator_traits<allocator<T>> to fill in the boilerplate).

The __has_trivial_construct part of this patch is a watered-down version of D49317. For now and maybe forever, libc++ wisely doesn't permit users to specialize allocator_traits. (See https://quuxplusone.github.io/blog/2018/07/14/traits-classes/ .)
So I guess it would be fine for me to eliminate __has_customized_allocator_traits from this patch.

include/vector

479 ↗

(On Diff #220005)

I think you're right, but then I'm confused by the similar code on the return type of move_if_noexcept (in trunk). What does _Tp&& mean, in C++03 mode? Is it a synonym for const _Tp&? If so, why does move_if_noexcept need that ifndef?

template <class _Tp>
inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11
#ifndef _LIBCPP_CXX03_LANG
typename conditional
<
    !is_nothrow_move_constructible<_Tp>::value && is_copy_constructible<_Tp>::value,
    const _Tp&,
    _Tp&&
>::type
#else  // _LIBCPP_CXX03_LANG
const _Tp&
#endif
move_if_noexcept(_Tp& __x) _NOEXCEPT
{
    return _VSTD::move(__x);
}

[zoecarver]

include/vector

479 ↗

(On Diff #220005)

Clang supports rvalues in C++03 mode. So it will work just like in C++11 mode. move_if_noexcept probably just hasn't been updated. Example: https://godbolt.org/z/L2CJQa

[• Quuxplusone]

Address most of @zoecarver's review comments. (Haven't looked into _And yet.)
Since __libcpp_is_constant_evaluated() is usable, use it in std::swap. (This passes all the test cases for swap, including the constexpr ones! Hooray!)

[EricWF]

How were the performance benefits measured? Are they visible in the existing benchmarks?

[• Quuxplusone]

Add a new benchmark, and add a TriviallyRelocatableType to the matrix in algorithms.bench.cpp.

My expectation is that swap.bench.cpp should get noticeably faster after this patch.

My less confident expectation is that the new .*trivre.* test cases in algorithms.bench.cpp should initially be noticeably worse than the .*string.* cases, but after this patch they should catch up. What's happening there is that when you swap strings, you're calling string's own ADL overload of swap which is very fast, but when you swap TriviallyRelocatableTypes, you're calling the generic std::swap<TriviallyRelocatableType> which is not quite so fast until this patch makes it do memcpy.

I'm putting the benchmarks right here in this patch so that @EricWF can run them. (Zoe and I produced some good-looking benchmark numbers earlier tonight, with code similar to this code; but my build tree is too screwed up to reproduce them on demand.)

[• Quuxplusone]

Fix a bug in my vector::insert; it wasn't exception-safe.

[• Quuxplusone]

In D67524#1674849, @Quuxplusone wrote:

I'm putting the benchmarks right here in this patch so that @EricWF can run them. (Zoe and I produced some good-looking benchmark numbers earlier tonight, with code similar to this code; but my build tree is too screwed up to reproduce them on demand.)

@EricWF ping!

[• Quuxplusone]

@EricWF ping!

[• Quuxplusone]

In D67524#1674849, @Quuxplusone wrote:

I'm putting the benchmarks right here in this patch so that @EricWF can run them. (Zoe and I produced some good-looking benchmark numbers earlier tonight, with code similar to this code; but my build tree is too screwed up to reproduce them on demand.)

@EricWF ping!

[• Quuxplusone]

Rebased on master, and fixed an exception-safety bug in my patch to vector::insert/erase.

[• Quuxplusone]

@EricWF ping!

[• Quuxplusone]

Migrate to the monorepo.
@EricWF ping? What's the deal with this new benchmark?

[Mordante]

Since P1144 is still in flight in WG21 abandoning this patch for now. When the paper is approved we can look it up again and see how outdated it is.

libcxx/benchmarks/algorithms.bench.cpp

 
 #include <algorithm>
 #include <cstdint>
 #include <map>
 #include <random>
 #include <string>
 #include <utility>
 #include <vector>
 
 #include "CartesianBenchmarks.h"
 #include "GenerateInput.h"
 #include "benchmark/benchmark.h"
 #include "test_macros.h"
 
 namespace {
 
-enum class ValueType { Uint32, String };
-struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
-  static constexpr const char* Names[] = {"uint32", "string"};
+struct TriviallyRelocatableType {
+  std::string datamember;
+  explicit TriviallyRelocatableType(std::string m) : datamember(m) {}
+  bool operator<(const TriviallyRelocatableType& rhs) const {
+    return this->datamember < rhs.datamember;
+  }
+  bool operator>(const TriviallyRelocatableType& rhs) const {
+    return this->datamember > rhs.datamember;
+  }
+};
+
+enum class ValueType { Uint32, String, Trivre };
+struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 3> {
+  static constexpr const char* Names[] = {"uint32", "string", "trivre"};
 };
 
 template <class V>
 using Value =
-    std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;
+    std::conditional_t<V() == ValueType::Uint32, uint32_t,
+    std::conditional_t<V() == ValueType::String, std::string,
+    TriviallyRelocatableType> >;
 
 enum class Order {
   Random,
   Ascending,
   Descending,
   SingleElement,
   PipeOrgan,
   Heap
void fillValues(std::vector<std::string>& V, size_t N, Order O) {
   if (O == Order::SingleElement) {
     V.resize(N, getRandomString(1024));
   } else {
     while (V.size() < N)
       V.push_back(getRandomString(1024));
   }
 }
 
+void fillValues(std::vector<TriviallyRelocatableType>& V, size_t N, Order O) {
+  if (O == Order::SingleElement) {
+    V.resize(N, TriviallyRelocatableType(getRandomString(1024)));
+  } else {
+    while (V.size() < N)
+      V.emplace_back(getRandomString(1024));
+  }
+}
+
 template <class T>
 void sortValues(T& V, Order O) {
   assert(std::is_sorted(V.begin(), V.end()));
   switch (O) {
   case Order::Random: {
     std::random_device R;
     std::mt19937 M(R());
     std::shuffle(V.begin(), V.end(), M);

libcxx/benchmarks/swap.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+#include <list>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "benchmark/benchmark.h"
+#include "GenerateInput.h"
+
+struct R {
+  std::vector<char> m;
+  void initializeWith(const std::string& s) {
+    m.assign(s.begin(), s.end());
+  }
+  struct Less {
+    bool operator()(const R& a, const R& b) const noexcept {
+        return a.m < b.m;
+    }
+  };
+};
+
+struct NR {
+  std::list<char> m;
+  void initializeWith(const std::string& s) {
+    m.assign(s.begin(), s.end());
+  }
+  struct Less {
+    bool operator()(const NR& a, const NR& b) const noexcept {
+      return a.m < b.m;
+    }
+  };
+};
+
+static void BM_TriviallyRelocatableSwapRanges(benchmark::State& st) {
+  std::vector<R> pv(1000);
+  std::vector<R> qv(1000);
+  while (st.KeepRunning()) {
+    std::swap_ranges(pv.begin(), pv.end(), qv.begin());
+    benchmark::DoNotOptimize(pv);
+    benchmark::DoNotOptimize(qv);
+  }
+}
+BENCHMARK(BM_TriviallyRelocatableSwapRanges);
+
+static void BM_NonTriviallyRelocatableSwapRanges(benchmark::State& st) {
+  std::vector<NR> pv(1000);
+  std::vector<NR> qv(1000);
+  while (st.KeepRunning()) {
+    std::swap_ranges(pv.begin(), pv.end(), qv.begin());
+    benchmark::DoNotOptimize(pv);
+    benchmark::DoNotOptimize(qv);
+  }
+}
+BENCHMARK(BM_NonTriviallyRelocatableSwapRanges);
+
+static void BM_TriviallyRelocatableMakeHeap(benchmark::State& st) {
+  std::vector<R> original(1000);
+  for (R& elt : original)
+    elt.initializeWith(getRandomString(256));
+  std::vector<R> v(1000);
+  while (st.KeepRunning()) {
+    st.PauseTiming();
+    v = original;
+    st.ResumeTiming();
+    std::make_heap(v.begin(), v.end(), R::Less{});
+    benchmark::DoNotOptimize(v);
+  }
+}
+BENCHMARK(BM_TriviallyRelocatableMakeHeap);
+
+static void BM_NonTriviallyRelocatableMakeHeap(benchmark::State& st) {
+  std::vector<NR> original(1000);
+  for (NR& elt : original)
+    elt.initializeWith(getRandomString(256));
+  std::vector<NR> v(1000);
+  while (st.KeepRunning()) {
+    st.PauseTiming();
+    v = original;
+    st.ResumeTiming();
+    std::make_heap(v.begin(), v.end(), NR::Less{});
+    benchmark::DoNotOptimize(v);
+  }
+}
+BENCHMARK(BM_NonTriviallyRelocatableMakeHeap);
+
+BENCHMARK_MAIN();

libcxx/include/memory

             {return __select_on_container_copy_construction(
                 __has_select_on_container_copy_construction<const allocator_type>(),
                 __a);}
 
     template <class _Ptr>
         _LIBCPP_INLINE_VISIBILITY
         static
         void
-        __construct_forward_with_exception_guarantees(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2)
+        __construct_forward_with_exception_guarantees(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2, false_type)
         {
             static_assert(__is_cpp17_move_insertable<allocator_type>::value,
               "The specified type does not meet the requirements of Cpp17MoveInsertible");
             for (; __begin1 != __end1; ++__begin1, (void) ++__begin2)
               construct(__a, _VSTD::__to_address(__begin2),
 #ifdef _LIBCPP_NO_EXCEPTIONS
                         _VSTD::move(*__begin1)
 #else
                         _VSTD::move_if_noexcept(*__begin1)
 #endif
                         );
         }
 
-    template <class _Tp>
+    template <class _Ptr>
         _LIBCPP_INLINE_VISIBILITY
         static
-        typename enable_if
-        <
-            (__is_default_allocator<allocator_type>::value
-                || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
-             is_trivially_move_constructible<_Tp>::value,
-            void
-        >::type
-        __construct_forward_with_exception_guarantees(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __begin2)
+        void
+        __construct_forward_with_exception_guarantees(allocator_type&, _Ptr __begin1, _Ptr __end1, _Ptr& __begin2, true_type)
         {
+            typedef typename iterator_traits<_Ptr>::value_type _Tp;
+            typedef typename remove_const<_Tp>::type _Vp;
             ptrdiff_t _Np = __end1 - __begin1;
             if (_Np > 0)
             {
-                _VSTD::memcpy(__begin2, __begin1, _Np * sizeof(_Tp));
+                _VSTD::memcpy(const_cast<_Vp*>(_VSTD::__to_address(__begin2)), _VSTD::__to_address(__begin1), _Np * sizeof(_Tp));
                 __begin2 += _Np;
             }
         }
 
     template <class _Iter, class _Ptr>
         _LIBCPP_INLINE_VISIBILITY
         static
         void

                 __begin2 += _Np;
             }
         }
 
     template <class _Ptr>
         _LIBCPP_INLINE_VISIBILITY
         static
         void
-        __construct_backward_with_exception_guarantees(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __end2)
+        __construct_backward_with_exception_guarantees(allocator_type& __a, _Ptr __begin1, _Ptr __end1, _Ptr& __end2, false_type)
         {
             static_assert(__is_cpp17_move_insertable<allocator_type>::value,
               "The specified type does not meet the requirements of Cpp17MoveInsertable");
             while (__end1 != __begin1)
             {
               construct(__a, _VSTD::__to_address(__end2 - 1),
 #ifdef _LIBCPP_NO_EXCEPTIONS
                         _VSTD::move(*--__end1)
 #else
                         _VSTD::move_if_noexcept(*--__end1)
 #endif
                         );
               --__end2;
             }
         }
 
-    template <class _Tp>
+    template <class _Ptr>
         _LIBCPP_INLINE_VISIBILITY
         static
-        typename enable_if
-        <
-            (__is_default_allocator<allocator_type>::value
-                || !__has_construct<allocator_type, _Tp*, _Tp>::value) &&
-             is_trivially_move_constructible<_Tp>::value,
-            void
-        >::type
-        __construct_backward_with_exception_guarantees(allocator_type&, _Tp* __begin1, _Tp* __end1, _Tp*& __end2)
+        void
+        __construct_backward_with_exception_guarantees(allocator_type&, _Ptr __begin1, _Ptr __end1, _Ptr& __end2, true_type)
         {
+            typedef typename iterator_traits<_Ptr>::value_type _Tp;
+            typedef typename remove_const<_Tp>::type _Vp;
             ptrdiff_t _Np = __end1 - __begin1;
             __end2 -= _Np;
             if (_Np > 0)
-                _VSTD::memcpy(__end2, __begin1, _Np * sizeof(_Tp));
+            {
+                _VSTD::memcpy(const_cast<_Vp*>(_VSTD::__to_address(__end2)), _VSTD::__to_address(__begin1), _Np * sizeof(_Tp));
+            }
         }
 
 private:
 
     _LIBCPP_INLINE_VISIBILITY
     static pointer __allocate(allocator_type& __a, size_type __n,
         const_void_pointer __hint, true_type)
         {return __a.allocate(__n, __hint);}

 
   template <class _Tp>
   _LIBCPP_NODEBUG _LIBCPP_ALWAYS_INLINE
   static void __deallocate_type(void* __p, size_t __n) _NOEXCEPT {
       __deallocate_bytes(__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));
   }
 };
 
+// __has_trivial_construct, __has_trivial_destroy
+
+template <class _Alloc>
+struct __is_exactly_std_allocator : false_type {};
+
+template <class _Tp>
+struct __is_exactly_std_allocator<allocator<_Tp> > : true_type {};
+
+template <class _Alloc, class _Tp, class... _Args>
+struct __has_trivial_construct : integral_constant<bool,
+    (__is_exactly_std_allocator<_Alloc>::value || !__has_construct<_Alloc, _Tp*, _Args...>::value)
+> {};
+
+template <class _Alloc, class _Tp>
+struct __has_trivial_destroy : integral_constant<bool,
+    (__is_exactly_std_allocator<_Alloc>::value || !__has_destroy<_Alloc, _Tp*>::value)
+> {};
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #if defined(_LIBCPP_HAS_PARALLEL_ALGORITHMS) && _LIBCPP_STD_VER >= 17
 #   include <__pstl_memory>
 #endif
 
 #endif  // _LIBCPP_MEMORY

libcxx/include/type_traits

       template<class B>
         inline constexpr bool negation_v = negation<B>::value;           // C++17
 
 }
 
 */
 #include <__config>
 #include <cstddef>
+#include <cstring>
 #include <version>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _T1, class _T2> struct _LIBCPP_TEMPLATE_VIS pair;
 template <class _Tp> class _LIBCPP_TEMPLATE_VIS reference_wrapper;
 template <class _Tp> struct _LIBCPP_TEMPLATE_VIS hash;
 
+#ifndef _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED
+#if _LIBCPP_STD_VER > 17
+_LIBCPP_INLINE_VISIBILITY
+inline constexpr bool is_constant_evaluated() noexcept {
+  return __builtin_is_constant_evaluated();
+}
+#endif
+
+inline _LIBCPP_CONSTEXPR
+bool __libcpp_is_constant_evaluated() _NOEXCEPT { return __builtin_is_constant_evaluated(); }
+#else
+inline _LIBCPP_CONSTEXPR
+bool __libcpp_is_constant_evaluated() _NOEXCEPT { return false; }
+#endif
+
 template <class _Tp, _Tp __v>
 struct _LIBCPP_TEMPLATE_VIS integral_constant
 {
   static _LIBCPP_CONSTEXPR const _Tp      value = __v;
   typedef _Tp               value_type;
   typedef integral_constant type;
   _LIBCPP_INLINE_VISIBILITY
   _LIBCPP_CONSTEXPR operator value_type() const _NOEXCEPT {return value;}

 >::type
 #else
 void
 #endif
 _LIBCPP_CONSTEXPR_AFTER_CXX17
 swap(_Tp& __x, _Tp& __y) _NOEXCEPT_(is_nothrow_move_constructible<_Tp>::value &&
                                     is_nothrow_move_assignable<_Tp>::value)
 {
-    _Tp __t(_VSTD::move(__x));
-    __x = _VSTD::move(__y);
-    __y = _VSTD::move(__t);
+    if (__libcpp_is_trivially_relocatable<_Tp>::value && !is_volatile<_Tp>::value && !__libcpp_is_constant_evaluated()) {
+        if (!is_empty<_Tp>::value) {
+            // TODO: if either __x or __y is a "possibly overlapping subobject"
+            // in Itanium ABI terms, this will memcpy too much data. But the
+            // same caveat has applied to std::copy and friends, since forever.
+            char __t[sizeof (_Tp)];
+            // We cannot use __libcpp_relocate_at here, because the stack array
+            // is deliberately underaligned for an actual object of type _Tp.
+            // We are deliberately shuffling bytes here, not objects.
+            _VSTD::memcpy(__t, _VSTD::addressof(__x), sizeof(_Tp));
+            _VSTD::memcpy(_VSTD::addressof(__x), _VSTD::addressof(__y), sizeof(_Tp));
+            _VSTD::memcpy(_VSTD::addressof(__y), __t, sizeof(_Tp));
+        }
+    } else {
+        _Tp __t(_VSTD::move(__x));
+        __x = _VSTD::move(__y);
+        __y = _VSTD::move(__t);
+    }
 }
 
 template<class _Tp, size_t _Np>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 typename enable_if<
     __is_swappable<_Tp>::value
 >::type
 swap(_Tp (&__a)[_Np], _Tp (&__b)[_Np]) _NOEXCEPT_(__is_nothrow_swappable<_Tp>::value)

 // This specialization returns __extract_key_fail_tag for non-map containers
 // because _Key == _ContainerValueTy
 template <class _ValTy, class _Key, class _RawValTy>
 struct __can_extract_map_key<_ValTy, _Key, _Key, _RawValTy>
     : false_type {};
 
 #endif
 
-#ifndef _LIBCPP_HAS_NO_BUILTIN_IS_CONSTANT_EVALUATED
-#if _LIBCPP_STD_VER > 17
-_LIBCPP_INLINE_VISIBILITY
-inline constexpr bool is_constant_evaluated() noexcept {
-  return __builtin_is_constant_evaluated();
-}
-#endif
-
-inline _LIBCPP_CONSTEXPR
-bool __libcpp_is_constant_evaluated() _NOEXCEPT { return __builtin_is_constant_evaluated(); }
-#else
-inline _LIBCPP_CONSTEXPR
-bool __libcpp_is_constant_evaluated() _NOEXCEPT { return false; }
-#endif
-
 template <class _CharT>
 using _IsCharLikeType = _And<is_standard_layout<_CharT>, is_trivial<_CharT> >;
 
 _LIBCPP_END_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 14
 // std::byte
 namespace std  // purposefully not versioned

libcxx/include/vector

 {
     if (__begin_ != nullptr)
     {
         clear();
         __alloc_traits::deallocate(__alloc(), __begin_, capacity());
     }
 }
 
+template<class _Tp, class _Allocator>
+struct __vector_move_via_memcpy : integral_constant<bool,
+    is_trivially_move_constructible<_Tp>::value &&
+    __has_trivial_construct<_Allocator, _Tp, _Tp&&>::value &&
+    !is_volatile<_Tp>::value
+> {};
+
+template<class _Tp, class _Allocator>
+struct __vector_relocate_via_memcpy : integral_constant<bool,
+    __libcpp_is_trivially_relocatable<_Tp>::value &&
+    __has_trivial_construct<_Allocator, _Tp, _Tp&&>::value &&
+    __has_trivial_destroy<_Allocator, _Tp>::value &&
+    !is_volatile<_Tp>::value
+> {};
+
 template <class _Tp, class _Allocator /* = allocator<_Tp> */>
 class _LIBCPP_TEMPLATE_VIS
       _LIBCPP_TRIVIALLY_RELOCATABLE_IF((__vector_base<_Tp, _Allocator>::__allow_trivial_relocation::value))
     vector
     : private __vector_base<_Tp, _Allocator>
 {
 private:
     typedef __vector_base<_Tp, _Allocator>           __base;
private:
     void __append(size_type __n, const_reference __x);
     _LIBCPP_INLINE_VISIBILITY
     iterator       __make_iter(pointer __p) _NOEXCEPT;
     _LIBCPP_INLINE_VISIBILITY
     const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
     void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
     pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
     void __move_range(pointer __from_s, pointer __from_e, pointer __to);
+    template<class _Up>
+        void __relocate_upward_and_insert(pointer __from_s, pointer __from_e, _Up&& __elt);
     void __move_assign(vector& __c, true_type)
         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
     void __move_assign(vector& __c, false_type)
         _NOEXCEPT_(__alloc_traits::is_always_equal::value);
     _LIBCPP_INLINE_VISIBILITY
     void __destruct_at_end(pointer __new_last) _NOEXCEPT
     {
         __invalidate_iterators_past(__new_last);

 vector(_InputIterator, _InputIterator, _Alloc)
   -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
 #endif
 
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
 {
+    typedef integral_constant<bool,
+        __vector_move_via_memcpy<_Tp, _Allocator>::value ||
+        __vector_relocate_via_memcpy<_Tp, _Allocator>::value
+    > __move_via_memcpy;
+    typedef integral_constant<bool,
+        __vector_relocate_via_memcpy<_Tp, _Allocator>::value
+    > __destroy_via_noop;
 
     __annotate_delete();
     __alloc_traits::__construct_backward_with_exception_guarantees(
-        this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
+        this->__alloc(), this->__begin_, this->__end_, __v.__begin_, __move_via_memcpy());
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
     __v.__first_ = __v.__begin_;
+    __v.__destruct_at_end(__v.__begin_, __destroy_via_noop());
     __annotate_new(size());
     __invalidate_all_iterators();
 }
 
 template <class _Tp, class _Allocator>
 typename vector<_Tp, _Allocator>::pointer
 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
 {
+    typedef integral_constant<bool,
+        __vector_move_via_memcpy<_Tp, _Allocator>::value ||
+        __vector_relocate_via_memcpy<_Tp, _Allocator>::value
+    > __move_via_memcpy;
+    typedef integral_constant<bool,
+        __vector_relocate_via_memcpy<_Tp, _Allocator>::value
+    > __destroy_via_noop;
+
     __annotate_delete();
     pointer __r = __v.__begin_;
     __alloc_traits::__construct_backward_with_exception_guarantees(
-        this->__alloc(), this->__begin_, __p, __v.__begin_);
+        this->__alloc(), this->__begin_, __p, __v.__begin_, __move_via_memcpy());
     __alloc_traits::__construct_forward_with_exception_guarantees(
-        this->__alloc(), __p, this->__end_, __v.__end_);
+        this->__alloc(), __p, this->__end_, __v.__end_, __move_via_memcpy());
     _VSTD::swap(this->__begin_, __v.__begin_);
     _VSTD::swap(this->__end_, __v.__end_);
     _VSTD::swap(this->__end_cap(), __v.__end_cap());
     __v.__first_ = __v.__begin_;
+    __v.__destruct_at_end(__v.__begin_, __destroy_via_noop());
     __annotate_new(size());
     __invalidate_all_iterators();
     return __r;
 }
 
 //  Allocate space for __n objects
 //  throws length_error if __n > max_size()
 //  throws (probably bad_alloc) if memory run out
#if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
         "vector::erase(iterator) called with an iterator not"
         " referring to this vector");
 #endif
     _LIBCPP_ASSERT(__position != end(),
         "vector::erase(iterator) called with a non-dereferenceable iterator");
     difference_type __ps = __position - cbegin();
     pointer __p = this->__begin_ + __ps;
+    _Tp *__rawp = _VSTD::__to_address(__p);
+    if (__vector_relocate_via_memcpy<_Tp, _Allocator>::value) {
+        __alloc_traits::destroy(this->__alloc(), __rawp);
+        --this->__end_;
+        if (__p != this->__end_) {
+            _VSTD::memmove(__rawp, __rawp + 1, this->__end_ - __p);
+        }
+    } else {
         this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
+    }
     this->__invalidate_iterators_past(__p-1);
     iterator __r = __make_iter(__p);
     return __r;
 }
 
 template <class _Tp, class _Allocator>
 typename vector<_Tp, _Allocator>::iterator
 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
#endif
     if (__first != __last) {
         this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
         this->__invalidate_iterators_past(__p - 1);
     }
     iterator __r = __make_iter(__p);
     return __r;
 }
 
+#ifdef _LIBCPP_CXX03_LANG
+template<class _Allocator, class _Tp, class _Up>
+struct __is_nothrow_constructible_a : integral_constant<bool, false> {};
+#else
+template<class _Allocator, class _Tp, class _Up>
+struct __is_nothrow_constructible_a : integral_constant<bool,
+    noexcept(allocator_traits<_Allocator>::construct(declval<_Allocator&>(), (_Tp*)nullptr, declval<_Up>()))
+> {};
+#endif
+
+template<class _Tp, class _Up>
+struct __is_nothrow_constructible_a<allocator<_Tp>, _Tp, _Up> : is_nothrow_constructible<_Tp, _Up> {};
+
+template<class _Tp, class _Allocator>
+template<class _Up>
+void
+vector<_Tp, _Allocator>::__relocate_upward_and_insert(pointer __from_s, pointer __from_e, _Up&& __elt)
+{
+    if (__vector_relocate_via_memcpy<_Tp, _Allocator>::value && __is_nothrow_constructible_a<_Allocator, _Tp, _Up&&>::value) {
+        _VSTD::memmove(_VSTD::__to_address(__from_s + 1), _VSTD::__to_address(__from_s), (__from_e - __from_s) * sizeof(_Tp));
+        ++this->__end_;
+        __alloc_traits::construct(this->__alloc(),
+                                  _VSTD::__to_address(__from_s),
+                                  static_cast<_Up&&>(__elt));
+    } else {
+        __move_range(__from_s, __from_e, __from_s + 1);
+        *__from_s = static_cast<_Up&&>(__elt);
+    }
+}
+
 template <class _Tp, class _Allocator>
 void
 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
 {
     pointer __old_last = this->__end_;
     difference_type __n = __old_last - __to;
     {
       pointer __i = __from_s + __n;
#endif
     if (this->__end_ < this->__end_cap())
     {
         if (__p == this->__end_)
         {
             __construct_one_at_end(__x);
         }
         else
         {
-            __move_range(__p, this->__end_, __p + 1);
             const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
             if (__p <= __xr && __xr < this->__end_)
                 ++__xr;
-            *__p = *__xr;
+            __relocate_upward_and_insert(__p, this->__end_, *__xr);
         }
     }
     else
     {
         allocator_type& __a = this->__alloc();
         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
         __v.push_back(__x);
         __p = __swap_out_circular_buffer(__v, __p);
#endif
     if (this->__end_ < this->__end_cap())
     {
         if (__p == this->__end_)
         {
             __construct_one_at_end(_VSTD::move(__x));
         }
         else
         {
-            __move_range(__p, this->__end_, __p + 1);
-            *__p = _VSTD::move(__x);
+            __relocate_upward_and_insert(__p, this->__end_, _VSTD::move(__x));
         }
     }
     else
     {
         allocator_type& __a = this->__alloc();
         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
         __v.push_back(_VSTD::move(__x));
         __p = __swap_out_circular_buffer(__v, __p);
#endif
     {
         if (__p == this->__end_)
         {
             __construct_one_at_end(_VSTD::forward<_Args>(__args)...);
         }
         else
         {
             __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
-            __move_range(__p, this->__end_, __p + 1);
-            *__p = _VSTD::move(__tmp.get());
+            __relocate_upward_and_insert(__p, this->__end_, _VSTD::move(__tmp.get()));
         }
     }
     else
     {
         allocator_type& __a = this->__alloc();
         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
         __v.emplace_back(_VSTD::forward<_Args>(__args)...);
         __p = __swap_out_circular_buffer(__v, __p);

libcxx/test/libcxx/containers/sequences/vector/insert_trivially_relocatable.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <vector>
+
+// void insert(const_iterator it, const value_type& x);
+
+// UNSUPPORTED: c++98, c++03
+
+#include <vector>
+#include <cassert>
+
+static int assignments = 0;
+
+template<bool TR>
+struct _LIBCPP_TRIVIALLY_RELOCATABLE_IF(TR) MyClass {
+    int value;
+    explicit MyClass(int i) : value(i) {}
+    MyClass(const MyClass& rhs) {
+        value = rhs.value;
+    }
+    MyClass(MyClass&& rhs) noexcept {
+        value = rhs.value;
+    }
+    MyClass& operator=(const MyClass& rhs) {
+        ++assignments;
+        value = rhs.value;
+        return *this;
+    }
+    MyClass& operator=(MyClass&& rhs) {
+        ++assignments;
+        value = rhs.value;
+        return *this;
+    }
+    ~MyClass() {}
+};
+
+template<bool TR>
+void test()
+{
+    using T = MyClass<TR>;
+    std::vector<T> vec;
+    vec.reserve(5);
+    vec.push_back(T(1));
+    vec.push_back(T(2));
+    vec.push_back(T(3));
+
+    assignments = 0;
+    vec.insert(vec.begin() + 2, T(4));
+    if (TR) {
+        assert(assignments == 0);  // relocate upward without assigning
+    } else {
+        assert(assignments >= 1);
+    }
+
+    assignments = 0;
+    vec.insert(vec.begin() + 2, T(5));
+    if (TR) {
+        assert(assignments == 0);  // relocate upward without assigning
+    } else {
+        assert(assignments >= 1);
+    }
+}
+
+int main(int, char**)
+{
+    test<true>();
+    test<false>();
+    return 0;
+}

libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_exception_safety.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <vector>
+
+// void insert(const_iterator it, const value_type& x);
+
+#include <vector>
+#include <cassert>
+
+static int countdown = 0;
+static int constructions = 0;
+static int destructions = 0;
+
+struct MyError {};
+
+template<bool TR, bool CC, bool MC, bool CA, bool MA>
+struct _LIBCPP_TRIVIALLY_RELOCATABLE_IF(TR) MyClass {
+    int value;
+    explicit MyClass(int i) : value(i) { ++constructions; }
+    MyClass(const MyClass& rhs) _NOEXCEPT_(!CC) {
+        value = rhs.value;
+        if (CC && countdown-- == 0) throw MyError();
+        ++constructions;
+    }
+    MyClass(MyClass&& rhs) _NOEXCEPT_(!MC) {
+        value = rhs.value;
+        if (MC && countdown-- == 0) throw MyError();
+        ++constructions;
+    }
+    MyClass& operator=(const MyClass& rhs) _NOEXCEPT_(!CA) {
+        value = rhs.value;
+        if (CA && countdown-- == 0) throw MyError();
+        return *this;
+    }
+    MyClass& operator=(MyClass&& rhs) _NOEXCEPT_(!MA) {
+        value = rhs.value;
+        if (MA && countdown-- == 0) throw MyError();
+        return *this;
+    }
+    ~MyClass() { ++destructions; }
+};
+
+template<int Mask>
+void test()
+{
+    using T = MyClass<!!(Mask & 1), !!(Mask & 2), !!(Mask & 4), !!(Mask & 8), !!(Mask & 16)>;
+    for (int n = 0; true; ++n) {
+        {
+            std::vector<T> vec;
+            vec.reserve(5);
+            try {
+                countdown = n;
+                vec.push_back(T(1));
+                vec.push_back(T(2));
+                vec.push_back(T(3));
+                vec.insert(vec.begin() + 2, T(4));
+                vec.insert(vec.begin() + 2, T(5));
+                // if we reach here, no exception was thrown
+                break;
+            } catch (const MyError&) {
+                assert(constructions == destructions + static_cast<int>(vec.size()));
+            }
+        }
+        // destroy the vector and check the invariant again
+        assert(constructions == destructions);
+    }
+}
+
+int main(int, char**)
+{
+    test<0x00>();
+    test<0x01>();
+    test<0x02>();
+    test<0x03>();
+    test<0x04>();
+    test<0x05>();
+    test<0x06>();
+    test<0x07>();
+    test<0x08>();
+    test<0x09>();
+    test<0x0a>();
+    test<0x0b>();
+    test<0x0c>();
+    test<0x0d>();
+    test<0x0e>();
+    test<0x0f>();
+    test<0x10>();
+    test<0x11>();
+    test<0x12>();
+    test<0x13>();
+    test<0x14>();
+    test<0x15>();
+    test<0x16>();
+    test<0x17>();
+    test<0x18>();
+    test<0x19>();
+    test<0x1a>();
+    test<0x1b>();
+    test<0x1c>();
+    test<0x1d>();
+    test<0x1e>();
+    test<0x1f>();
+    return 0;
+}