[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:
PR libstdc++/67922
* include/bits/hashtable.h (clear): Special-case sparse population.
* testsuite/performance/23_containers/hash_clear/README: Add.
* testsuite/performance/23_containers/hash_clear/Makefile: Add.
* testsuite/performance/23_containers/hash_clear/hashbench.cc: Add.
* testsuite/performance/23_containers/hash_clear/bench_int.cc: Add.
* testsuite/performance/23_containers/hash_clear/bench_str.cc: Add.
* 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_clear/Makefile
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_clear/README
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_clear/bench_int.cc
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_clear/bench_str.cc
create mode 100644 libstdc++-v3/testsuite/performance/23_containers/hash_clear/hashbench.cc
create mode 100755 libstdc++-v3/testsuite/performance/23_containers/hash_clear/run
@@ -2778,8 +2778,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_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 = _GLIBCXX_HASH_CLEAR_THRESHOLD;
+ if (__threshold != 0 && _M_bucket_count / __threshold < _M_element_count)
+ { // Avoid computing hashes.
+ this->_M_deallocate_nodes(_M_begin());
+ std::fill_n(_M_buckets, _M_bucket_count, nullptr);
+ }
+ else for (auto __n = this->_M_begin(); __n != nullptr;)
+ {
+ auto __tmp = __n;
+ __n = __n->_M_next();
+ _M_buckets[_M_bucket_index(*__tmp)] = nullptr;
+ this->_M_deallocate_node(__tmp);
+ }
_M_element_count = 0;
_M_before_begin._M_nxt = nullptr;
}
new file mode 100644
@@ -0,0 +1,56 @@
+CACHE_SIZE=16 # Megabytes of L3 cache.
+THREADS=4
+FIRST_CORE=0 # Run on cores [0..THREADS).
+CACHELINE=64 # Size of cache line, 128 on POWER.
+
+THR_N=-DTHREADS=$(THREADS)
+THR_1=-DTHREADS=1
+# CXX=
+CXXFLAGS=-W -Wall -O2 -g -std=c++26 \
+ -DCACHELINE=$(CACHELINE) \
+ -DCACHE_SIZE=$(CACHE_SIZE) \
+ -DFIRST_CORE=$(FIRST_CORE)
+
+run: all; bash run
+
+ALL = bench_int_walk \
+ bench_int_fill \
+ bench_str_walk \
+ bench_str_fill \
+ bench_int_walk_nc \
+ bench_int_fill_nc \
+ bench_str_walk_nc \
+ bench_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
+ $(CXX) $(CXXFLAGS) $(THR_N) -o $@ $^
+
+bench_int_fill: bench_int.cc hashbench.cc
+ $(CXX) $(CXXFLAGS) $(THR_N) -DFILL -o $@ $^
+
+bench_str_walk: bench_str.cc hashbench.cc
+ $(CXX) $(CXXFLAGS) $(THR_N) -o $@ $^
+
+bench_str_fill: bench_str.cc hashbench.cc
+ $(CXX) $(CXXFLAGS) $(THR_N) -DFILL -o $@ $^
+
+# These run without cache interference.
+
+bench_int_walk_nc: bench_int.cc hashbench.cc
+ $(CXX) $(CXXFLAGS) $(THR_1) -o $@ $^
+
+bench_int_fill_nc: bench_int.cc hashbench.cc
+ $(CXX) $(CXXFLAGS) $(THR_1) -DFILL -o $@ $^
+
+bench_str_walk_nc: bench_str.cc hashbench.cc
+ $(CXX) $(CXXFLAGS) $(THR_1) -o $@ $^
+
+bench_str_fill_nc: bench_str.cc hashbench.cc
+ $(CXX) $(CXXFLAGS) $(THR_1) -DFILL -o $@ $^
new file mode 100644
@@ -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=67922> 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%
+int 100k 50 2000 23923 17621 135%
+int 100k 35 2857 17774 14033 126%
+int 100k 20 5000 9382 7817 120%
+int 100K 16 6250 6678 6015 111%
+int 100k 12 8333 4260 4766 89% *
+int 100k 10 10000 4183 4079 102%
+int 100k 7 14285 3095 2909 106%
+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.
new file mode 100644
@@ -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 = size / element_count;
+ while (!flag.load(std::memory_order::acquire))
+ {
+ for (std::size_t i = 0; i != element_count; ++i)
+ set.insert(i * step);
+ set.clear();
+ ++count;
+ }
+}
new file mode 100644
@@ -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==(S const&) const = 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 = 0; i != element_count; ++i)
+ set.emplace(i);
+ set.clear();
+ ++count;
+ }
+}
new file mode 100644
@@ -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 = CACHE_SIZE * 1024 * 1024;
+const unsigned cacheline_size = CACHELINE;
+const unsigned first_core = FIRST_CORE;
+const unsigned threads = THREADS;
+
+unsigned buckets = l3_cache_size / sizeof(int*);
+unsigned ratio = 16; // buckets per element
+alignas(cacheline_size) std::atomic<int> stop_flag{0};
+
+struct alignas(cacheline_size) Ctx
+{
+ unsigned id;
+ unsigned count = 0;
+ ::pthread_t thr{};
+};
+
+struct alignas(cacheline_size) Cacheline
+{
+ std::atomic<unsigned> words[cacheline_size / sizeof(unsigned)];
+};
+
+void* run(void* in)
+{
+ auto& ctx = *(Ctx*)in;
+ if (ctx.id >= ::threads) exit(1);
+ ::cpu_set_t cpu_set; CPU_ZERO(&cpu_set);
+ CPU_SET(first_core + ctx.id, &cpu_set);
+ if (0 != ::pthread_setaffinity_np(ctx.thr, sizeof(cpu_set), &cpu_set))
+ ::exit(1);
+ const std::size_t size = l3_cache_size / cacheline_size;
+ if (ctx.id != 0)
+ {
+ // Clobber L3 cache continually.
+ Cacheline* a = new Cacheline[size];
+ while (!stop_flag.load(std::memory_order::acquire)) {
+ // walk through memory clobbering each cache line.
+ for (std::size_t i = 0; i != size; ++i) {
+ a[i].words[0].store(i+ctx.count, std::memory_order::relaxed);
+ }
+ ++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 = ::atoi(av[1]);
+ if (buckets < 1000) exit(1);
+ if (ac > 2) ratio = ::atoi(av[2]);
+ if (ratio < 1) exit(1);
+ Ctx ctxs[::threads];
+ for (unsigned id = ::threads; id-- != 0;)
+ {
+ ctxs[id].id = id;
+ if (0 != ::pthread_create(&ctxs[id].thr, nullptr, ::run, ctxs + id))
+ exit(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";
+}
new file mode 100755
@@ -0,0 +1,14 @@
+#/bin/bash
+for cache in "" "_nc"; do
+ for ty in int str; do
+ 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
+ bux=$((buckets*1000))
+ echo -n ${ty}${cache} ${buckets}k $ratio " "$((bux/ratio)) " "
+ a=$(./bench_${ty}_walk${cache} $bux $ratio)
+ echo -n $a " "
+ b=$(./bench_${ty}_fill${cache} $bux $ratio)
+ r=$((100 * a / b))
+ s= ; if ((r < 101)); then s='*'; fi
+ echo $b $r% "$s"
+done; echo; done; done; done