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

[Nathan Myers]

On 7/2/26 3:53 AM, Tomasz Kaminski wrote:
> 
> 
> On Thu, Jul 2, 2026 at 9:32 AM Tomasz Kaminski <tkaminsk@redhat.com 
> <mailto:tkaminsk@redhat.com>> wrote:
> 
> 
> 
>     On Thu, Jul 2, 2026 at 2:21 AM Nathan Myers <ncm@cantrip.org
>     <mailto: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 
 >> What I mean is custom string_view class, that defines hash, that
 >> then delegate to hash of string_view.

I understand.

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

Are you suggesting two different thresholds, one for cached
and one not?

It is hard to produce meaningful benchmarks because the time
to zero the whole table will depend heavily on how much of it
lives in some other core's cache, and must first be loaded.
Those in the ticket have the table as hot as is possible.

>         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(*__tmp)] = nullptr;]
>            _M_deallocate_node(__tmp);
>          }
>        _M_element_count = 0;
>        _M_before_begin._M_nxt = nullptr;
> 

Thank you, this looks more like what I had planned originally.


>         +         return;
>         +       }
>                 this->_M_deallocate_nodes(_M_begin());
>                 std::fill_n(_M_buckets, _M_bucket_count, nullptr);
>                 _M_element_count = 0;
>         -- 
>         2.54.0
>