[PATCH] libstdc++: make hash container clear() complexity O(size()) (DR2550) [PR67922]

[Tomasz Kaminski]

On Thu, Jul 2, 2026 at 9:53 AM Tomasz Kaminski <tkaminsk@redhat.com> wrote:

>
>
> On Thu, Jul 2, 2026 at 9:32 AM Tomasz Kaminski <tkaminsk@redhat.com>
> wrote:
>
>>
>>
>> On Thu, Jul 2, 2026 at 2:21 AM Nathan Myers <ncm@cantrip.org> wrote:
>>
>>> The hash tables std::unordered_set, _map, _multiset, _multimap
>>> as implemented take time linear in the size of the bucket array
>>> (because memset), rather than in the number of elements stored,
>>> in violation of Standard requirements. With this patch it
>>> performs work only for the elements present, but only for a very
>>> sparsely-populated table. With a bucket loading above 0.5%, the
>>> status-quo method tests faster, so the new method is used only
>>> when less.
>>>
>> Could you post your test results?
>>
> Clearing at the bucket level requires us to find the bucket index for the
> node,
> which requires computing a hash. This may highly depend on type used, so
> I would measure for keys
>   * int - so fash hash is enabled
>   * string_view - we explicitly disable fast hash, so we get hash cached
>   * string_view with custom hash specialization - so is_fast_hash is
> enabled
>
> If you will use the implementation suggested below (instead of erase), I
> think
> the expected load factor may be much higher if is_fast_hash was specialized
> to false (and we do not need to recompute the hash).
>
>
>>
>>> It turns out libc++ also zeroes its bucket table on clear(), like
>>> libstdc++, but uses a regular loop. Performance differences seem
>>> to depend on memory organization.
>>>
>>> libstdc++-v3/Changelog:
>>>         PR libstdc++/67922
>>>         * include/bits/hashtable.h (clear): Special-case minimal
>>> population.
>>> ---
>>>  libstdc++-v3/include/bits/hashtable.h | 5 +++++
>>>  1 file changed, 5 insertions(+)
>>>
>>> diff --git a/libstdc++-v3/include/bits/hashtable.h
>>> b/libstdc++-v3/include/bits/hashtable.h
>>> index eff6c31d827..d9eb0fe45e3 100644
>>> --- a/libstdc++-v3/include/bits/hashtable.h
>>> +++ b/libstdc++-v3/include/bits/hashtable.h
>>> @@ -2778,6 +2778,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>                _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
>>>      clear() noexcept
>>>      {
>>> +      if (this->size() < this->bucket_count() / 200)
>>> +       {
>>> +         this->erase(this->begin(), this->end());
>>>
>> The erase implementation here is not optimal, as it requires some extra
> work
> to detect moving between the buckets, that is unnecessary here,
> We could do something like this instead, were we just clear the buckets
> nodes
> as we go.
>       if (load_factor_check)
>       {
>           // Avoids computing the hash
>           this->_M_deallocate_nodes(_M_begin());
>           std::fill_n(_M_buckets, _M_bucket_count, nullptr);
>       }
>       else while (__n)
>         {
>           __node_ptr __tmp = __n;
>           __n = __n->_M_next();
>           _M_buckets[M_bucket_index(*__n)] = nullptr;
>
The above should be before moving next or use __tmp.

>           _M_deallocate_node(__tmp);
>         }
>       _M_element_count = 0;
>       _M_before_begin._M_nxt = nullptr;
>
>
>> +         return;
>>> +       }
>>>        this->_M_deallocate_nodes(_M_begin());
>>>        std::fill_n(_M_buckets, _M_bucket_count, nullptr);
>>>        _M_element_count = 0;
>>> --
>>> 2.54.0
>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260702/96ec5f8f/attachment-0001.htm>