* [PATCH 3/5][_Hashtable] Avoid redundant usage of rehash policy
@ 2023-11-23 21:58 François Dumont
2023-12-21 22:17 ` Jonathan Wakely
0 siblings, 1 reply; 3+ messages in thread
From: François Dumont @ 2023-11-23 21:58 UTC (permalink / raw)
To: libstdc++; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1001 bytes --]
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
[-- Attachment #2: hashtable_redundancies.txt --]
[-- Type: text/plain, Size: 5226 bytes --]
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);
}
/**
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH 3/5][_Hashtable] Avoid redundant usage of rehash policy
2023-11-23 21:58 [PATCH 3/5][_Hashtable] Avoid redundant usage of rehash policy François Dumont
@ 2023-12-21 22:17 ` Jonathan Wakely
2024-01-04 5:50 ` François Dumont
0 siblings, 1 reply; 3+ messages in thread
From: Jonathan Wakely @ 2023-12-21 22:17 UTC (permalink / raw)
To: François Dumont; +Cc: libstdc++, gcc-patches
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH 3/5][_Hashtable] Avoid redundant usage of rehash policy
2023-12-21 22:17 ` Jonathan Wakely
@ 2024-01-04 5:50 ` François Dumont
0 siblings, 0 replies; 3+ messages in thread
From: François Dumont @ 2024-01-04 5:50 UTC (permalink / raw)
To: Jonathan Wakely; +Cc: libstdc++, gcc-patches
[-- Attachment #1: Type: text/plain, Size: 2359 bytes --]
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
[-- Attachment #2: hashtable_redundancies.txt --]
[-- Type: text/plain, Size: 5471 bytes --]
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);
}
/**
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2024-01-04 5:50 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-11-23 21:58 [PATCH 3/5][_Hashtable] Avoid redundant usage of rehash policy François Dumont
2023-12-21 22:17 ` Jonathan Wakely
2024-01-04 5:50 ` François Dumont
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).