On Thu, Jul 2, 2026 at 9:32 AM Tomasz Kaminski <[email protected]> wrote:
> > > On Thu, Jul 2, 2026 at 2:21 AM Nathan Myers <[email protected]> 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; _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 >> >>
