<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote gmail_quote_container"><div dir="ltr" class="gmail_attr">On Tue, Jul 7, 2026 at 8:08 PM Nathan Myers <<a href="mailto:ncm@cantrip.org">ncm@cantrip.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 7/2/26 3:53 AM, Tomasz Kaminski wrote:<br>
> <br>
> <br>
> On Thu, Jul 2, 2026 at 9:32 AM Tomasz Kaminski <<a href="mailto:tkaminsk@redhat.com" target="_blank">tkaminsk@redhat.com</a> <br>
> <mailto:<a href="mailto:tkaminsk@redhat.com" target="_blank">tkaminsk@redhat.com</a>>> wrote:<br>
> <br>
> <br>
> <br>
> On Thu, Jul 2, 2026 at 2:21 AM Nathan Myers <<a href="mailto:ncm@cantrip.org" target="_blank">ncm@cantrip.org</a><br>
> <mailto:<a href="mailto:ncm@cantrip.org" target="_blank">ncm@cantrip.org</a>>> wrote:<br>
> <br>
> The hash tables std::unordered_set, _map, _multiset, _multimap<br>
> as implemented take time linear in the size of the bucket array<br>
> (because memset), rather than in the number of elements stored,<br>
> in violation of Standard requirements. With this patch it<br>
> performs work only for the elements present, but only for a very<br>
> sparsely-populated table. With a bucket loading above 0.5%, the<br>
> status-quo method tests faster, so the new method is used only<br>
> when less.<br>
> <br>
> Could you post your test results? <br>
> <br>
> Clearing at the bucket level requires us to find the bucket index for <br>
> the node,<br>
> which requires computing a hash. This may highly depend on type used, so<br>
> I would measure for keys<br>
> * int - so fash hash is enabled<br>
> * string_view - we explicitly disable fast hash, so we get hash cached<br>
> * string_view with custom hash specialization - so is_fast_hash is <br>
> enabled <br>
>> What I mean is custom string_view class, that defines hash, that<br>
>> then delegate to hash of string_view.<br>
<br>
I understand.<br>
<br>
> If you will use the implementation suggested below (instead of erase), I <br>
> think<br>
> the expected load factor may be much higher if is_fast_hash was specialized<br>
> to false (and we do not need to recompute the hash).<br>
<br>
Are you suggesting two different thresholds, one for cached<br>
and one not?<br></blockquote><div>I am suggesting measurements. I expect them being different, as the</div><div>the differenence between _M_deallocate_nodes and the loop I am suggesting</div><div>is calling M_bucket_index(*__tmp) in each iteration.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
It is hard to produce meaningful benchmarks because the time<br>
to zero the whole table will depend heavily on how much of it<br>
lives in some other core's cache, and must first be loaded.<br>
Those in the ticket have the table as hot as is possible.<br>
<br>
> It turns out libc++ also zeroes its bucket table on clear(), like<br>
> libstdc++, but uses a regular loop. Performance differences seem<br>
> to depend on memory organization.<br>
> <br>
> libstdc++-v3/Changelog:<br>
> PR libstdc++/67922<br>
> * include/bits/hashtable.h (clear): Special-case<br>
> minimal population.<br>
> ---<br>
> libstdc++-v3/include/bits/hashtable.h | 5 +++++<br>
> 1 file changed, 5 insertions(+)<br>
> <br>
> diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-<br>
> v3/include/bits/hashtable.h<br>
> index eff6c31d827..d9eb0fe45e3 100644<br>
> --- a/libstdc++-v3/include/bits/hashtable.h<br>
> +++ b/libstdc++-v3/include/bits/hashtable.h<br>
> @@ -2778,6 +2778,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION<br>
> _Hash, _RangeHash, _Unused, _RehashPolicy,<br>
> _Traits>::<br>
> clear() noexcept<br>
> {<br>
> + if (this->size() < this->bucket_count() / 200)<br>
> + {<br>
> + this->erase(this->begin(), this->end());<br>
> <br>
> The erase implementation here is not optimal, as it requires some extra work<br>
> to detect moving between the buckets, that is unnecessary here,<br>
> We could do something like this instead, were we just clear the buckets <br>
> nodes<br>
> as we go.<br>
> if (load_factor_check)<br>
> {<br>
> // Avoids computing the hash<br>
> this->_M_deallocate_nodes(_M_begin());<br>
> std::fill_n(_M_buckets, _M_bucket_count, nullptr);<br>
> }<br>
> else while (__n)<br>
> {<br>
> __node_ptr __tmp = __n;<br>
> __n = __n->_M_next();<br>
>[ _M_buckets[M_bucket_index(*__tmp)] = nullptr;]<br>
> _M_deallocate_node(__tmp);<br>
> }<br>
> _M_element_count = 0;<br>
> _M_before_begin._M_nxt = nullptr;<br>
> <br>
<br>
Thank you, this looks more like what I had planned originally.<br>
<br>
<br>
> + return;<br>
> + }<br>
> this->_M_deallocate_nodes(_M_begin());<br>
> std::fill_n(_M_buckets, _M_bucket_count, nullptr);<br>
> _M_element_count = 0;<br>
> -- <br>
> 2.54.0<br>
> <br>
<br>
</blockquote></div></div>