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

[François Dumont]

Note that this problem will be even worst when fancy pointer support in 
_Hashtable will be in.

Maybe with my proposal last recall here:

https://gcc.gnu.org/pipermail/libstdc++/2026-May/066381.html

If memset is not used anymore we might prefer to use the alternative 
loop at a much lower load factor threshold.


On 7/8/26 06:31, Tomasz Kaminski wrote:
>
>
> 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/20260711/dccd37b0/attachment.htm>