[libc++] Fix performance inconsistency between map/set copy-assignment and copy-constructor

[ldionne]

Summary

Before this patch, std::map's copy constructor and copy assignment operators
would have significantly different performance characteristics. This was
caused by tree::operator= using assign_multi even in the case of a
container with unique keys like std::map. Furthermore, upon investigation,
it appears that __assign_unique was actually slower in some cases than
insert(first, last), because we were not using a hint to insert in the
loop. This patch fixes that issue which provides a small additional speedup.

In the future, we could instead reintroduce a copy assignment operator in
tree and copy the whole tree without performing any comparison. This
isn't done in this patch because such a patch should ensure the copy
assignment and copy constructors for tree are consistent, which goes
beyond the targeted fix I'm trying to do here. See https://llvm.org/PR62571.

This patch also adds a benchmark for std::map copy assignment, which
highlights the performance inconsistency we had.

---

Benchmark Time CPU Iterations

(before) BM_ConstructorCopy_MapSize=1000000 60.2 ns 60.2 ns 11000000
(before) BM_CopyAssignment_MapSize=1000000 68.7 ns 68.7 ns 11000000
(before) BM_CopyAssignmentPrepopulated_MapSize=1000000 42.1 ns 42.1 ns 17000000

(after) BM_ConstructorCopy_MapSize=1000000 59.9 ns 59.9 ns 12000000
(after) BM_CopyAssignment_MapSize=1000000 59.9 ns 59.9 ns 12000000
(after) BM_CopyAssignmentPrepopulated_MapSize=1000000 40.7 ns 40.7 ns 18000000

rdar://89335215

[ldionne]

Add regression test.

[var-const]

libcxx/benchmarks/map.bench.cpp

171

Question: why are we using a different naming convention here (with capitalized variable Names)?

1046

Question: is a similar benchmark for set needed? And perhaps multimap, unless it's covered by this test?

libcxx/include/set

613–617

Question: it's _VSTD and not std for consistency within the file, right?

libcxx/test/libcxx/containers/associative/perf.assignment_vs_construction.pass.cpp

3 ↗

(On Diff #414745)

A couple of questions:

• can/should we use Google Benchmark here?
• is this file compiled with optimizations enabled?

21 ↗

(On Diff #414745)

Nit: include <vector>.

27 ↗

(On Diff #414745)

If I understand correctly, all the generated strings will be short enough for SSO to kick in. Is this desirable (I presume it effectively turns copies into moves and minimizes the time difference between the old and new implementations, thus testing for the "worst" case scenario)? If yes, it might be worth adding a comment to that effect.

Also, now that I think of it, what's the reason to use strings and not integers as the key type?

33 ↗

(On Diff #414745)

Alternatively, this code could use an unordered_map to store generated keys and not add them to keys if they were already seen before. Though I don't think efficiency matters for this function.

43 ↗

(On Diff #414745)

Very optional / question: using <chrono> always makes me want to create a short alias like using namespace chr = std::chrono. What's your preference on this?

50 ↗

(On Diff #414745)

Note: this could overflow if iterations were unbounded, though if we're always using a small integer, it doesn't matter.

57–59 ↗

(On Diff #414745)

Optional: test_map and test_set could probably be merged into a single function by moving the difference out into a helper. The best I could come up with is to have a functor that takes care of the difference in value_type (to avoid specializing for all 4 map/set variations):

template <typename Container, typename Func>
void test(std::vector<std::string> const& keys, Func const& value_type_func) {
...
tmp.insert(value_type_func(key));

...

test<std::map<std::string, int>(keys, [](const auto& s) { return std::make_pair(s, 1); });

Though it might be not worth it.

62 ↗

(On Diff #414745)

I'm a bit concerned about the compiler seeing that foo is never used and potentially optimizing it away. Is it known that it's not the case / cannot be the case?

[var-const]

Note: it looks like the double underscore in front of the tree name causes incorrect formatting in the patch description. Perhaps putting __tree inside backpacks would help (if you think it's worth fixing).

libcxx/include/__tree

1116–1119

From the patch description: "In the future, we could instead reintroduce a copy assignment operator in
tree and copy the whole tree without performing any comparison". Would it be worthwhile adding a TODO to that effect here?

[Mordante]

Nice that this issue has been found!

libcxx/include/__tree

1116–1119

+1 for the TODO.

libcxx/include/set

613–617

These changes are quite unexpected when reading the patch description. Can you update the description?
(Same for the multi(map|set).)

libcxx/test/libcxx/containers/associative/perf.assignment_vs_construction.pass.cpp

10 ↗

(On Diff #414745)

When this can't be done in Google Benchmark please add the rationale here.

71 ↗

(On Diff #414745)

When this is the reason to not do it in Google Benchmark I think it's worthwhile to consider how we can test for timing regressions in the benchmarks. (This would even be good to look into regardless of this patch.)

[EricWF]

I don't think a custom benchmarking test is appropriate. Please rewrite your benchmarks using Google benchmark.

libcxx/benchmarks/map.bench.cpp

171

Probably because I started it because I was feeling funky. Not sure it matters much.

173

I don't think this is the correct usage of KeepRunningBatch.

175

What about the case where the map is already populated? And with different sizes?

libcxx/include/__tree

1120

On another note: a copy assignment operator gets implicitly declared by the compiler. For readability lets make that implicit declaration explicit.

1628

Could we make this faster for non-multi containers by using a different assign f ml

libcxx/include/set

617

What's the performance like if you call __assign_unique(__s.begin(), __s.end()) instead?

libcxx/test/libcxx/containers/associative/perf.assignment_vs_construction.pass.cpp

3 ↗

(On Diff #414745)

Yes, this should be google benchmark.

[EricWF]

PS. This is removing an optimization where:

(A) the node allocations are reused during assignment
(B) For reused nodes, the types assignment operator is called.

So this could be a significant regression when either

(A) Memory allocation is slow.
(B) The element types assignment operator is faster than its copy constructor (imagine a case where it too is reusing resources).

So I think we need more benchmarks that attempt to measure the performance in these cases.

[EricWF]

libcxx/include/__tree

1628

Ignore this comment.

[ldionne]

Rebase, address comments and improve performance more.

[ldionne]

libcxx/benchmarks/map.bench.cpp

171

Yeah it's weird but I am staying consistent with the rest of the file.

173

This is what I see in GoogleBenchmark:

// Returns true iff the benchmark should run n more iterations.
// REQUIRES: 'n' > 0.
// NOTE: A benchmark must not return from the test until KeepRunningBatch()
// has returned false.
// NOTE: KeepRunningBatch() may overshoot by up to 'n' iterations.
//
// Intended usage:
//   while (state.KeepRunningBatch(1000)) {
//     // process 1000 elements
//   }
bool KeepRunningBatch(IterationCount n);

You're right that it's a bit weird since we're only "processing" one element here (aka we're doing the assignment of a single map). However, if I look at how all these benchmarks were written, I think the intent is that we pretend that copying each element in the map is "one iteration". I guess that's done so that the output of Google Benchmark can show the time taken on average for each element given a map with N elements in it. That's what we do in all the benchmarks in this file.

Anyway, I switched all the constructor-related benchmarks to use the pattern used in ConstructorMove, which gave me the most sensical and the most consistent results.

175

Added a benchmark.

libcxx/include/__tree

1116–1119

See https://github.com/llvm/llvm-project/issues/62571

1120

Since there's a move constructor, it won't get declared. But I explicitly marked it as deleted.

libcxx/include/set

613–617

This is taken from the __tree::operator= code we were using before, so there are no changes really.

Question: it's _VSTD and not std for consistency within the file, right?

Hmm, I'll use std anyway.

617

It's better in case there's already elements in the tree, so I changed it to that instead. Good catch!

libcxx/test/libcxx/containers/associative/perf.assignment_vs_construction.pass.cpp

3 ↗

(On Diff #414745)

I basically removed this test. The goal was to have a regression test that would catch when copy assignment and copy construction are not within a reasonable margin of each other, which we don't achieve with our current benchmarks. But I think it's fine to instead have just the benchmarks under libcxx/benchmarks.

71 ↗

(On Diff #414745)

Yes, I agree, however let's not block this patch on figuring out how to do performance regression testing.

[ldionne]

Rebase onto D150119 to fix C++03 issue

[ldionne]

Rebase onto main

[Mordante]

libcxx/benchmarks/map.bench.cpp

121

Why regenerating the data?

124

Why remove the validation?

libcxx/include/__tree

1642

I really wished somebody would have named this function __insert_unique_hint.

libcxx/include/map

1902

Actually I think this is needed.

• we allocated nodes with allocator foo
• we change the allocator to bar in __tree_.__copy_assign_alloc(__m.__tree_);
• the __tree_.__assign_multi will remove the exiting nodes using allocator bar instead of foo

Am I missing something?

When I'm correct please fix the other 3 assignments too. And then we probably need tests too.

libcxx/benchmarks/map.bench.cpp

struct ConstructorDefault {
 
   std::string name() const { return "BM_ConstructorDefault"; }
 };
 
 struct ConstructorIterator : Base {
   using Base::Base;
 
   void run(benchmark::State& State) const {
-    auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
-    auto& Map = Data.Maps.front();
-    while (State.KeepRunningBatch(MapSize)) {
-#ifndef VALIDATE
-      benchmark::DoNotOptimize(
-          std::map<uint64_t, int64_t>(Map.begin(), Map.end()));
-#else
-      std::map<uint64_t, int64_t> M{Map.begin(), Map.end()};
-      if (M != Map)
-        State.SkipWithError("Map copy not identical");
-#endif
+    auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+    while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
+      for (auto& Map : Data.Maps) {
+        std::map<uint64_t, int64_t> M(Map.begin(), Map.end());
+        benchmark::DoNotOptimize(M);
+      }
+      State.PauseTiming();
+      Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+      State.ResumeTiming();
     }
   }
 
   std::string name() const { return "BM_ConstructorIterator" + baseName(); }
 };
 
 struct ConstructorCopy : Base {
   using Base::Base;
 
   void run(benchmark::State& State) const {
-    auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1);
-    auto& Map = Data.Maps.front();
-    while (State.KeepRunningBatch(MapSize)) {
-#ifndef VALIDATE
+    auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+    while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
+      for (auto const& Map : Data.Maps) {
         std::map<uint64_t, int64_t> M(Map);
         benchmark::DoNotOptimize(M);
-#else
-      std::map<uint64_t, int64_t> M(Map);
-      if (M != Map)
-        State.SkipWithError("Map copy not identical");
-#endif
+      }
+      State.PauseTiming();
+      Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+      State.ResumeTiming();
     }
   }
 
   std::string name() const { return "BM_ConstructorCopy" + baseName(); }
 };
 
 struct ConstructorMove : Base {
   using Base::Base;
while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
       Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
       State.ResumeTiming();
     }
   }
 
   std::string name() const { return "BM_ConstructorMove" + baseName(); }
 };
 
+struct CopyAssignment : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+    while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
+      for (auto const& Map : Data.Maps) {
+        std::map<uint64_t, int64_t> M;
+        M = Map;
+        benchmark::DoNotOptimize(M);
+      }
+      State.PauseTiming();
+      Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+      State.ResumeTiming();
+    }
+  }
+
+  std::string name() const { return "BM_CopyAssignment" + baseName(); }
+};
+
+struct CopyAssignmentPrepopulated : Base {
+  using Base::Base;
+
+  void run(benchmark::State& State) const {
+    auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+    auto Init = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+    while (State.KeepRunningBatch(MapSize * Data.Maps.size())) {
+      for (std::size_t i = 0; i != Data.Maps.size(); ++i) {
+        Init.Maps[i] = Data.Maps[i];
+        benchmark::DoNotOptimize(Init.Maps[i]);
+      }
+      State.PauseTiming();
+      Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+      Init = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000);
+      State.ResumeTiming();
+    }
+  }
+
+  std::string name() const { return "BM_CopyAssignmentPrepopulated" + baseName(); }
+};
+
 //*******************************************************************|
 //                           Capacity                                |
 //*******************************************************************|
 
 struct Empty : Base {
   using Base::Base;
 
   void run(benchmark::State& State) const {
#else
   const std::vector<size_t> MapSize{10, 100, 1000, 10000, 100000, 1000000};
 #endif
 
   // Member functions
   makeCartesianProductBenchmark<ConstructorDefault>();
   makeCartesianProductBenchmark<ConstructorIterator>(MapSize);
   makeCartesianProductBenchmark<ConstructorCopy>(MapSize);
   makeCartesianProductBenchmark<ConstructorMove>(MapSize);
+  makeCartesianProductBenchmark<CopyAssignment>(MapSize);
+  makeCartesianProductBenchmark<CopyAssignmentPrepopulated>(MapSize);
 
   // Capacity
   makeCartesianProductBenchmark<Empty>(MapSize);
   makeCartesianProductBenchmark<Size>(MapSize);
 
   // Modifiers
   makeCartesianProductBenchmark<Clear>(MapSize);
   makeCartesianProductBenchmark<Insert, AllModes, AllOrders>(MapSize);

libcxx/include/__tree

public:
 
     typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
     typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
 
     _LIBCPP_HIDE_FROM_ABI explicit __tree(const value_compare& __comp)
         _NOEXCEPT_(
             is_nothrow_default_constructible<__node_allocator>::value &&
             is_nothrow_copy_constructible<value_compare>::value);
     _LIBCPP_HIDE_FROM_ABI explicit __tree(const allocator_type& __a);
     _LIBCPP_HIDE_FROM_ABI __tree(const value_compare& __comp, const allocator_type& __a);
     _LIBCPP_HIDE_FROM_ABI __tree(const __tree& __t);
-    _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t);
+    _LIBCPP_HIDE_FROM_ABI __tree& operator=(const __tree& __t) = delete; // use __assign_unique or __assign_multi instead
     template <class _ForwardIterator>
     _LIBCPP_HIDE_FROM_ABI void __assign_unique(_ForwardIterator __first, _ForwardIterator __last);
     template <class _InputIterator>
     _LIBCPP_HIDE_FROM_ABI void __assign_multi(_InputIterator __first, _InputIterator __last);
     _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t)
         _NOEXCEPT_(
             is_nothrow_move_constructible<__node_allocator>::value &&
             is_nothrow_move_constructible<value_compare>::value);
     _LIBCPP_HIDE_FROM_ABI __tree(__tree&& __t, const allocator_type& __a);
private:
       __tree *__t_;
       __node_pointer __cache_root_;
       __node_pointer __cache_elem_;
     };
 
 
     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
     template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
+    template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set;
+    template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;
 };
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp)
         _NOEXCEPT_(
             is_nothrow_default_constructible<__node_allocator>::value &&
             is_nothrow_copy_constructible<value_compare>::value)
     : __pair3_(0, __comp)
__tree<_Tp, _Compare, _Allocator>::_DetachedTreeCache::__detach_next(__node_pointer __cache) _NOEXCEPT
     __cache->__parent_unsafe()->__right_ = nullptr;
     __cache = static_cast<__node_pointer>(__cache->__parent_);
     if (__cache->__left_ == nullptr)
         return __cache;
     return static_cast<__node_pointer>(_VSTD::__tree_leaf(__cache->__left_));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
-__tree<_Tp, _Compare, _Allocator>&
-__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t)
-{
-    if (this != _VSTD::addressof(__t))
-    {
-        value_comp() = __t.value_comp();
-        __copy_assign_alloc(__t);
-        __assign_multi(__t.begin(), __t.end());
-    }
-    return *this;
-}
-
-template <class _Tp, class _Compare, class _Allocator>
 template <class _ForwardIterator>
 void
 __tree<_Tp, _Compare, _Allocator>::__assign_unique(_ForwardIterator __first, _ForwardIterator __last)
 {
     typedef iterator_traits<_ForwardIterator> _ITraits;
     typedef typename _ITraits::value_type _ItValueType;
     static_assert((is_same<_ItValueType, __container_value_type>::value),
                   "__assign_unique may only be called with the containers value type");
     static_assert(__is_cpp17_forward_iterator<_ForwardIterator>::value,
                   "__assign_unique requires a forward iterator");
     if (size() != 0)
     {
         _DetachedTreeCache __cache(this);
           for (; __cache.__get() != nullptr && __first != __last; ++__first) {
               if (__node_assign_unique(*__first, __cache.__get()).second)
                   __cache.__advance();
             }
     }
-    for (; __first != __last; ++__first)
-        __insert_unique(*__first);
+    for (const_iterator __e = end(); __first != __last; ++__first)
+        __insert_unique(__e, *__first);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 template <class _InputIterator>
 void
 __tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last)
 {
     typedef iterator_traits<_InputIterator> _ITraits;
     typedef typename _ITraits::value_type _ItValueType;
     static_assert((is_same<_ItValueType, __container_value_type>::value ||
                   is_same<_ItValueType, __node_value_type>::value),
                   "__assign_multi may only be called with the containers value type"
                   " or the nodes value type");
     if (size() != 0)
     {
         _DetachedTreeCache __cache(this);
         for (; __cache.__get() && __first != __last; ++__first) {
             __cache.__get()->__value_ = *__first;
             __node_insert_multi(__cache.__get());
             __cache.__advance();
         }
     }
-    for (; __first != __last; ++__first)
-        __insert_multi(_NodeTypes::__get_value(*__first));
+    for (const_iterator __e = end(); __first != __last; ++__first)
+        __insert_multi(__e, _NodeTypes::__get_value(*__first));
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 __tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t)
     : __begin_node_(__iter_pointer()),
       __pair1_(__default_init_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())),
       __pair3_(0, __t.value_comp())
 {

libcxx/include/map

 };
 
 template <class _Key, class _Tp, class _Compare, class _Allocator>
     class map;
 template <class _Key, class _Tp, class _Compare, class _Allocator>
     class multimap;
 template <class _TreeIterator> class __map_const_iterator;
 
-#ifndef _LIBCPP_CXX03_LANG
-
 template <class _Key, class _Tp>
 struct _LIBCPP_STANDALONE_DEBUG __value_type
 {
     typedef _Key                                     key_type;
     typedef _Tp                                      mapped_type;
     typedef pair<const key_type, mapped_type>        value_type;
     typedef pair<key_type&, mapped_type&>            __nc_ref_pair_type;
     typedef pair<key_type&&, mapped_type&&>          __nc_rref_pair_type;

 
 private:
     __value_type() = delete;
     ~__value_type() = delete;
     __value_type(const __value_type&) = delete;
     __value_type(__value_type&&) = delete;
 };
 
-#else
-
-template <class _Key, class _Tp>
-struct __value_type
-{
-    typedef _Key                                     key_type;
-    typedef _Tp                                      mapped_type;
-    typedef pair<const key_type, mapped_type>        value_type;
-
-private:
-    value_type __cc_;
-
-public:
-    _LIBCPP_INLINE_VISIBILITY
-    value_type& __get_value() { return __cc_; }
-    _LIBCPP_INLINE_VISIBILITY
-    const value_type& __get_value() const { return __cc_; }
-
-private:
-   __value_type();
-   __value_type(__value_type const&);
-   __value_type& operator=(__value_type const&);
-   ~__value_type();
-};
-
-#endif // _LIBCPP_CXX03_LANG
-
 template <class _Tp>
 struct __extract_key_value_types;
 
 template <class _Key, class _Tp>
 struct __extract_key_value_types<__value_type<_Key, _Tp> >
 {
   typedef _Key const __key_type;
   typedef _Tp        __mapped_type;
map(const map& __m)
         : __tree_(__m.__tree_)
         {
             insert(__m.begin(), __m.end());
         }
 
     _LIBCPP_INLINE_VISIBILITY
     map& operator=(const map& __m)
         {
-#ifndef _LIBCPP_CXX03_LANG
-            __tree_ = __m.__tree_;
-#else
             if (this != _VSTD::addressof(__m)) {
-                __tree_.clear();
                 __tree_.value_comp() = __m.__tree_.value_comp();
                 __tree_.__copy_assign_alloc(__m.__tree_);
-                insert(__m.begin(), __m.end());
+                __tree_.__assign_unique(__m.begin(), __m.end());
             }
-#endif
             return *this;
         }
 
 #ifndef _LIBCPP_CXX03_LANG
 
     _LIBCPP_INLINE_VISIBILITY
     map(map&& __m)
         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
multimap(const multimap& __m)
           __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
         {
             insert(__m.begin(), __m.end());
         }
 
     _LIBCPP_INLINE_VISIBILITY
     multimap& operator=(const multimap& __m)
         {
-#ifndef _LIBCPP_CXX03_LANG
-            __tree_ = __m.__tree_;
-#else
             if (this != _VSTD::addressof(__m)) {
-                __tree_.clear();
                 __tree_.value_comp() = __m.__tree_.value_comp();
                 __tree_.__copy_assign_alloc(__m.__tree_);
-                insert(__m.begin(), __m.end());
+                __tree_.__assign_multi(__m.begin(), __m.end());
             }
-#endif
             return *this;
         }
 
 #ifndef _LIBCPP_CXX03_LANG
 
     _LIBCPP_INLINE_VISIBILITY
     multimap(multimap&& __m)
         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)

libcxx/include/set

set(const set& __s)
         : __tree_(__s.__tree_)
         {
             insert(__s.begin(), __s.end());
         }
 
     _LIBCPP_INLINE_VISIBILITY
     set& operator=(const set& __s)
         {
-            __tree_ = __s.__tree_;
+            if (this != std::addressof(__s)) {
+                __tree_.value_comp() = __s.__tree_.value_comp();
+                __tree_.__copy_assign_alloc(__s.__tree_);
+                __tree_.__assign_unique(__s.begin(), __s.end());
+            }
             return *this;
         }
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     set(set&& __s)
         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
         : __tree_(_VSTD::move(__s.__tree_)) {}
multiset(const multiset& __s)
           __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
         {
             insert(__s.begin(), __s.end());
         }
 
     _LIBCPP_INLINE_VISIBILITY
     multiset& operator=(const multiset& __s)
         {
-            __tree_ = __s.__tree_;
+            if (this != std::addressof(__s)) {
+                __tree_.value_comp() = __s.__tree_.value_comp();
+                __tree_.__copy_assign_alloc(__s.__tree_);
+                __tree_.__assign_multi(__s.begin(), __s.end());
+            }
             return *this;
         }
 
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     multiset(multiset&& __s)
         _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
         : __tree_(_VSTD::move(__s.__tree_)) {}