[PATCH] Hashtable PR96088

[François Dumont]

I eventually would like to propose the following resolution.

For multi-key containers I kept the same resolution build the node first 
and compute has code from the node key.

For unique-key ones I change behavior when I can't find out hash functor 
argument type. I am rather using the iterator key type and just hope 
that the user's functors are prepared for it.

For now I am using functor argument_type which is deprecated. I just 
hope that the day we remove it we will have a compiler built-in to get 
any functor argument type given an input type.

     libstdc++: Limit allocation on iterator insertion in Hashtable [PR 
96088]

     Detect Hash functor argument type to find out if it is different to the
     container key_type and if a temporary instance needs to be 
generated to invoke
     the functor from the iterator value_type key part. If this 
temporary generation
     can throw a key_type instance is generated at Hashtable level and 
use to call
     the functors and, if needed, move it to the storage.

     libstdc++-v3/ChangeLog:

             PR libstdc++/96088
             * include/bits/hashtable_policy.h (_Select2nd): New.
             (_NodeBuilder<>): New.
             (_ReuseOrAllocNode<>::operator()): Use varriadic template args.
             (_AllocNode<>::operator()): Likewise.
             (_Hash_code_base<>::_M_hash_code): Add _KType template 
parameter.
             (_Hashtable_base<>::_M_equals): Add _KType template parameter.
             * include/bits/hashtable.h
             (_Hashtable<>::__node_builder_t): New.
             (_Hashtable<>::_M_find_before_node): Add _KType template 
parameter.
             (_Hashtable<>::_M_find_node): Likewise.
             (_Hashtable<>::_Hash_arg_t): New.
             (_Hashtable<>::_S_forward_key): New.
(_Hashtable<>::_M_insert_unique<>(_KType&&, _Arg&&, const _NodeGenerator&)):
              New.
             (_Hashtable<>::_M_insert): Use latter.
             * 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 x86_64.

Ok to commit ?

François

On 01/09/20 2:36 pm, François Dumont wrote:
> Hi
>
>     I started working on PR96088 problem in Hashtable implementation.
>
>     In the case of multi-key containers the problem is easy to manage. 
> Now that we have _Scoped_node we can easily allocate the node first 
> and then extract the key from it to compute hash code. It is quite 
> safe as computating a hash code is rarely going to throw especially if 
> there is no allocation anymore to invoke the hasher.
>
>     In the unique-key case it is more tricky. First I only consider 
> the hasher invocation, the equal_to shall be consistent with it. My 
> approach is to consider that if the operation needed transform the 
> inserted element key part into the hasher argument can throw then I 
> better generate a key_type instance myself and move it to the node if 
> it is eventually to be inserted. Note that any allocation needed to 
> call the hasher from the key_type is user fault.
>
>     Of course the tricky part here is to find out what is the hasher 
> argument_type. For the moment I support hasher with a nested 
> argument_type typedef and function pointer. But, as pointed out by the 
> tests which are failing for the moment I am missing the support for a 
> classic functor. I am pretty sure that if I support it I will still be 
> missing some use cases (like std::function). So I am looking for help 
> on how to determine it. Or maybe the whole approach it wrong ?
>
> For now I am still working on it, thanks,
>
> François
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: pr96088.patch
Type: text/x-patch
Size: 28586 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20201017/aa1c9662/attachment-0001.bin>