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.dum...@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);
}
/**
