diff mbox series

[3/5,_Hashtable] Avoid redundant usage of rehash policy

Message ID 7d985892-3188-4b35-8f3f-1a3a12e09012@gmail.com
State New
Headers show
Series Optimize insertions | expand

Commit Message

François Dumont Nov. 23, 2023, 9:58 p.m. UTC 
libstdc++: [_Hashtable] Avoid redundant usage of rehash policy

     Bypass call to __detail::__distance_fwd and the check if rehash is 
needed when
     assigning an initializer_list to an unordered_multimap or 
unordered_multiset.

     libstdc++-v3/ChangeLog:

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

Tested under Linux x64

Ok to commit ?

François

Comments

Jonathan Wakely Dec. 21, 2023, 10:17 p.m. UTC | #1 
On Thu, 23 Nov 2023 at 21:59, François Dumont <frs.dumont@gmail.com> wrote:
>
>      libstdc++: [_Hashtable] Avoid redundant usage of rehash policy
>
>      Bypass call to __detail::__distance_fwd and the check if rehash is
> needed when
>      assigning an initializer_list to an unordered_multimap or
> unordered_multiset.

I find this patch and the description a bit confusing. It would help
if the new _Hashtable::_M_insert_range function had a comment (or a
different name!) explaining how it's different from the existing
_Insert_base::_M_insert_range functions.


>
>      libstdc++-v3/ChangeLog:
>
>              * include/bits/hashtable.h
>              (_Hashtable<>::_M_insert_range(_InputIte, _InputIte,
> _NodeGen&)): New.
> (_Hashtable<>::operator=(initializer_list<value_type>)): Use latter.
>              (_Hashtable<>::_Hashtable(_InputIte, _InputIte, size_type,
> const _Hash&, const _Equal&,
>              const allocator_type&, false_type)): Use latter.
>              * include/bits/hashtable_policy.h
>              (_Insert_base<>::_M_insert_range(_InputIte, _InputIte,
> true_type)): Use latter.
>              (_Insert_base<>::_M_insert_range(_InputIte, _InputIte,
> false_type)): Likewise.
>
> Tested under Linux x64
>
> Ok to commit ?
>
> François
François Dumont Jan. 4, 2024, 5:50 a.m. UTC | #2 
Here is an updated version.

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

     Bypass call to __detail::__distance_fwd and the check if rehash is 
needed when
     instantiating from an iterator range or assigning an 
initializer_list to an
     unordered_multimap or unordered_multiset.

     libstdc++-v3/ChangeLog:

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

Ok to commit ?

François


On 21/12/2023 23:17, Jonathan Wakely wrote:
> On Thu, 23 Nov 2023 at 21:59, François Dumont <frs.dumont@gmail.com> wrote:
>>       libstdc++: [_Hashtable] Avoid redundant usage of rehash policy
>>
>>       Bypass call to __detail::__distance_fwd and the check if rehash is
>> needed when
>>       assigning an initializer_list to an unordered_multimap or
>> unordered_multiset.
> I find this patch and the description a bit confusing. It would help
> if the new _Hashtable::_M_insert_range function had a comment (or a
> different name!) explaining how it's different from the existing
> _Insert_base::_M_insert_range functions.
>
>
>>       libstdc++-v3/ChangeLog:
>>
>>               * include/bits/hashtable.h
>>               (_Hashtable<>::_M_insert_range(_InputIte, _InputIte,
>> _NodeGen&)): New.
>> (_Hashtable<>::operator=(initializer_list<value_type>)): Use latter.
>>               (_Hashtable<>::_Hashtable(_InputIte, _InputIte, size_type,
>> const _Hash&, const _Equal&,
>>               const allocator_type&, false_type)): Use latter.
>>               * include/bits/hashtable_policy.h
>>               (_Insert_base<>::_M_insert_range(_InputIte, _InputIte,
>> true_type)): Use latter.
>>               (_Insert_base<>::_M_insert_range(_InputIte, _InputIte,
>> false_type)): Likewise.
>>
>> Tested under Linux x64
>>
>> Ok to commit ?
>>
>> François
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index adf77f25d41..aec77c34a58 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -616,7 +616,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{});
+	_M_insert_range(__l.begin(), __l.end(), __roan);
 	return *this;
       }
 
@@ -989,6 +989,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(const_iterator, _Arg&&,
 		  _NodeGenerator&, false_type __uks);
 
+      template<typename _InputIterator, typename _NodeGenerator>
+	void
+	_M_insert_range(_InputIterator __first, _InputIterator __last,
+			_NodeGenerator&);
+
       size_type
       _M_erase(true_type __uks, const key_type&);
 
@@ -1304,8 +1309,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  }
 
 	__alloc_node_gen_t __node_gen(*this);
-	for (; __f != __l; ++__f)
-	  _M_insert(*__f, __node_gen, __uks);
+	_M_insert_range(__f, __l, __node_gen);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -2375,6 +2379,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __pos;
       }
 
+  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 _NodeGenerator>
+      void
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_insert_range(_InputIterator __first, _InputIterator __last,
+		      _NodeGenerator& __node_gen)
+      {
+	for (; __first != __last; ++__first)
+	  _M_insert(*__first, __node_gen, __unique_keys{});
+      }
+
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 2a59db75036..64dcdc466b8 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -932,15 +932,16 @@ namespace __detail
       _M_conjure_hashtable()
       { return *(static_cast<__hashtable*>(this)); }
 
-      template<typename _InputIterator, typename _NodeGetter>
+    private:
+      template<typename _InputIterator>
 	void
-	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			_NodeGetter&, true_type __uks);
+	_M_insert(_InputIterator __first, _InputIterator __last,
+		  true_type __uks);
 
-      template<typename _InputIterator, typename _NodeGetter>
+      template<typename _InputIterator>
 	void
-	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			_NodeGetter&, false_type __uks);
+	_M_insert(_InputIterator __first, _InputIterator __last,
+		  false_type __uks);
 
     public:
       using iterator = _Node_iterator<_Value, __constant_iterators::value,
@@ -999,41 +1000,37 @@ 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(__first, __last, __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,
-		      _NodeGetter& __node_gen, true_type __uks)
+      _M_insert(_InputIterator __first, _InputIterator __last,
+		true_type /* __uks */)
       {
 	__hashtable& __h = _M_conjure_hashtable();
-	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __uks);
+	__node_gen_type __node_gen(__h);
+	__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, 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,
-		      _NodeGetter& __node_gen, false_type __uks)
+      _M_insert(_InputIterator __first, _InputIterator __last,
+		false_type __uks)
       {
 	using __rehash_guard_t = typename __hashtable::__rehash_guard_t;
 	using __pair_type = std::pair<bool, std::size_t>;
@@ -1053,8 +1050,8 @@ namespace __detail
 	  __h._M_rehash(__do_rehash.second, __uks);
 
 	__rehash_guard._M_guarded_obj = nullptr;
-	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __uks);
+	__node_gen_type __node_gen(__h);
+	__h._M_insert_range(__first, __last, __node_gen);
       }
 
   /**
diff mbox series

Patch

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 8329d32e68e..771ed9968f7 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -612,7 +612,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{});
+	_M_insert_range(__l.begin(), __l.end(), __roan);
 	return *this;
       }
 
@@ -985,6 +985,11 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	_M_insert(const_iterator, _Arg&&,
 		  _NodeGenerator&, false_type __uks);
 
+      template<typename _InputIterator, typename _NodeGenerator>
+	void
+	_M_insert_range(_InputIterator __first, _InputIterator __last,
+			_NodeGenerator&);
+
       size_type
       _M_erase(true_type __uks, const key_type&);
 
@@ -1263,8 +1268,7 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	  }
 
 	__alloc_node_gen_t __node_gen(*this);
-	for (; __f != __l; ++__f)
-	  _M_insert(*__f, __node_gen, __uks);
+	_M_insert_range(__f, __l, __node_gen);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
@@ -2278,6 +2282,21 @@  _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	return __pos;
       }
 
+  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 _NodeGenerator>
+      void
+      _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
+		 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
+      _M_insert_range(_InputIterator __first, _InputIterator __last,
+		      _NodeGenerator& __node_gen)
+      {
+	for (; __first != __last; ++__first)
+	  _M_insert(*__first, __node_gen, __unique_keys{});
+      }
+
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
 	   typename _Hash, typename _RangeHash, typename _Unused,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 5c40be2cb72..9f775522cff 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -930,15 +930,15 @@  namespace __detail
       _M_conjure_hashtable()
       { return *(static_cast<__hashtable*>(this)); }
 
-      template<typename _InputIterator, typename _NodeGetter>
+      template<typename _InputIterator>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			_NodeGetter&, true_type __uks);
+			true_type __uks);
 
-      template<typename _InputIterator, typename _NodeGetter>
+      template<typename _InputIterator>
 	void
 	_M_insert_range(_InputIterator __first, _InputIterator __last,
-			_NodeGetter&, false_type __uks);
+			false_type __uks);
 
     public:
       using iterator = _Node_iterator<_Value, __constant_iterators::value,
@@ -997,41 +997,37 @@  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,
 	   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,
-		      _NodeGetter& __node_gen, true_type __uks)
+		      true_type /* __uks */)
       {
 	__hashtable& __h = _M_conjure_hashtable();
-	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __uks);
+	__node_gen_type __node_gen(__h);
+	__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, 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,
-		      _NodeGetter& __node_gen, false_type __uks)
+		      false_type __uks)
       {
 	using __rehash_guard_t = typename __hashtable::__rehash_guard_t;
 	using __pair_type = std::pair<bool, std::size_t>;
@@ -1051,8 +1047,8 @@  namespace __detail
 	  __h._M_rehash(__do_rehash.second, __uks);
 
 	__rehash_guard._M_guarded_obj = nullptr;
-	for (; __first != __last; ++__first)
-	  __h._M_insert(*__first, __node_gen, __uks);
+	__node_gen_type __node_gen(__h);
+	__h._M_insert_range(__first, __last, __node_gen);
       }
 
   /**