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.
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());
+ return;
+ }
this->_M_deallocate_nodes(_M_begin());
std::fill_n(_M_buckets, _M_bucket_count, nullptr);
_M_element_count = 0;
--
2.54.0
