public inbox for libstdc++-cvs@sourceware.org
help / color / mirror / Atom feed
From: "Franथईois Dumont" <fdumont@gcc.gnu.org>
To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org
Subject: [gcc r12-5277] libstdc++: Unordered containers merge re-use hash code
Date: Mon, 15 Nov 2021 17:55:35 +0000 (GMT) [thread overview]
Message-ID: <20211115175535.7F28D3858405@sourceware.org> (raw)
https://gcc.gnu.org/g:d10b863fa3de8b202aadbdef1b012188ab0868d8
commit r12-5277-gd10b863fa3de8b202aadbdef1b012188ab0868d8
Author: François Dumont <fdumont@gcc.gnu.org>
Date: Mon Oct 25 15:59:35 2021 +0200
libstdc++: Unordered containers merge re-use hash code
When merging 2 unordered containers with same hasher we can re-use the hash code from
the cache if any.
Also in the context of the merge operation on multi-container use previous insert iterator as a hint
for the next insert.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h:
(_Hash_code_base<>::_M_hash_code(const _Hash&, const _Hash_node_value<_Value, true>&)): New.
(_Hash_code_base<>::_M_hash_code<_H2>(const _H2&, const _Hash_node_value<>&)): New.
* include/bits/hashtable.h (_Hashtable<>::_M_merge_unique): Use latter.
(_Hashtable<>::_M_merge_multi): Likewise.
* testsuite/23_containers/unordered_multiset/modifiers/merge.cc (test05): New test.
* testsuite/23_containers/unordered_set/modifiers/merge.cc (test04): New test.
Diff:
---
libstdc++-v3/include/bits/hashtable.h | 10 +++--
libstdc++-v3/include/bits/hashtable_policy.h | 13 +++++++
.../unordered_multiset/modifiers/merge.cc | 22 +++++++++++
.../23_containers/unordered_set/modifiers/merge.cc | 43 ++++++++++++++++++++++
4 files changed, 84 insertions(+), 4 deletions(-)
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 0e949d73614..6e2d4c10cfe 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -1076,7 +1076,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __pos = __i++;
const key_type& __k = _ExtractKey{}(*__pos);
- __hash_code __code = this->_M_hash_code(__k);
+ __hash_code __code
+ = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
size_type __bkt = _M_bucket_index(__code);
if (_M_find_node(__bkt, __k, __code) == nullptr)
{
@@ -1099,14 +1100,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
node_type>, "Node types are compatible");
__glibcxx_assert(get_allocator() == __src.get_allocator());
+ __node_ptr __hint = nullptr;
this->reserve(size() + __src.size());
for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
{
auto __pos = __i++;
- const key_type& __k = _ExtractKey{}(*__pos);
- __hash_code __code = this->_M_hash_code(__k);
+ __hash_code __code
+ = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
auto __nh = __src.extract(__pos);
- _M_insert_multi_node(nullptr, __code, __nh._M_ptr);
+ __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
__nh._M_ptr = nullptr;
}
}
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index c0295b75963..0b5443fc187 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1250,6 +1250,19 @@ namespace __detail
return _M_hash()(__k);
}
+ __hash_code
+ _M_hash_code(const _Hash&,
+ const _Hash_node_value<_Value, true>& __n) const
+ { return __n._M_hash_code; }
+
+ // Compute hash code using _Hash as __n _M_hash_code, if present, was
+ // computed using _H2.
+ template<typename _H2>
+ __hash_code
+ _M_hash_code(const _H2&,
+ const _Hash_node_value<_Value, __cache_hash_code>& __n) const
+ { return _M_hash_code(_ExtractKey{}(__n._M_v())); }
+
std::size_t
_M_bucket_index(__hash_code __c, std::size_t __bkt_count) const
{ return _RangeHash{}(__c, __bkt_count); }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc
index 1ed2ce234a1..07b8a344169 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/merge.cc
@@ -17,6 +17,7 @@
// { dg-do run { target c++17 } }
+#include <string>
#include <unordered_set>
#include <algorithm>
#include <testsuite_hooks.h>
@@ -105,6 +106,26 @@ test04()
VERIFY( c2.empty() );
}
+void
+test05()
+{
+ const std::unordered_multiset<std::string> c0{ "abcd", "abcd", "efgh", "efgh", "ijkl", "ijkl" };
+ std::unordered_multiset<std::string> c1 = c0;
+ std::unordered_set<std::string> c2( c0.begin(), c0.end() );
+
+ c1.merge(c2);
+ VERIFY( c1.size() == (1.5 * c0.size()) );
+ for (auto& i : c1)
+ VERIFY( c1.count(i) == (1.5 * c0.count(i)) );
+ VERIFY( c2.empty() );
+
+ c1.clear();
+ c2.insert( c0.begin(), c0.end() );
+ c1.merge(std::move(c2));
+ VERIFY( c1.size() == (0.5 * c0.size()) );
+ VERIFY( c2.empty() );
+}
+
int
main()
{
@@ -112,4 +133,5 @@ main()
test02();
test03();
test04();
+ test05();
}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc
index c9c8a60fd54..0e184b10c60 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/merge.cc
@@ -17,6 +17,7 @@
// { dg-do run { target c++17 } }
+#include <string>
#include <unordered_set>
#include <algorithm>
#include <testsuite_hooks.h>
@@ -125,10 +126,52 @@ test03()
VERIFY( c2.empty() );
}
+void
+test04()
+{
+ const std::unordered_set<std::string> c0{ "abcd", "efgh", "ijkl", };
+ std::unordered_set<std::string> c1 = c0;
+ std::unordered_multiset<std::string> c2( c0.begin(), c0.end() );
+ c1.merge(c2);
+ VERIFY( c1 == c0 );
+ VERIFY( equal_elements(c2, c0) );
+
+ c1.clear();
+ c1.merge(c2);
+ VERIFY( c1 == c0 );
+ VERIFY( c2.empty() );
+
+ c2.merge(c1);
+ VERIFY( c1.empty() );
+ VERIFY( equal_elements(c2, c0) );
+
+ c1 = c0;
+ c2.merge(c1);
+ VERIFY( c1.empty() );
+ VERIFY( c2.size() == (2 * c0.size()) );
+ VERIFY( c2.count("abcd") == 2 );
+ VERIFY( c2.count("efgh") == 2 );
+ VERIFY( c2.count("ijkl") == 2 );
+
+ c1.merge(c2);
+ VERIFY( c1 == c0 );
+ VERIFY( equal_elements(c2, c0) );
+
+ c1.merge(std::move(c2));
+ VERIFY( c1 == c0 );
+ VERIFY( equal_elements(c2, c0) );
+
+ c1.clear();
+ c1.merge(std::move(c2));
+ VERIFY( c1 == c0 );
+ VERIFY( c2.empty() );
+}
+
int
main()
{
test01();
test02();
test03();
+ test04();
}
reply other threads:[~2021-11-15 17:55 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20211115175535.7F28D3858405@sourceware.org \
--to=fdumont@gcc.gnu.org \
--cc=gcc-cvs@gcc.gnu.org \
--cc=libstdc++-cvs@gcc.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).