[PATCH] libstdc++: Use proper hash function for atomic::wait state [PR115955]
Jonathan Wakely
jwakely@redhat.com
Mon Oct 5 12:55:30 GMT 2026
On Mon, 5 Oct 2026 at 13:41, Tomasz Kaminski <tkaminsk@redhat.com> wrote:
>
>
>
> On Mon, Oct 5, 2026 at 1:40 PM Jonathan Wakely <jwakely@redhat.com> wrote:
>>
>> 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.
>
> Looks good with small comment below.
>>
>>
>> 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;
>
> I was going to suggest that could reinterpret cast and mix the bits (same as below) of the address of
> size static variable from above in that case. But that would only benefit platforms that have address
> space randomization (so library is loaded at different address), but does not have any of the random devices.
> Which does not seem likely, so I think zero would be essentially equivalent.
Yes, an interesting idea, but I agree it probably isn't likely to have
any practical impact.
The per-process seed is there to mix things up a little more in case
an attacker can somehow control the addresses at which atomics are
placed, e.g. if they're on the heap and the attacker can make the
allocation pattern predictable. The extra seed might prevent a DoS in
that case and seems worthwhile. But targets that don't have arc4random
&& (compile the library with -fno-exceptions || get an exception from
std::random_device) are likely to be small embedded targets, where
using the heap for an unbounded number of atomics is unlikely. So I
figured 0 was good enough for that case.
>
>> +#endif
>> + }
>> +
>> + const unsigned seed{ gen_seed() }; // Per-process random seed.
>
> Gen seed generates uin32_t but this variable is unsigned, I think it would be better if they types would match.
Good catch, thanks. That would have been a narrowing conversion for
targets with 16-bit int. I've changed the data member to be uint32_t
as well.
>>
>> +
>> + 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
>>
More information about the Libstdc++
mailing list