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 >>>> >>> >> >