[WIP] libstdc++: fix hash container clear() complexity (DR2550) [PR67922]
Nathan Myers <[email protected]> Tue, 4 Aug 2026 23:05:19 -0400
| Newsgroups | gmane.comp.gcc.patches,gmane.comp.gcc.libstdc++.devel |
|---|---|
| Message-ID | <[email protected]> |
[This uses a single compile-time number as a fraction of
`bucket_count()` to define sparsity. In principle this could
be adjusted by e.g. whether the hash function is slow and not
cached vs. fast or cached.]
The hash tables std::unordered_set, _map, _multiset, _multimap as
implemented take time linear in the size of the bucket array (via
std::fill), 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 sparsely-
populated table. With a bucket loading above a fixed threshold,
clearing the whole table is assumed to be faster, so the new
method is used only when loading is less.
The optimal definition for "sparsely-populated" depends on
information rarely available, so we choose a default threshold,
expressed as a fraction of the number of buckets, 16 indicating
that if size() is less than 1/16th bucket_count(), the table is
considered sparsely-populated. Users may set a preprocessor
symbol _GLIBCXX_HASH_CLEAR_THRESHOLD when building with hashed
containers to choose a different value.
This also adds a directory under testsuite/performance with
code to help identify, for a given target, a good choice of
threshold.
libstdc++-v3/Changelog:
=09PR libstdc++/67922
=09* include/bits/hashtable.h (clear): Special-case sparse population.
=09* testsuite/performance/23_containers/hash_clear/README: Add.
=09* testsuite/performance/23_containers/hash_clear/Makefile: Add.
=09* testsuite/performance/23_containers/hash_clear/hashbench.cc: Add.
=09* testsuite/performance/23_containers/hash_clear/bench_int.cc: Add.
=09* testsuite/performance/23_containers/hash_clear/bench_str.cc: Add.
=09* testsuite/performance/23_containers/hash_clear/run: Add.
---
libstdc++-v3/include/bits/hashtable.h | 18 ++++-
.../23_containers/hash_clear/Makefile | 56 +++++++++++++
.../23_containers/hash_clear/README | 80 +++++++++++++++++++
.../23_containers/hash_clear/bench_int.cc | 22 +++++
.../23_containers/hash_clear/bench_str.cc | 38 +++++++++
.../23_containers/hash_clear/hashbench.cc | 77 ++++++++++++++++++
.../performance/23_containers/hash_clear/run | 14 ++++
7 files changed, 303 insertions(+), 2 deletions(-)
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_c=
lear/Makefile
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_c=
lear/README
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_c=
lear/bench_int.cc
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_c=
lear/bench_str.cc
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_c=
lear/hashbench.cc
create mode 100755 libstdc++-v3/testsuite/performance/23_containers/hash_c=
lear/run
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/b=
its/hashtable.h
index eff6c31d827..f6141882883 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -2778,8 +2778,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
=09 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
clear() noexcept
{
- this->_M_deallocate_nodes(_M_begin());
- std::fill_n(_M_buckets, _M_bucket_count, nullptr);
+# ifndef _GLIBCXX_HASH_CLEAR_THRESHOLD
+# define _GLIBCXX_HASH_CLEAR_THRESHOLD 16 // [0 .. ~size_t()]
+# endif
+ const size_t __threshold =3D _GLIBCXX_HASH_CLEAR_THRESHOLD;
+ if (__threshold !=3D 0 && _M_bucket_count / __threshold < _M_element=
_count)
+=09{ // Avoid computing hashes.
+=09 this->_M_deallocate_nodes(_M_begin());
+=09 std::fill_n(_M_buckets, _M_bucket_count, nullptr);
+=09}
+ else for (auto __n =3D this->_M_begin(); __n !=3D nullptr;)
+=09{
+=09 auto __tmp =3D __n;
+=09 __n =3D __n->_M_next();
+=09 _M_buckets[_M_bucket_index(*__tmp)] =3D nullptr;
+=09 this->_M_deallocate_node(__tmp);
+=09}
_M_element_count =3D 0;
_M_before_begin._M_nxt =3D nullptr;
}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/hash_clear/Ma=
kefile b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/Makefi=
le
new file mode 100644
index 00000000000..b88aa261d32
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/Makefile
@@ -0,0 +1,56 @@
+CACHE_SIZE=3D16 # Megabytes of L3 cache.
+THREADS=3D4
+FIRST_CORE=3D0 # Run on cores [0..THREADS).
+CACHELINE=3D64 # Size of cache line, 128 on POWER.
+
+THR_N=3D-DTHREADS=3D$(THREADS)
+THR_1=3D-DTHREADS=3D1
+# CXX=3D
+CXXFLAGS=3D-W -Wall -O2 -g -std=3Dc++26 \
+ -DCACHELINE=3D$(CACHELINE) \
+ -DCACHE_SIZE=3D$(CACHE_SIZE) \
+ -DFIRST_CORE=3D$(FIRST_CORE)
+
+run: all; bash run
+
+ALL =3D=09bench_int_walk \
+=09bench_int_fill \
+=09bench_str_walk \
+=09bench_str_fill \
+=09bench_int_walk_nc \
+=09bench_int_fill_nc \
+=09bench_str_walk_nc \
+=09bench_str_fill_nc
+
+all: $(ALL)
+clean:; rm -f $(ALL)
+
+# These run with one or more threads clobbering cache
+
+bench_int.cc bench_str.cc: hashtable.h
+
+bench_int_walk: bench_int.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_N) -o $@ $^
+
+bench_int_fill: bench_int.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_N) -DFILL -o $@ $^
+
+bench_str_walk: bench_str.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_N) -o $@ $^
+
+bench_str_fill: bench_str.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_N) -DFILL -o $@ $^
+
+# These run without cache interference.
+
+bench_int_walk_nc: bench_int.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_1) -o $@ $^
+
+bench_int_fill_nc: bench_int.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_1) -DFILL -o $@ $^
+
+bench_str_walk_nc: bench_str.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_1) -o $@ $^
+
+bench_str_fill_nc: bench_str.cc hashbench.cc
+=09$(CXX) $(CXXFLAGS) $(THR_1) -DFILL -o $@ $^
diff --git a/libstdc++-v3/testsuite/performance/23_containers/hash_clear/RE=
ADME b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/README
new file mode 100644
index 00000000000..6338a32c8bf
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/README
@@ -0,0 +1,80 @@
+This benchmark compares performance of two strategies for
+clearing a hashing container. When the container has few enough
+elements, it is faster to rehash each element and zero only
+those elements' buckets; but with more elements, it is faster
+to zero all the buckets, and avoid re-hashing.
+
+See <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=3D67922> and WG21
+LEWG DR 2550. The Standard requires that the `clear` member's
+performance be linear in the number of elements being cleared,
+not the number of buckets, but we don't want clearing a loaded
+table to take longer than necessary just to conform.
+
+We want a rule for when a container has enough elements that it
+is not worth rehashing all the elements just to avoid zeroing
+empty buckets. The correct number for a given use case depends
+on details of the target architecture, on how expensive it is
+to hash the elements, and on what is cached, details not
+generally available, so we must approximate it with a guess.
+
+Zeroing an individual bucket not in cache may require reading
+(usually) 8 adjacent buckets from backing RAM, poking out the
+one bucket, and writing them all back, where zeroing the whole
+table mostly does not require loading current values. Walking
+the chain of nodes when they are not in cache is commonly much
+slower than actually hashing its elements, but there is no
+avoiding this walk because the nodes must be destroyed and freed.
+
+Much of the cost of zeroing already-empty buckets is borne by
+other code whose cache entries are displaced by zeroed bucket
+contents. It is in general hard to measure that cost, which
+anyway does not figure in the formal complexity guarantee.
+
+This test uses a program that starts two or more threads, one
+that loads up and clears hash tables with varying bucket counts
+and number of elements relative to that count, and others that
+spin, clobbering cache entries. Just two threads may suffice to
+differentiate cache-hot from cache-cold tests, but CPUs with
+many-way caches might need more. The number is chosen in the
+Makefile.
+
+The Makefile also hard-codes the size of the L3 cache, which
+should be adjusted to the host running it, and the ids (0..n)
+of CPU cores that share an L3 cache, likewise. It #defines a
+symbol `FILL` that forces `clear` to use one strategy or the
+other. The Makefile builds eight versions of the program, for
+the two strategies ("walk" and "fill"), for fast and slow (`int`
+and `str`) hash functions, and for running, or not (`_nc`), the
+threads to clobber the cache. `make all` builds and runs tests.
+
+The script `run` executes these programs for a chosen set of
+bucket table sizes and number of elements, reporting the
+relative performance of walking the element list rehashing
+and clearing buckets, vs. filling the bucket table. Runs that
+seem to favor zeroing buckets by `fill` are marked with a "*".
+Running it, we are interested in the transition from more than
+100% to that or less.
+
+Tests are run without and with cache interference ("" vs. "_nc"),
+for tables with fast and slow hashes ("int" vs. "str"), and for
+each the set of table sizes and table loading. Raw numbers
+reported are the actual number of elements inserted each cycle,
+and how many cycles of table load-and-clear were run in one
+second using the "walk" and "fill" strategies.
+
+A sample output stanza with fast hash, and cache interference:
+
+int 100k 100 1000 51627 30467 169%=20
+int 100k 50 2000 23923 17621 135%=20
+int 100k 35 2857 17774 14033 126%=20
+int 100k 20 5000 9382 7817 120%=20
+int 100K 16 6250 6678 6015 111%=20
+int 100k 12 8333 4260 4766 89% *
+int 100k 10 10000 4183 4079 102%=20
+int 100k 7 14285 3095 2909 106%=20
+int 100k 5 20000 2108 2113 99% *
+
+Here we see the transition from 111% to 89%, indicating that with
+100k buckets, a loading ratio above 16 buckets/element, a fast
+hash function, and cold cache, there seems to be no advantage to
+clearing only the buckets occupied by 6250 or more elements.
diff --git a/libstdc++-v3/testsuite/performance/23_containers/hash_clear/be=
nch_int.cc b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/be=
nch_int.cc
new file mode 100644
index 00000000000..24ce6ecffee
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/bench_int=
.cc
@@ -0,0 +1,22 @@
+#ifdef FILL
+# define _GLIBCXX_HASH_CLEAR_THRESHOLD ~0ULL
+#else
+# define _GLIBCXX_HASH_CLEAR_THRESHOLD 0
+#endif
+// #include "../../../../include/bits/hashtable.h"
+#include <unordered_set>
+#include <atomic>
+
+void bench(std::size_t size, unsigned element_count,
+ std::atomic<int>& flag, unsigned& count)
+{
+ std::unordered_set<std::size_t> set; set.rehash(size);
+ std::size_t step =3D size / element_count;
+ while (!flag.load(std::memory_order::acquire))
+ {
+ for (std::size_t i =3D 0; i !=3D element_count; ++i)
+=09set.insert(i * step);
+ set.clear();
+ ++count;
+ }
+}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/hash_clear/be=
nch_str.cc b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/be=
nch_str.cc
new file mode 100644
index 00000000000..ed5577cf8f7
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/bench_str=
.cc
@@ -0,0 +1,38 @@
+#ifdef FILL
+# define _GLIBCXX_HASH_CLEAR_THRESHOLD ~0ULL
+#else
+# define _GLIBCXX_HASH_CLEAR_THRESHOLD 0
+#endif
+// #include "../../../../include/bits/hashtable.h"
+#include <string>
+#include <atomic>
+#include <unordered_set>
+#include <functional>
+#include <charconv>
+
+struct S
+{
+ std::string s{"abcdefghijklmnop"};
+ S(unsigned n) { std::to_chars(&s[0], &s[s.size()], n); }
+ bool operator=3D=3D(S const&) const =3D default;
+};
+namespace std
+{
+ template <> struct hash<S>
+ {
+ static std::size_t operator()(S const& s)
+ { return std::hash<std::string>{}(s.s); }
+ };
+}
+void bench(std::size_t size, unsigned element_count,
+ std::atomic<int>& flag, unsigned& count)
+{
+ std::unordered_set<S> set; set.rehash(size);
+ while (!flag.load(std::memory_order::acquire))
+ {
+ for (std::size_t i =3D 0; i !=3D element_count; ++i)
+=09set.emplace(i);
+ set.clear();
+ ++count;
+ }
+}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/hash_clear/ha=
shbench.cc b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/ha=
shbench.cc
new file mode 100644
index 00000000000..4ba4571118a
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/hashbench=
.cc
@@ -0,0 +1,77 @@
+#include <iostream>
+#include <atomic>
+#include <cstdint>
+#include <pthread.h>
+#include <sched.h>
+#include <time.h>
+
+const std::size_t l3_cache_size =3D CACHE_SIZE * 1024 * 1024;
+const unsigned cacheline_size =3D CACHELINE;
+const unsigned first_core =3D FIRST_CORE;
+const unsigned threads =3D THREADS;
+
+unsigned buckets =3D l3_cache_size / sizeof(int*);
+unsigned ratio =3D 16; // buckets per element
+alignas(cacheline_size) std::atomic<int> stop_flag{0};
+
+struct alignas(cacheline_size) Ctx
+{
+ unsigned id;
+ unsigned count =3D 0;
+ ::pthread_t thr{};
+};
+
+struct alignas(cacheline_size) Cacheline
+{
+ std::atomic<unsigned> words[cacheline_size / sizeof(unsigned)];
+};
+
+void* run(void* in)
+{
+ auto& ctx =3D *(Ctx*)in;
+ if (ctx.id >=3D ::threads) exit(1);
+ ::cpu_set_t cpu_set; CPU_ZERO(&cpu_set);
+ CPU_SET(first_core + ctx.id, &cpu_set);
+ if (0 !=3D ::pthread_setaffinity_np(ctx.thr, sizeof(cpu_set), &cpu_set))
+ ::exit(1);
+ const std::size_t size =3D l3_cache_size / cacheline_size;
+ if (ctx.id !=3D 0)
+ {
+ // Clobber L3 cache continually.
+ Cacheline* a =3D new Cacheline[size];
+ while (!stop_flag.load(std::memory_order::acquire)) {
+=09// walk through memory clobbering each cache line.
+=09for (std::size_t i =3D 0; i !=3D size; ++i) {
+=09 a[i].words[0].store(i+ctx.count, std::memory_order::relaxed);
+=09}
+=09++ctx.count;
+ }
+ }
+ else
+ {
+ void bench(std::size_t, unsigned, std::atomic<int>&, unsigned&);
+ bench(buckets, buckets/ratio, stop_flag, ctx.count);
+ }
+ ::pthread_exit(nullptr);
+}
+
+int main(int ac, char** av)
+{
+ if (ac > 1) buckets =3D ::atoi(av[1]);
+ if (buckets < 1000) exit(1);
+ if (ac > 2) ratio =3D ::atoi(av[2]);
+ if (ratio < 1) exit(1);
+ Ctx ctxs[::threads];
+ for (unsigned id =3D ::threads; id-- !=3D 0;)
+ {
+ ctxs[id].id =3D id;
+ if (0 !=3D ::pthread_create(&ctxs[id].thr, nullptr, ::run, ctxs + id=
))
+=09exit(1);
+ }
+ ::timespec time{::time_t(1),{}};
+ ::nanosleep(&time, nullptr);
+ stop_flag.store(1, std::memory_order::release);
+ for (auto& ctx : ctxs)
+ ::pthread_join(ctx.thr, nullptr);
+ std::cout << ctxs[0].count << " \n";
+}
diff --git a/libstdc++-v3/testsuite/performance/23_containers/hash_clear/ru=
n b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/run
new file mode 100755
index 00000000000..06a15e57644
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/23_containers/hash_clear/run
@@ -0,0 +1,14 @@
+#/bin/bash
+for cache in "" "_nc"; do
+ for ty in int str; do=20
+ for buckets in 1000 500 100 50 30 10 5; do # thousands
+ for ratio in 100 50 35 20 16 12 10 7 5; do # buckets / element
+=09bux=3D$((buckets*1000))
+=09echo -n ${ty}${cache} ${buckets}k $ratio " "$((bux/ratio)) " "=20
+=09a=3D$(./bench_${ty}_walk${cache} $bux $ratio)
+=09echo -n $a " "
+=09b=3D$(./bench_${ty}_fill${cache} $bux $ratio)
+=09r=3D$((100 * a / b))
+=09s=3D ; if ((r < 101)); then s=3D'*'; fi
+=09echo $b $r% "$s"
+done; echo; done; done; done
--=20
2.55.0