[PATCH] Hashtable PR96088

Thu May 6 20:03:18 GMT 2021

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.

Tested under Linux x86_64, ok to commit ?

François

On 04/12/20 10:10 am, François Dumont wrote:
> Following submission of the heterogeneous lookup in unordered 
> containers I rebased this patch on top of it.
>
> Appart from reducing its size because of some code reuse the 
> heterogeneous lookup had no impact on this one. This is because when I 
> cannot find out if conversion from inserted element type to hash 
> functor can throw then I pass the element as-is, like if hash functor 
> was transparent.
>
>     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 
> used to call
>     the functors and, if necessary, moved to the storage.
>
>     libstdc++-v3/ChangeLog:
>
>             PR libstdc++/96088
>             * include/bits/hashtable_policy.h (_Select2nd): New.
>             (_NodeBuilder<>): New.
>             (_ReuseOrAllocNode<>::operator()): Use variadic template 
> args.
>             (_AllocNode<>::operator()): Likewise.
>             (_Hash_code_base<>::_M_hash_code): Add _Kt template 
> parameter.
>             (_Hashtable_base<>::_M_equals): Add _Kt template parameter.
>             * include/bits/hashtable.h
>             (_Hashtable<>::__node_builder_t): New.
>             (_Hashtable<>::_M_find_before_node): Add _Kt template 
> parameter.
>             (_Hashtable<>::_M_find_node): Likewise.
>             (_Hashtable<>::_Hash_arg_t): New.
>             (_Hashtable<>::_S_forward_key): New.
> (_Hashtable<>::_M_insert_unique<>(_Kt&&, _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.
>
> Note that I plan to change counter type name to something more 
> meaningful but only when back to stage 1.
>
> François
>
> On 24/10/20 4:25 pm, François Dumont wrote:
>> Hi
>>
>>     Just a rebase of this patch.
>>
>> François
>>
>> On 17/10/20 6:21 pm, François Dumont wrote:
>>> 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: hashtable.patch
Type: text/x-patch
Size: 25892 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20210506/c91021cc/attachment-0001.bin>