[PATCH] Hashtable PR96088
François Dumont
frs.dumont@gmail.com
Sat May 22 16:35:16 GMT 2021
This was indeed the right approach.
The only minor drawback is that __is_noexcept_invocable<> combines
noexcept qualification of the conversion and of the hash functor. So if
the hash functor is not noexcept we could end up creating temporaries
for nothing.
So I've eventually used this condition:
__and_<__is_nothrow_invocable<_Hash&, const key_type&>,
__not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
so that we do not create a temporary key_type if invoking _Hash
with it can still throw.
libstdc++: Limit allocation on iterator insertion in Hashtable [PR
96088]
When inserting into unordered_multiset or unordered_multimap first
instantiate
the node to store and compute the hash code from it to avoid a
potential
intermediate key_type instantiation.
When inserting into unordered_set or unordered_map check if
invoking the hash
functor with container key_type is noexcept and invoking the same
hash functor
with key part of the iterator value_type can throw. In this case
create a
temporary key_type instance at Hashtable level and use it to
compute the hash
code. This temporary instance is moved to the final storage
location if needed.
libstdc++-v3/ChangeLog:
PR libstdc++/96088
* include/bits/hashtable_policy.h (_Select2nd): New.
(_NodeBuilder<>): New.
(_ReuseOrAllocNode<>::operator()): Use variadic template args.
(_AllocNode<>::operator()): Likewise.
* include/bits/hashtable.h
(_Hashtable<>::__node_builder_t): New.
(_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)):
New.
(_Hashtable<>::_S_forward_key): New.
(_Hashtable<>::_M_insert): Use latter.
(_Hashtable<>::_M_insert(const_iterator, _Arg&&, const
_NodeGenerator&, false_type)):
Instantiate node first, compute hash code second.
* testsuite/23_containers/unordered_map/96088.cc: New test.
* testsuite/23_containers/unordered_multimap/96088.cc: New
test.
* testsuite/23_containers/unordered_multiset/96088.cc: New
test.
* testsuite/23_containers/unordered_set/96088.cc: New test.
* testsuite/util/replacement_memory_operators.h
(counter::_M_increment): New.
(counter::_M_decrement): New.
(counter::reset()): New.
Tested under Linux x64.
Ok to commit ?
François
On 21/05/21 8:55 am, Jonathan Wakely wrote:
>
>
> On Fri, 21 May 2021, 07:48 Jonathan Wakely, <jwakely.gcc@gmail.com
> <mailto:jwakely.gcc@gmail.com>> wrote:
>
>
>
> On Fri, 21 May 2021, 07:31 François Dumont via Libstdc++,
> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@gcc.gnu.org>> wrote:
>
> On 20/05/21 6:44 pm, Jonathan Wakely wrote:
> > On 06/05/21 22:03 +0200, François Dumont via Libstdc++ wrote:
> >> Hi
> >>
> >> Considering your feedback on backtrace in debug mode is
> going to
> >> take me some time so here is another one.
> >>
> >> Compared to latest submission I've added a _Hash_arg_t
> partial
> >> specialization for std::hash<>. It is not strictly
> necessary for the
> >> moment but when we will eventually remove its nested
> argument_type it
> >> will be. I also wonder if it is not easier to handle for the
> >> compiler, not sure about that thought.
> >
> > The std::hash specializations in libstdc++ define
> argument_type, but
> > I'm already working on one that doesn't (forstd::stacktrace).
> >
> > And std::hash<acme::ProgramDefinedType> can be specialized
> by users,
> > and is not required to provide argument_type.
> >
> > So it's already not valid to assume that
> std::hash<T>::argument_type
> > exists.
>
> Yes, I know that the plan is to get rid of argument_type. But
> as long as
> it is there we can still use it even if I didn't realize that
> you were
> already in the process of removing it so soon.
>
>
> I'm adding a new specialization for a C++23 type, and not adding
> the nested types.
>
>
>
>
> >
> >> @@ -850,9 +852,56 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> iterator
> >> _M_emplace(const_iterator, false_type __uks, _Args&&...
> __args);
> >>
> >> + template<typename _Kt, typename _Arg, typename
> _NodeGenerator>
> >> + std::pair<iterator, bool>
> >> + _M_insert_unique(_Kt&&, _Arg&&, const _NodeGenerator&);
> >> +
> >> + // Detect nested argument_type.
> >> + template<typename _Kt, typename _Ht, typename =
> __void_t<>>
> >> + struct _Hash_arg_t
> >> + { typedef _Kt argument_type; };
> >> +
> >> + // std::hash
> >> + template<typename _Kt, typename _Arg>
> >> + struct _Hash_arg_t<_Kt, std::hash<_Arg>>
> >> + { typedef _Arg argument_type; };
> >> +
> >> + // Nested argument_type.
> >> + template<typename _Kt, typename _Ht>
> >> + struct _Hash_arg_t<_Kt, _Ht,
> >> + __void_t<typename _Ht::argument_type>>
> >> + { typedef typename _Ht::argument_type argument_type; };
> >> +
> >> + // Function pointer.
> >> + template<typename _Kt, typename _Arg>
> >> + struct _Hash_arg_t<_Kt, std::size_t(*)(const _Arg&)>
> >> + { typedef _Arg argument_type; };
> >> +
> >> + template<typename _Kt,
> >> + typename _ArgType
> >> + = typename _Hash_arg_t<_Kt, _Hash>::argument_type>
> >> + static typename conditional<
> >> + __is_nothrow_convertible<_Kt, _ArgType>::value, _Kt&&,
> >> key_type>::type
> >
> > Please use __conditional_t<...> here instead of
> > typename conditional<...>::type.
> >
> > The purpose of the _Hash_arg_t type is to determine whether
> invoking
> > the hash function with _Kt&& can throw, right?
>
> No, the purpose of _Hash_arg_t is to find out what is the
> argument type
> of the _Hash functor. With this info I can check if invoking that
> functor is going to instantiate a temporary using a throwing
> operation.
>
>
> Right, that's what I mean.
>
>
> If so, I create a temporary at _Hashtable code level and move
> it to its
> final storage place when needed.
>
> The tricky part is that _Hash can accept different argument
> types, for
> the moment I just do not create a temporary in this case.
>
> >
> > And if it can throw, you force a conversion early, and if it
> can't,
> > you don't do the conversion.
> >
> > Can't you use __is_nothrow_invocable<_Hash&, _Kt> for that,
> instead of
> > this fragile approach?
> >
> I think I already try but I'll check.
>
> I fear that __is_nothrow_invocable<_Hash&, _Kt> tells if the
> chosen
> operator()(const _Arg&) is noexcept qualified.
>
>
> No.
>
> Not if the conversion
> from _Kt to _Arg is noexcept.
>
>
>
> It does exactly what you need.
>
>
> And even if it didn't, you could do it yourself with the noexcept
> operator:
>
> noexcept(std::declval<_Hash&>()(std::declval<_Kt>()));
>
>
> This is what the trait uses, and it tells you if invoking Hash with a
> Kt will throw. If a conversion to the argument type is needed, the
> compiler will consider whether that can throw.
>
> You don't need to know the argument type, you only need to know if the
> expression can throw, and C++11 provides the tools to check that
> accurately.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr96088.patch
Type: text/x-patch
Size: 26711 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20210522/26703560/attachment-0001.bin>
More information about the Libstdc++
mailing list