[PATCH] _Hashtable fancy pointer support
François Dumont
frs.dumont@gmail.com
Thu Oct 16 20:12:00 GMT 2025
Ping ?
With the multiplication of PRs, great news by the way, it starts being
lost in the limbos of sourceware.org :-)
On 8/6/25 21:20, François Dumont wrote:
> Hi
>
> Any chance to get a review for this patch ?
>
> I've been testing it for quite some time now with no problem. Moreover
> it's mostly replication of what has been done on other containers.
>
> libstdc++: Add fancy pointer support to std::_Hashtable [PR57272]
>
> The fancy allocator pointer type support is added to
> std::unordered_map,
> std::unordered_multimap, std::unordered_multiset and
> std::unordered_set
> through the underlying std::_Hashtable class.
>
> To respect ABI a new parallel hierarchy of node types has been added.
> This change introduces new class template parameterized on the
> allocator's
> void_pointer type, __hashtable::_Node_base, and new class templates
> parameterized on the allocator's pointer type, __hashtable::_Node,
> __hashtable::_Iterator, __hashtable::_Local_iterator. The
> _Iterator class
> template is used for both iterator and const_iterator. The
> _Local_iterator
> class template is used for both local_iterator and
> const_local_iterator.
> Whether std::_Hashtable<K, V, A, KoV, E, H, RH, U, RP, T> should
> use the old
> __detail::_Hash_node<V, T::__hash_cached::value> or new
> __hashtable::_Node<A::pointer> type family internally is
> controlled by a new
> __hashtable::_Node_traits traits template. Whether it should use
> the old
> __detail::_Node_iterator<V, T::__constant_iterators::value,
> T::__hash_cached::value>
> or new __hashtable::_Iterator<Const,
> T::__constant_iterators::value, A::pointer>
> type family internally is controlled by
> __hashtable::_Iterator_traits traits
> template.
>
> In case anybody is currently using std::_Hashtable with an
> allocator that has a
> fancy pointer, this change will be an ABI break, because their
> std::_Hashtable
> instantiations would start to (correctly) use the fancy pointer
> type. Note that
> the new type family used in this case is always caching the hash
> code at node
> level.
>
> Because std::_Hashtable will never use fancy pointers in C++98
> mode, recompiling
> everything to use fancy pointers isn't even possible if mixing
> C++98 and C++11
> code that uses std::_Hashtable. To alleviate this problem,
> compiling with
> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0 will force
> std::_Hashtable to have the
> old, non-conforming behaviour and use raw pointers internally. For
> testing
> purposes, compiling with
> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001 will force
> std::_Hashtable to always use the new node types.
>
> This macro is currently undocumented, which needs to be fixed.
>
> libstdc++-v3/ChangeLog:
>
> PR libstdc++/57272
> * include/bits/hashtable.h
> (__hashtable::_Node_base<>, __hashtable::_Node<>): New.
> (__hashtable::_Iterator_base<>, __hashtable::_Iterator<>):
> New.
> (__hashtable::_Local_iterator<>): New.
> (__hashtable::_Node_traits<>,
> __hashtable::_Iterator_traits<>): New.
> (__hashtable::__alloc_ptr<>): New template alias.
> (_Hashtable<>::__node_type, __node_alloc_type,
> __node_alloc_traits, __node_ptr)
> (__node_base, __node_base_ptr, __buckets_ptr): Rename
> respectively into...
> (_Hashtable<>::_Node, _Node_alloc, _Node_alloc_traits,
> _Node_ptr)
> (_Node_base, _Base_ptr, _Buckets_ptr): ... those.
> (_Hashtable<>::_Buckets_ptr_traits): New.
> (_Hashtable<>::__hash_code_base_access): Remove.
> (_Hashtable<>::_S_v, _S_next, _M_single_bucket_ptr): New.
> (_Hashtable<>::_M_node_hash_code, _M_node_hash_code_ext,
> _M_bucket_index)
> (_M_bucket_index_ext, _M_key_equals, _M_key_equals_tr,
> _M_equals, _M_equals_tr)
> (_M_node_equals): New.
> (_Hashtable<>::__location_type::_M_base): New.
> (_Hashtable<>::_S_adapt): New.
> (_Hashtable<>): Adapt.
> * include/bits/hashtable_policy.h: Include
> <bits/ptr_traits.h>.
> Include <bits/stl_uninitialized.h>.
> (_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE): New macro, default
> to 1.
> (_Hash_node_base::_M_base_ptr): New.
> (_Hash_node<>::_M_node_ptr): New.
> (_Hash_code_base<>::_M_hash_code, _M_bucket_index): Remove.
> (_Hashtable_base<>::_M_key_equals, _M_key_equals_tr):
> Adapt to only take key
> type.
> (_Hashtable_base<>::_M_equals, _M_equals_tr,
> _M_node_equals): Remove.
> (_Hashtable_alloc<>): Adapt.
> * testsuite/23_containers/unordered_map/115939.cc: #undef
> _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE as types associated
> with fancy pointer
> support do not suffer from the ambiguity issue tested here.
> *
> testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New test.
> *
> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc:
> New test case.
> *
> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
> New test case.
> *
> testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc: New
> test case.
> *
> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc:
> New test case.
> *
> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
> New test case.
> *
> testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc: New
> test case.
> *
> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc:
> New test case.
> *
> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
> New test case.
> *
> testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt.
> * testsuite/23_containers/unordered_set/instantiation_neg.cc:
> Undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE.
> *
> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc:
> New test case.
> *
> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
> New test case.
>
> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>
> Thanks,
>
> François
>
>
> On 06/07/2025 16:04, François Dumont wrote:
>> I've eventually decided to preserve abi if the sizeof of the fancy
>> pointer type is equal to the sizeof of a C pointer that we are
>> currently using. That's a prerequisite to potentially have abi
>> backward compatibility.
>>
>> The only diff now with the legacy node/iterator implementations is on
>> the local_iterator for which I haven't reproduce the complicated code
>> to store of the hash functor on the local_iterator instance when the
>> hash code is not cached. Instead, when hash code is not cached, the
>> end(bucket) method is finding the last node of the bucket. The
>> drawback is that the loop on bucket's local_iterator will be done
>> twice, once to compute end and then the user code loop.
>>
>> PR updated here:
>>
>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>>
>> François
>>
>> On 26/06/2025 19:39, François Dumont wrote:
>>> No chance to just answer to the question below about how
>>> conservative I should be ?
>>>
>>> Thanks
>>>
>>> On 02/06/2025 07:07, François Dumont wrote:
>>>> Hi
>>>>
>>>> It would be nice if someone got some time to review this PR.
>>>>
>>>> Compared to other containers for which support of fancy allocator
>>>> pointer type have been added the main difference is that in
>>>> std::_Hashtable usage of the new node types is an abi breaking
>>>> change, no matter how fancy or not is the allocator's pointer type.
>>>> This is because in this case hash code is always cached and is put
>>>> in memory just after pointer to next node. Let me know if I need to
>>>> be more conservative.
>>>>
>>>> libstdc++: Add fancy pointer support to std::_Hashtable [PR57272]
>>>>
>>>> The fancy allocator pointer type support is added to
>>>> std::unordered_map,
>>>> std::unordered_multimap, std::unordered_multiset and
>>>> std::unordered_set
>>>> through the underlying std::_Hashtable class.
>>>>
>>>> To respect ABI a new parallel hierarchy of node types has been
>>>> added.
>>>> This change introduces new class template parameterized on the
>>>> allocator's
>>>> void_pointer type, __hashtable::_Node_base, and new class
>>>> templates
>>>> parameterized on the allocator's pointer type, __hashtable::_Node,
>>>> __hashtable::_Iterator, __hashtable::_Local_iterator. The
>>>> _Iterator class
>>>> template is used for both iterator and const_iterator. The
>>>> _Local_iterator
>>>> class template is used for both local_iterator and
>>>> const_local_iterator.
>>>> Whether std::_Hashtable<K, V, A, KoV, E, H, RH, U, RP, T>
>>>> should use the old
>>>> __detail::_Hash_node<V, T::__hash_cached::value> or new
>>>> __hashtable::_Node<A::pointer> type family internally is
>>>> controlled by a new
>>>> __hashtable::_Node_traits traits template. Whether it should
>>>> use the old
>>>> __detail::_Node_iterator<V, T::__constant_iterators::value,
>>>> T::__hash_cached::value>
>>>> or new __hashtable::_Iterator<Const,
>>>> T::__constant_iterators::value, A::pointer>
>>>> type family internally is controlled by
>>>> __hashtable::_Iterator_traits traits
>>>> template.
>>>>
>>>> In case anybody is currently using std::_Hashtable with an
>>>> allocator that has a
>>>> fancy pointer, this change will be an ABI break, because their
>>>> std::_Hashtable
>>>> instantiations would start to (correctly) use the fancy pointer
>>>> type. Note that
>>>> the new type family used in this case is always caching the
>>>> hash code at node
>>>> level.
>>>>
>>>> Because std::_Hashtable will never use fancy pointers in C++98
>>>> mode, recompiling
>>>> everything to use fancy pointers isn't even possible if mixing
>>>> C++98 and C++11
>>>> code that uses std::_Hashtable. To alleviate this problem,
>>>> compiling with
>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0 will force
>>>> std::_Hashtable to have the
>>>> old, non-conforming behaviour and use raw pointers internally.
>>>> For testing
>>>> purposes, compiling with
>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001 will force
>>>> std::_Hashtable to always use the new node types.
>>>>
>>>> This macro is currently undocumented, which needs to be fixed.
>>>>
>>>> libstdc++-v3/ChangeLog:
>>>>
>>>> PR libstdc++/57272
>>>> * include/bits/hashtable.h
>>>> (__hashtable::_Node_base<>, __hashtable::_Node<>): New.
>>>> (__hashtable::_Iterator_base<>,
>>>> __hashtable::_Iterator<>): New.
>>>> (__hashtable::_Local_iterator<>): New.
>>>> (__hashtable::_Node_traits<>,
>>>> __hashtable::_Iterator_traits<>): New.
>>>> (__hashtable::__alloc_ptr<>): New template alias.
>>>> (_Hashtable<>::__node_type, __node_alloc_type,
>>>> __node_alloc_traits, __node_ptr)
>>>> (__node_base, __node_base_ptr, __buckets_ptr): Rename
>>>> respectively into...
>>>> (_Hashtable<>::_Node, _Node_alloc, _Node_alloc_traits,
>>>> _Node_ptr)
>>>> (_Node_base, _Base_ptr, _Buckets_ptr): ... those.
>>>> (_Hashtable<>::_Buckets_ptr_traits): New.
>>>> (_Hashtable<>::__hash_code_base_access): Remove.
>>>> (_Hashtable<>::_S_v, _S_next, _M_single_bucket_ptr): New.
>>>> (_Hashtable<>::_M_node_hash_code,
>>>> _M_node_hash_code_ext, _M_bucket_index)
>>>> (_M_bucket_index_ext, _M_key_equals, _M_key_equals_tr,
>>>> _M_equals, _M_equals_tr)
>>>> (_M_node_equals): New.
>>>> (_Hashtable<>::__location_type::_M_base): New.
>>>> (_Hashtable<>::_S_adapt): New.
>>>> (_Hashtable<>): Adapt.
>>>> * include/bits/hashtable_policy.h: Include
>>>> <bits/ptr_traits.h>.
>>>> Include <bits/stl_uninitialized.h>.
>>>> (_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE): New macro,
>>>> default to 1.
>>>> (_Hash_node_base::_M_base_ptr): New.
>>>> (_Hash_node<>::_M_node_ptr): New.
>>>> (_Hash_code_base<>::_M_hash_code, _M_bucket_index):
>>>> Remove.
>>>> (_Hashtable_base<>::_M_key_equals, _M_key_equals_tr):
>>>> Adapt to only take key
>>>> type.
>>>> (_Hashtable_base<>::_M_equals, _M_equals_tr,
>>>> _M_node_equals): Remove.
>>>> (_Hashtable_alloc<>): Adapt.
>>>> * testsuite/23_containers/unordered_map/115939.cc: #undef
>>>> _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE as types
>>>> associated with fancy pointer
>>>> support do not suffer from the ambiguity issue tested
>>>> here.
>>>> *
>>>> testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New test.
>>>> *
>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt.
>>>> *
>>>> testsuite/23_containers/unordered_set/instantiation_neg.cc:
>>>> Undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE.
>>>> *
>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc:
>>>> New test case.
>>>> *
>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>> New test case.
>>>>
>>>> Ok to commit ?
>>>>
>>>> See also:
>>>>
>>>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>>>>
>>>> François
>>>>
>>>>
>>>> On 19/03/2025 21:09, François Dumont wrote:
>>>>> Hi
>>>>>
>>>>> Following latest changes on unordered container I've rebased and
>>>>> updated this patch to add fancy allocator 's pointer type support
>>>>> in unordered containers.
>>>>>
>>>>> libstdc++: Add fancy pointer support to std::_Hashtable [PR57272]
>>>>>
>>>>> The fancy allocator pointer type support is added to
>>>>> std::unordered_map,
>>>>> std::unordered_multimap, std::unordered_multiset and
>>>>> std::unordered_set
>>>>> through the underlying std::_Hashtable class.
>>>>>
>>>>> To respect ABI a new parralel hierarchy of node types has been
>>>>> added.
>>>>> This change introduces new class template parameterized on the
>>>>> allocator's
>>>>> void_pointer type, __hashtable::_Node_base, and new class
>>>>> templates
>>>>> parameterized on the allocator's pointer type,
>>>>> __hashtable::_Node,
>>>>> __hashtable::_Iterator, __hashtable::_Local_iterator. The
>>>>> _Iterator class
>>>>> template is used for both iterator and const_iterator. The
>>>>> _Local_iterator
>>>>> class template is used for both local_iterator and
>>>>> const_local_iterator.
>>>>> Whether std::_Hashtable<K, V, A, KoV, E, H, RH, U, RP, T>
>>>>> should use the old
>>>>> __detail::_Hash_node<V, T::__hash_cached::value> or new
>>>>> __hashtable::_Node<A::pointer> type family internally is
>>>>> controlled by a new
>>>>> __hashtable::_Node_traits traits template. Whether it should
>>>>> use the old
>>>>> __detail::_Node_iterator<V, T::__constant_iterators::value,
>>>>> T::__hash_cached::value>
>>>>> or new __hashtable::_Iterator<Const,
>>>>> T::__constant_iterators::value, A::pointer>
>>>>> type family internally is controlled by
>>>>> __hashtable::_Iterator_traits traits
>>>>> template.
>>>>>
>>>>> In case anybody is currently using std::_Hashtable with an
>>>>> allocator that has a
>>>>> fancy pointer, this change would be an ABI break, because
>>>>> their std::_Hashtable
>>>>> instantiations would start to (correctly) use the fancy
>>>>> pointer type. If the
>>>>> fancy pointer just contains a single pointer and so has the
>>>>> same size, layout,
>>>>> and object representation as a raw pointer, the code might
>>>>> still work (despite
>>>>> being an ODR violation). But if their fancy pointer has a
>>>>> different
>>>>> representation, they would need to recompile all their code
>>>>> using that
>>>>> allocator with std::_Hashtable. Because std::_Hashtable will
>>>>> never use fancy
>>>>> pointers in C++98 mode, recompiling everything to use fancy
>>>>> pointers isn't
>>>>> even possible if mixing C++98 and C++11 code that uses
>>>>> std::_Hashtable. To
>>>>> alleviate this problem, compiling with
>>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=0
>>>>> will force std::_Hashtable to have the old, non-conforming
>>>>> behaviour and use
>>>>> raw pointers internally. For testing purposes, compiling with
>>>>> -D_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE=9001 will force
>>>>> std::_Hashtable to
>>>>> always use the new node types. This macro is currently
>>>>> undocumented, which
>>>>> needs to be fixed.
>>>>>
>>>>> Note that the new type family used in case of fancy allocator
>>>>> pointer type is
>>>>> always caching the hash code at node level.
>>>>>
>>>>> libstdc++-v3/ChangeLog:
>>>>>
>>>>> PR libstdc++/57272
>>>>> * include/bits/hashtable.h
>>>>> (__hashtable::_Node_base<>, __hashtable::_Node<>): New.
>>>>> (__hashtable::_Iterator_base<>,
>>>>> __hashtable::_Iterator<>): New.
>>>>> (__hashtable::_Local_iterator<>): New.
>>>>> (__hashtable::_Node_traits<>,
>>>>> __hashtable::_Iterator_traits<>): New.
>>>>> (_Hashtable<>::__node_type, __node_alloc_type,
>>>>> __node_alloc_traits,
>>>>> __node_ptr, __node_base, __node_base_ptr,
>>>>> __buckets_ptr): Rename
>>>>> respectively into...
>>>>> (__hashtable::__alloc_ptr<>): New template alias.
>>>>> (_Hashtable<>::_Node, _Node_alloc, _Node_alloc_traits,
>>>>> _Node_ptr,
>>>>> _Node_base, _Base_ptr, _Buckets_ptr): ... those.
>>>>> (_Hashtable<>::_Buckets_ptr_traits): New.
>>>>> (_Hashtable<>::__hash_code_base_access): Remove.
>>>>> (_Hashtable<>::_S_v, _S_next, _M_single_bucket_ptr): New.
>>>>> (_Hashtable<>::_M_node_hash_code,
>>>>> _M_node_hash_code_ext, _M_bucket_index,
>>>>> _M_bucket_index_ext, _M_key_equals, _M_key_equals_tr,
>>>>> _M_equals, _M_equals_tr,
>>>>> _M_node_equals): New.
>>>>> (_Hashtable<>::__location_type::_M_base): New.
>>>>> (_Hashtable<>::_S_adapt): New.
>>>>> (_Hashtable<>): Adapt.
>>>>> * include/bits/hashtable_policy.h: Include
>>>>> <bits/ptr_traits.h>.
>>>>> Include <bits/stl_uninitialized.h>.
>>>>> (_GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE): New macro,
>>>>> default to 1.
>>>>> (_Hash_node_base::_M_base_ptr): New.
>>>>> (_Hash_node<>::_M_node_ptr): New.
>>>>> (_Hash_code_base<>::_M_hash_code, _M_bucket_index):
>>>>> Remove.
>>>>> (_Hashtable_base<>::_M_key_equals, _M_key_equals_tr):
>>>>> Adapt to only take key
>>>>> type.
>>>>> (_Hashtable_base<>::_M_equals, _M_equals_tr,
>>>>> _M_node_equals): Remove.
>>>>> (_Hashtable_alloc<>): Adapt.
>>>>> * testsuite/23_containers/unordered_map/115939.cc: #undef
>>>>> _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE as types
>>>>> associated with fancy pointer
>>>>> support do not suffer from the ambiguity issue tested
>>>>> here.
>>>>> *
>>>>> testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New test.
>>>>> *
>>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_map/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multimap/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_multiset/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/allocator/ext_ptr.cc: Adapt.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/instantiation_neg.cc:
>>>>> Undef _GLIBCXX_USE_ALLOC_PTR_FOR_HASHTABLE.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr.cc:
>>>>> New test case.
>>>>> *
>>>>> testsuite/23_containers/unordered_set/requirements/explicit_instantiation/alloc_ptr_ignored.cc:
>>>>> New test case.
>>>>>
>>>>> Available as a PR here:
>>>>>
>>>>> https://forge.sourceware.org/gcc/gcc-TEST/pulls/32
>>>>>
>>>>> François
>>>>>
More information about the Libstdc++
mailing list