[PATCH] Hashtable PR96088
François Dumont
frs.dumont@gmail.com
Mon May 17 19:24:09 GMT 2021
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
>>>>>
>>>>
>>>
>>
>
More information about the Libstdc++
mailing list