https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115955
--- Comment #6 from GCC Commits <cvs-commit at gcc dot gnu.org> --- The releases/gcc-16 branch has been updated by Jonathan Wakely <[email protected]>: https://gcc.gnu.org/g:888cefc00f16d9199372b2dd733c7fdd390adf99 commit r16-9792-g888cefc00f16d9199372b2dd733c7fdd390adf99 Author: Jonathan Wakely <[email protected]> Date: Tue May 5 21:34:41 2026 +0100 libstdc++: Use proper hash function for atomic::wait state [PR115955] 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. Reviewed-by: Tomasz KamiÅski <[email protected]> (cherry picked from commit 4b690722a0585c50f033deec5637760a671c72f0)
