public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
From: "François Dumont" <frs.dumont@gmail.com>
To: libstdc++ <libstdc++@gcc.gnu.org>
Cc: gcc-patches <gcc-patches@gcc.gnu.org>
Subject: [PATCH][_Hashtable] Avoid redundant usage of rehash policy
Date: Sun, 17 Sep 2023 22:41:13 +0200	[thread overview]
Message-ID: <8046050f-c7e7-e41a-caf6-ddf087719597@gmail.com> (raw)

[-- Attachment #1: Type: text/plain, Size: 827 bytes --]

libstdc++: [_Hashtable] Avoid redundant usage of rehash policy

Bypass usage of __detail::__distance_fwd and check for need to rehash 
when assigning an initializer_list to
an unordered_multimap or unordered_multiset.

libstdc++-v3/ChangeLog:

     * include/bits/hashtable_policy.h
     (_Insert_base<>::_M_insert_range(_InputIte, _InputIte, _NodeGen&)): 
New.
     (_Insert_base<>::_M_insert_range(_InputIte, _InputIte, true_type)): 
Use latter.
     (_Insert_base<>::_M_insert_range(_InputIte, _InputIte, 
false_type)): Likewise.
     * include/bits/hashtable.h
(_Hashtable<>::operator=(initializer_list<value_type>)): Likewise.
     (_Hashtable<>::_Hashtable(_InputIte, _InputIte, size_type, const 
_Hash&, const _Equal&,
     const allocator_type&, false_type)): Likewise.

Ok to commit ?

François


[-- Attachment #2: hashtable.patch --]
[-- Type: text/x-patch, Size: 4367 bytes --]

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 4c12dc895b2..c544094847d 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -614,7 +614,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	if (_M_bucket_count < __l_bkt_count)
 	  rehash(__l_bkt_count);
 
-	this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
+	this->_M_insert_range(__l.begin(), __l.end(), __roan);
 	return *this;
       }
 
@@ -1254,8 +1254,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  }
 
 	__alloc_node_gen_t __node_gen(*this);
-	for (; __f != __l; ++__f)
-	  _M_insert(*__f, __node_gen, __uks);
+	this->_M_insert_range(__f, __l, __node_gen);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 347d468ea86..ab931d42e2d 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -902,12 +902,17 @@ namespace __detail
       template<typename _InputIterator, typename _NodeGetter>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, true_type __uks);
+			const _NodeGetter&);
 
-      template<typename _InputIterator, typename _NodeGetter>
+      template<typename _InputIterator>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			const _NodeGetter&, false_type __uks);
+			true_type __uks);
+
+      template<typename _InputIterator>
+	void
+	_M_insert_range(_InputIterator __first, _InputIterator __last,
+			false_type __uks);
 
     public:
       using iterator = _Node_iterator<_Value, __constant_iterators::value,
@@ -966,11 +971,7 @@ namespace __detail
       template<typename _InputIterator>
 	void
 	insert(_InputIterator __first, _InputIterator __last)
-	{
-	  __hashtable& __h = _M_conjure_hashtable();
-	  __node_gen_type __node_gen(__h);
-	  return _M_insert_range(__first, __last, __node_gen, __unique_keys{});
-	}
+	{ _M_insert_range(__first, __last, __unique_keys{}); }
     };
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -983,24 +984,41 @@ namespace __detail
 		   _Hash, _RangeHash, _Unused,
 		   _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, true_type __uks)
+		      const _NodeGetter& __node_gen)
       {
 	__hashtable& __h = _M_conjure_hashtable();
 	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __uks);
+	  __h._M_insert(*__first, __node_gen, __unique_keys{});
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
 	   typename _RehashPolicy, typename _Traits>
-    template<typename _InputIterator, typename _NodeGetter>
+    template<typename _InputIterator>
+      void
+      _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		   _Hash, _RangeHash, _Unused,
+		   _RehashPolicy, _Traits>::
+      _M_insert_range(_InputIterator __first, _InputIterator __last,
+		      true_type /* __uks */)
+      {
+	__hashtable& __h = _M_conjure_hashtable();
+	__node_gen_type __node_gen(__h);
+	_M_insert_range(__first, __last, __node_gen);
+      }
+
+  template<typename _Key, typename _Value, typename _Alloc,
+	   typename _ExtractKey, typename _Equal,
+	   typename _Hash, typename _RangeHash, typename _Unused,
+	   typename _RehashPolicy, typename _Traits>
+    template<typename _InputIterator>
       void
       _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
 		   _Hash, _RangeHash, _Unused,
 		   _RehashPolicy, _Traits>::
       _M_insert_range(_InputIterator __first, _InputIterator __last,
-		      const _NodeGetter& __node_gen, false_type __uks)
+		      false_type /* __uks */)
       {
 	using __rehash_type = typename __hashtable::__rehash_type;
 	using __rehash_state = typename __hashtable::__rehash_state;
@@ -1020,8 +1038,8 @@ namespace __detail
 	if (__do_rehash.first)
 	  __h._M_rehash(__do_rehash.second, __saved_state);
 
-	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __uks);
+	__node_gen_type __node_gen(__h);
+	_M_insert_range(__first, __last, __node_gen);
       }
 
   /**

             reply	other threads:[~2023-09-17 20:41 UTC|newest]

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-09-17 20:41 François Dumont [this message]
2023-10-12 17:02 ` François Dumont

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=8046050f-c7e7-e41a-caf6-ddf087719597@gmail.com \
    --to=frs.dumont@gmail.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=libstdc++@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).