diff --git a/libcxx/include/__hash_table b/libcxx/include/__hash_table --- a/libcxx/include/__hash_table +++ b/libcxx/include/__hash_table @@ -1017,7 +1017,6 @@ __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_( @@ -1386,6 +1385,8 @@ template friend class _LIBCPP_TEMPLATE_VIS unordered_map; template friend class _LIBCPP_TEMPLATE_VIS unordered_multimap; + template friend class _LIBCPP_TEMPLATE_VIS unordered_set; + template friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; }; template @@ -1534,21 +1535,6 @@ __node_alloc() = __u.__node_alloc(); } -template -__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 void __hash_table<_Tp, _Hash, _Equal, _Alloc>::__deallocate_node(__next_pointer __np) diff --git a/libcxx/include/unordered_map b/libcxx/include/unordered_map --- a/libcxx/include/unordered_map +++ b/libcxx/include/unordered_map @@ -1138,18 +1138,15 @@ _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 @@ -2030,18 +2027,15 @@ _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 diff --git a/libcxx/include/unordered_set b/libcxx/include/unordered_set --- a/libcxx/include/unordered_set +++ b/libcxx/include/unordered_set @@ -598,7 +598,15 @@ _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 @@ -1270,7 +1278,15 @@ _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 diff --git a/libcxx/test/libcxx/containers/unord/perf.assignment_vs_construction.pass.cpp b/libcxx/test/libcxx/containers/unord/perf.assignment_vs_construction.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/containers/unord/perf.assignment_vs_construction.pass.cpp @@ -0,0 +1,103 @@ +//===----------------------------------------------------------------------===// +// +// 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 +#include +#include +#include +#include +#include +#include +#include + +std::vector generate_keys(int N) { + auto generator = std::default_random_engine(12345); + + // Generate random keys to store in the container + std::vector 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 tmp(keys.begin(), keys.end()); + keys.assign(tmp.begin(), tmp.end()); + + std::shuffle(keys.begin(), keys.end(), generator); + return keys; +} + +template +std::size_t microseconds_avg(std::size_t iterations, F const& f) { + std::vector 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(stop - start).count(); + durations.push_back(duration); + } + + return std::accumulate(durations.begin(), durations.end(), 0) / iterations; +} + +template +void test_map(std::vector 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 +void test_set(std::vector 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 keys = generate_keys(1000000); + test_map>(keys); + test_map>(keys); + + test_set>(keys); + test_set>(keys); + return 0; +}