The table of __waitable_state objects used by std::atomic::wait is
indexed based on the address of the atomic being waited on, but the
index is computed using `(uintptr_t(addr) >> 2) % 16`. This has very
non-uniform properties and results in high numbers of collisions.
This commit uses an efficient hash function that mixes the high bits of
the address and cascades them to the low bits. This should have better
distribution and avoid the pathological case where every atomic object
collides on the same wait state.
The hash function also uses a per-process seed initialized on first use.
That seed comes from arc4random if available, or std::random_device.
If neither works, no seed is used.
Before this change collisions in the wait state table meant that
distinct atomic objects would share the same proxy wait state and a
notify_one() call would wake threads waiting on completely separate
atomic objects. When the number of threads was smaller than the core
count, the false sharing "only" resulted in other CPUs spinning on the
unrelated atomics that were woken even though their atomic didn't change
value. This wastes cycles, but for some naive benchmarks it looks like a
win because all the atomics are kept hot and are acting like a spinlock
with no back off, never actually doing a futex wait before being
interrupted again. When the number of threads exceeds the available
cores the old code has disastrous behaviour, because there aren't enough
cores to service the thundering herd that wakes up on every notify. The
CPU usage for a single notify scales with the number of waiters and
performance drops when every waiter has to wait to get scheduled on a
CPU.
After this change collisions in the wait state are less likely, avoiding
the pathological case where every object collides with every other
because they've been intentionally separated by 64 bytes to sit on
separate cachelines. Now waking one waiter doesn't affect every other
waiter, so most waiters stay blocked in the kernel. The CPU usage for a
single notify is flat and the latency of a notify is approximately just
the system call overhead for the futex wake.
For a benchmark with 17 threads doing wait/notify on std::atomic<bool>,
my laptop sees a 30x reduction in CPU time, and almost 2x reduction in
latency per-notify. The numbers are obviously very workload dependent,
but the code is now behaving as it was always intended to.
For non-proxy waits (e.g. std::atomic<int> where the atomic is used as a
futex directly) the benefit of this change is much smaller. Even when
there is a collision on the wait state, that's only used for contention
tracking not as the futex object that the real wait/wake syscalls act
on. But the change doesn't hurt the non-proxy case, so is still a
significant improvement overall.
libstdc++-v3/ChangeLog:
PR libstdc++/115955
* src/c++20/atomic.cc (__waitable_state::_S_state_for): Use a
real hash function to map addresses to waitable states.
---
Tested x86_64-linux.
libstdc++-v3/src/c++20/atomic.cc | 64 ++++++++++++++++++++++++++++----
1 file changed, 57 insertions(+), 7 deletions(-)
diff --git a/libstdc++-v3/src/c++20/atomic.cc b/libstdc++-v3/src/c++20/atomic.cc
index 3fbc05c2e682..1182cda43b4a 100644
--- a/libstdc++-v3/src/c++20/atomic.cc
+++ b/libstdc++-v3/src/c++20/atomic.cc
@@ -28,6 +28,7 @@
#include <atomic>
#include <bits/atomic_timed_wait.h>
#include <utility> // cmp_less
+#include <numbers> // numbers::phi
#include <cstdint> // uint32_t, uint64_t, uintptr_t
#include <climits> // INT_MAX
#include <cerrno> // errno, ETIMEDOUT, etc.
@@ -35,6 +36,12 @@
#include <bits/functexcept.h> // __throw_system_error
#include <bits/functional_hash.h>
+#ifdef _GLIBCXX_HAVE_ARC4RANDOM
+# include <stdlib.h> // arc4random
+#else
+# include <random> // random_device
+#endif
+
#ifdef _GLIBCXX_HAVE_LINUX_FUTEX
# include <sys/syscall.h> // SYS_futex
# include <unistd.h>
@@ -332,16 +339,59 @@ namespace
return __res != 0;
}
+ class Table;
+
static __waitable_state&
- _S_state_for(const void* __addr) noexcept
- {
- constexpr __UINTPTR_TYPE__ __ct = 16;
- static __waitable_state __w[__ct];
- auto __key = ((__UINTPTR_TYPE__)__addr >> 2) % __ct;
- return __w[__key];
- }
+ _S_state_for(const void* addr) noexcept;
};
+ // This aggregates the array of states and the seed into a single object,
+ // so that there is only one static initialization guard needed.
+ class __waitable_state::Table
+ {
+ static constexpr size_t size = 16;
+ __waitable_state wait_states[size];
+
+ static uint32_t gen_seed()
+ {
+#ifdef _GLIBCXX_HAVE_ARC4RANDOM // glibc 2.36 and BSD
+ // Avoid the overhead of constructing+destroying std::random_device.
+ return arc4random();
+#else
+# if __cpp_exceptions
+ // Use the default platform-specific source of entropy.
+ try { return std::random_device{}(); } catch (...) { }
+# endif
+ return 0;
+#endif
+ }
+
+ const unsigned seed{ gen_seed() }; // Per-process random seed.
+
+ static size_t
+ hash(const void* p, size_t seed) noexcept
+ {
+ size_t x = reinterpret_cast<uintptr_t>(p);
+ x ^= seed;
+ x ^= x >> (__SIZE_WIDTH__ / 2 + 1);
+ x *= size_t(__SIZE_MAX__ / std::numbers::phi);
+ x ^= x >> (__SIZE_WIDTH__ / 2 - 1);
+ return x;
+ }
+
+ public:
+ __waitable_state&
+ operator[](const void* p)
+ { return wait_states[hash(p, seed) % size]; }
+ };
+
+ inline __waitable_state&
+ __waitable_state::_S_state_for(const void* addr) noexcept
+ {
+ static Table table;
+ return table[addr];
+ }
+
// Scope-based contention tracking.
struct scoped_wait
{
--
2.55.0
