libstdc++: Use proper hash function for atomic::wait state [PR115955]
Improves std::atomic::wait performance and correctness by using a better hash function for wait state lookups.
The hash function used for managing wait states in std::atomic::wait has been improved to reduce collisions and pathological behavior. The previous hashing scheme led to frequent collisions, causing incorrect wakeups and performance degradation, especially under high thread contention. The new hash function provides better distribution and uses a per-process seed for increased uniqueness.
In Details
The __waitable_state table in libstdc++'s implementation of std::atomic::wait was indexed using (uintptr_t(addr) >> 2) % 16, a scheme prone to high collision rates. This was particularly problematic when atomic objects were aligned on multiples of 64 bytes, causing all waiters to collide on the same wait state. This commit replaces the poor hash function with one that mixes high bits of the address and cascades them to low bits, using a per-process seed derived from arc4random or std::random_device. This significantly reduces collisions, improving correctness by preventing spuriou…
- std::atomic::wait
- A C++ standard library function that allows a thread to block efficiently until a specified atomic object changes its value or is notified. It's part of the C++20 concurrency features.
- hash function
- A function that maps input data of arbitrary size to output data of a fixed size. In data structures like hash tables, it's used to compute an index for storing and retrieving elements.
- collision
- In the context of hash tables, a collision occurs when two different keys produce the same hash value, leading to them potentially being stored in the same location.
- futex
- Fast Userspace muTeX. A Linux kernel system call that provides a basic building block for implementing locks and synchronization primitives in userspace.
- false sharing
- A performance issue in multi-core systems where different threads operating on independent data invalidate each other's cache lines, even though they are not accessing the same memory location. This happens when unrelated data resides on the same cache line.
- cache line
- The smallest unit of data that can be transferred between the main memory and the CPU cache. Modern processors fetch data in cache line sized blocks.
- arc4random
- A pseudorandom number generator function available on some Unix-like systems, known for its speed and quality.
- std::random_device
- A C++ class that produces non-deterministic random numbers, often used to seed pseudorandom number generators.