[libc++] Fix performance inconsistency between unordered_map copy-assignment and copy-construction

[ldionne]

Summary

We were not rehashing the hash table before performing assignment, which
resulted in greatly sub-optimal performance when compared to the
otherwise equivalent copy constructor.

This patch also adds a test that will start failing should a performance
difference be reintroduced in the future.

rdar://89335436

[Mordante]

Just curious can you share the before and after timings of this change?

libcxx/include/unordered_set

601

Please update the description/title to mention unordered_set and the multi versions.

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

10

This raises the same questions as this test for D121485.

libcxx/include/__hash_table

__hash_table(__hash_table&& __u)
             is_nothrow_move_constructible<__bucket_list>::value &&
             is_nothrow_move_constructible<__first_node>::value &&
             is_nothrow_move_constructible<__node_allocator>::value &&
             is_nothrow_move_constructible<hasher>::value &&
             is_nothrow_move_constructible<key_equal>::value);
     __hash_table(__hash_table&& __u, const allocator_type& __a);
     ~__hash_table();
 
-    __hash_table& operator=(const __hash_table& __u);
     _LIBCPP_INLINE_VISIBILITY
     __hash_table& operator=(__hash_table&& __u)
         _NOEXCEPT_(
             __node_traits::propagate_on_container_move_assignment::value &&
             is_nothrow_move_assignable<__node_allocator>::value &&
             is_nothrow_move_assignable<hasher>::value &&
             is_nothrow_move_assignable<key_equal>::value);
     template <class _InputIterator>
private:
     _LIBCPP_INLINE_VISIBILITY
         void __move_assign_alloc(__hash_table&, false_type) _NOEXCEPT {}
 
     void __deallocate_node(__next_pointer __np) _NOEXCEPT;
     __next_pointer __detach() _NOEXCEPT;
 
     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
+    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_set;
+    template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
 };
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 inline
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__hash_table()
     _NOEXCEPT_(
         is_nothrow_default_constructible<__bucket_list>::value &&
         is_nothrow_default_constructible<__first_node>::value &&
if (__node_alloc() != __u.__node_alloc())
         __bucket_list_.reset();
         __bucket_list_.get_deleter().size() = 0;
     }
     __bucket_list_.get_deleter().__alloc() = __u.__bucket_list_.get_deleter().__alloc();
     __node_alloc() = __u.__node_alloc();
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>&
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::operator=(const __hash_table& __u)
-{
-    if (this != _VSTD::addressof(__u))
-    {
-        __copy_assign_alloc(__u);
-        hash_function() = __u.hash_function();
-        key_eq() = __u.key_eq();
-        max_load_factor() = __u.max_load_factor();
-        __assign_multi(__u.begin(), __u.end());
-    }
-    return *this;
-}
-
-template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np)
     _NOEXCEPT
 {
     __node_allocator& __na = __node_alloc();
     while (__np != nullptr)
     {
         __next_pointer __next = __np->__next_;

libcxx/include/unordered_map

#endif
     _LIBCPP_INLINE_VISIBILITY
     ~unordered_map() {
         static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
     }
 
     _LIBCPP_INLINE_VISIBILITY
     unordered_map& operator=(const unordered_map& __u)
     {
-#ifndef _LIBCPP_CXX03_LANG
-        __table_ = __u.__table_;
-#else
         if (this != _VSTD::addressof(__u)) {
             __table_.clear();
             __table_.hash_function() = __u.__table_.hash_function();
             __table_.key_eq() = __u.__table_.key_eq();
             __table_.max_load_factor() = __u.__table_.max_load_factor();
             __table_.__copy_assign_alloc(__u.__table_);
+            __table_.rehash(__u.bucket_count());
             insert(__u.begin(), __u.end());
         }
-#endif
         return *this;
     }
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     unordered_map& operator=(unordered_map&& __u)
         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
     _LIBCPP_INLINE_VISIBILITY
     unordered_map& operator=(initializer_list<value_type> __il);
#endif
     _LIBCPP_INLINE_VISIBILITY
     ~unordered_multimap() {
         static_assert(sizeof(__diagnose_unordered_container_requirements<_Key, _Hash, _Pred>(0)), "");
     }
 
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap& operator=(const unordered_multimap& __u)
     {
-#ifndef _LIBCPP_CXX03_LANG
-        __table_ = __u.__table_;
-#else
         if (this != _VSTD::addressof(__u)) {
             __table_.clear();
             __table_.hash_function() = __u.__table_.hash_function();
             __table_.key_eq() = __u.__table_.key_eq();
             __table_.max_load_factor() = __u.__table_.max_load_factor();
             __table_.__copy_assign_alloc(__u.__table_);
+            __table_.rehash(__u.bucket_count());
             insert(__u.begin(), __u.end());
         }
-#endif
         return *this;
     }
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap& operator=(unordered_multimap&& __u)
         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap& operator=(initializer_list<value_type> __il);

libcxx/include/unordered_set

#endif // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     ~unordered_set() {
         static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
     }
 
     _LIBCPP_INLINE_VISIBILITY
     unordered_set& operator=(const unordered_set& __u)
     {
-        __table_ = __u.__table_;
+        if (this != _VSTD::addressof(__u)) {
+            __table_.clear();
+            __table_.hash_function() = __u.__table_.hash_function();
+            __table_.key_eq() = __u.__table_.key_eq();
+            __table_.max_load_factor() = __u.__table_.max_load_factor();
+            __table_.__copy_assign_alloc(__u.__table_);
+            __table_.rehash(__u.bucket_count());
+            insert(__u.begin(), __u.end());
+        }
         return *this;
     }
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     unordered_set& operator=(unordered_set&& __u)
         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
     _LIBCPP_INLINE_VISIBILITY
     unordered_set& operator=(initializer_list<value_type> __il);
#endif // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     ~unordered_multiset() {
         static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
     }
 
     _LIBCPP_INLINE_VISIBILITY
     unordered_multiset& operator=(const unordered_multiset& __u)
     {
-        __table_ = __u.__table_;
+        if (this != _VSTD::addressof(__u)) {
+            __table_.clear();
+            __table_.hash_function() = __u.__table_.hash_function();
+            __table_.key_eq() = __u.__table_.key_eq();
+            __table_.max_load_factor() = __u.__table_.max_load_factor();
+            __table_.__copy_assign_alloc(__u.__table_);
+            __table_.rehash(__u.bucket_count());
+            insert(__u.begin(), __u.end());
+        }
         return *this;
     }
 #ifndef _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     unordered_multiset& operator=(unordered_multiset&& __u)
         _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
     unordered_multiset& operator=(initializer_list<value_type> __il);
 #endif // _LIBCPP_CXX03_LANG

libcxx/test/libcxx/containers/unord/perf.assignment_vs_construction.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
+//
+//===----------------------------------------------------------------------===//
+
+// This test ensures that copy assignment and copy construction are within a reasonable
+// margin from each other performance wise.
+
+#include <algorithm>
+#include <cassert>
+#include <chrono>
+#include <cstddef>
+#include <random>
+#include <string>
+#include <unordered_map>
+#include <unordered_set>
+
+std::vector<std::string> generate_keys(int N) {
+    auto generator = std::default_random_engine(12345);
+
+    // Generate random keys to store in the container
+    std::vector<std::string> keys;
+    for (int i = 0; i != N; ++i) {
+        auto key = std::to_string(generator());
+        keys.push_back(key);
+    }
+
+    // Make sure all the strings are unique
+    std::unordered_set<std::string> tmp(keys.begin(), keys.end());
+    keys.assign(tmp.begin(), tmp.end());
+
+    std::shuffle(keys.begin(), keys.end(), generator);
+    return keys;
+}
+
+template <typename F>
+std::size_t microseconds_avg(std::size_t iterations, F const& f) {
+    std::vector<std::size_t> durations;
+    for (size_t i = 0; i < iterations; ++i) {
+        const auto start = std::chrono::high_resolution_clock::now();
+        f();
+        const auto stop = std::chrono::high_resolution_clock::now();
+        const auto duration = std::chrono::duration_cast<std::chrono::microseconds>(stop - start).count();
+        durations.push_back(duration);
+    }
+
+    return std::accumulate(durations.begin(), durations.end(), 0) / iterations;
+}
+
+template <typename Container>
+void test_map(std::vector<std::string> const& keys) {
+    constexpr std::size_t iterations = 5;
+
+    Container tmp;
+    for (const auto& key : keys)
+        tmp.insert({key, 1});
+
+    std::size_t ctor_avg = microseconds_avg(iterations, [&] {
+        Container foo(tmp);
+    });
+
+    std::size_t assignment_avg = microseconds_avg(iterations, [&] {
+        Container foo;
+        foo = tmp;
+    });
+
+    auto percentage = (std::labs((ssize_t)ctor_avg - (ssize_t)assignment_avg) / (double)ctor_avg) * 100.0;
+    assert(percentage < 10.0 && "Copy assignment and copy constructor have more than 10% difference");
+}
+
+template <typename Container>
+void test_set(std::vector<std::string> const& keys) {
+    constexpr std::size_t iterations = 5;
+
+    Container tmp;
+    for (const auto& key : keys)
+        tmp.insert(key);
+
+    std::size_t ctor_avg = microseconds_avg(iterations, [&] {
+        Container foo(tmp);
+    });
+
+    std::size_t assignment_avg = microseconds_avg(iterations, [&] {
+        Container foo;
+        foo = tmp;
+    });
+
+    auto percentage = (std::labs((ssize_t)ctor_avg - (ssize_t)assignment_avg) / (double)ctor_avg) * 100.0;
+    assert(percentage < 10.0 && "Copy assignment and copy constructor have more than 10% difference");
+}
+
+int main(int, char const**) {
+    std::vector<std::string> keys = generate_keys(1000000);
+    test_map<std::unordered_map<std::string, int>>(keys);
+    test_map<std::unordered_multimap<std::string, int>>(keys);
+
+    test_set<std::unordered_set<std::string>>(keys);
+    test_set<std::unordered_multiset<std::string>>(keys);
+    return 0;
+}