Message ID | 7d985892-3188-4b35-8f3f-1a3a12e09012@gmail.com |
---|---|
State | New |
Headers | show |
Series | Optimize insertions | expand |
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
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 --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); } /**