Re: [PATCH] Hashtable PR96088

["François Dumont" <frs.dumont@gmail.com>]

Hi

     No chance yet to review this proposal ?

François

On 06/05/21 10:03 pm, François Dumont 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.
>
> 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
>>>>>
>>>>
>>>
>>
>