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

[Tomasz Kaminski]

On Tue, Jul 7, 2026 at 8:08 PM Nathan Myers <ncm@cantrip.org> wrote:

> 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?
>
I am suggesting measurements. I expect them being different, as the
the differenence between _M_deallocate_nodes and the loop I am suggesting
is calling M_bucket_index(*__tmp) in each iteration.

>
> 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
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260708/ef7bb8ea/attachment.htm>