Summary:
========

The way I understand the code in 
https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/atomic_wait.h#L251-L258
and the article at
https://developers.redhat.com/articles/2022/12/06/implementing-c20-atomic-waiting-libstdc#
is that for std::atomic<uint64_t>::wait the implementation uses 16 elements and maps the address of the actual atomic to the element by a very simple hash function:
```
      static __waiter_pool_base&
      _S_for(const void* __addr) noexcept
      {
	constexpr uintptr_t __ct = 16;
	static __waiter_pool_base __w[__ct];
	auto __key = (uintptr_t(__addr) >> 2) % __ct;
	return __w[__key];
      }
```
This seems to be a very poor choice in my experience, as it only depends on (4 of) the lowest 6 bits, because data structures used in multi-threaded apps, and in particular, data structures which use atomics, often use cache-line alignment to avoid "false sharing", and because a cache line usually has 64 bytes, thus the __addr%64 is usually the same value for all instances of a given class. Also, quite often: 0.
This is a performance problem, as it then leads to spurious wake ups.

Background:
===========

I am working on InnoDB engine for MySQL, which uses a very old `struct os_event` which among other things lets people call epoch=reset(), set(), wait_low(epoch). This structure is used a lot in other old classes such as ib_mutex_t or rw_lock_t to notify threads waiting for a latch that it got released. As each page in Buffer Pool has several such latches, and BP size can be in TBs, one can imagine we have a lot of os_event-s. They are implemented as a combination of boolean flag, uint64_t counter, a native mutex, and a native cond var, leading to a huge sizeof(os_event) (upwards of 96 bytes on Linux) and a lot of non-trivial code to maintain. In 2020 [Facebook proposed](https://bugs.mysql.com/bug.php?id=102045) to use an idea similar to [WebKit's Parking Lot](https://db.in.tum.de/~boettcher/locking.pdf), which is to have a pool of such structs, and somehow reuse/share them. This would make the logic even more complicated, but would save a lot of memory (their claim: 1GB).

Recently MySQL's codebase moved to C++20, and I saw an opportunity to replace all of this custom logic with std::atomic<uint64_t> as there is a natural mapping:
```
epoch=reset() --> counter=load(), 
set() --> fetch_add(1)+notify_all(), 
wait_low(counter) --> wait(epoch).
```
This is not exactly the same thing, but close enough semantically, so I've implemented the change and run sysbench OLTP-RW test suite, and saw...disaster:
```
$num_of_runs $median $median_abs_diff ($min < $avg < $max) "$version"
pareto 64
6 27800 +- 113 ( 27423 < 27739 < 27943 ) "use std::atomic instead of os_event_t + 32-bit"
6 27676 +- 255 ( 27401 < 27696 < 28019 ) "use std::atomic instead of os_event_t"
6 27527 +- 163 ( 27171 < 27545 < 27806 ) "baseline"

pareto 1024
9 32234 +- 113 ( 31930 < 32244 < 32555 ) "use std::atomic instead of os_event_t + 32-bit"
9 32080 +- 134 ( 31946 < 32137 < 32460 ) "baseline"
9 21791 +- 677 ( 19965 < 21408 < 22486 ) "use std::atomic instead of os_event_t"

uniform 64
9 27326 +- 170 ( 26799 < 27287 < 27666 ) "use std::atomic instead of os_event_t + 32-bit"
9 27264 +- 98 ( 26677 < 27162 < 27453 ) "use std::atomic instead of os_event_t"
9 27246 +- 195 ( 26758 < 27206 < 27561 ) "baseline"

uniform 1024
9 35766 +- 125 ( 35246 < 35671 < 36173 ) "use std::atomic instead of os_event_t + 32-bit"
9 35623 +- 146 ( 35446 < 35669 < 36150 ) "baseline"
9 23631 +- 313 ( 22835 < 23603 < 24399 ) "use std::atomic instead of os_event_t"
```
This is a machine with 96 CPUs, and we can see that for 1024 threads the impact of replacing the default os_event_t with atomic<uint64_t> is changing the number of transactions per second from 35.6K to 23.6K.

A flame graphs' diff showed a lot of time spent in `syscall` during latch acquistions, i.e. when calling "wait".
I guess this is not so much about the duration, but about frequency of these calls, as there's a retry `while` loop in atomic_wait.h which calls futex syscall again whenever a spurious wake up occurs.
At any rate, the problem is somewhere in the handling of 64-bit atomics, because changing the counter to std::atomic<uint32_t> made the problem go away as you can see.
I'd rather use uint64_t to make ABA almost impossible.

Proposed fix:
=============
How about:
a) using %17 instead of %16? 
b) looking at the next 4 bits?
c) pre-multiply the __addr by a random odd constant and take the top 4 bits?
d) use a real hash function, such as _mm_crc32_u64?
e) something more galaxy brainded like using a lock-free hashmap from actively used addr values to a pool of the size equal to number of threads?

Personally, I'd give (a) a try - division by a contexpr value shouldn't hurt much, and we are about to do a costly syscall anyway.