3 ms·

An interesting thing to try with the two-bit mutex is to add exponential back off. I suspect it’ll dramatically improve the latency under contention. Another i

by sakras 4y ago

An interesting thing to try with the two-bit mutex is to add exponential back off. I suspect it’ll dramatically improve the latency under contention. Another interesting thing to point out is that there seems to be a crossover point between when using an array of std::mutex is better vs having an array of these pointer-locks. Imagine you have an array of pointers to objects that you want to lock. With the pointer locks, you’ll have 8 mutexes per cache line, which for small arrays will probably have a high degree of false sharing. With an array of std::mutex, you’d probably pad them out to 64 bytes and there would be no false sharing. But for larger arrays (assuming a uniform distribution of accesses), the probability of false sharing would be low enough that the pointer-mutex would be faster. The last thing I have to say is that I’ve been reading a lot about memory models lately, and I’ve become terrified of trying to mix TLA+ and non-seq_cst memory orders. Since TLA+ produces a global total order of actions, you still haven’t quite properly model checked your program if you haven’t modeled C++’s memory in your spec. That said, you can probably get away with it most of the time (especially on x86).

jeffbee 4y ago
Just putting an x86 pause in your spin loop will dramatically improve the mean latency under contention, but it also leads to huge tail latency explosions because it has no fairness mechanism.
- sakras 4y ago
  You can also dramatically reduce the latency by testing before attempting the CAS, which will switch a lot of cache line requests into Shares instead of Owns. I didn’t see it in this implementation. But the point of the wait/notify in the post to sleep if I understand correctly. My guess is there is some amount of spurious waking up that’s happening, or multiple threads are woken up by the notify_one (it only guarantees at least one is woken up!) An exponential backoff would reduce the probability of these spurious wakeups colliding dramatically. On a separate note, fairness isn’t always required, just throughput. If you need predictable latency then this lock won’t work for you, but in this case optimizing for mean latency seems more worthwhile.

by sakras 4y ago

jeffbee 4y ago

Just putting an x86 pause in your spin loop will dramatically improve the mean latency under contention, but it also leads to huge tail latency explosions because it has no fairness mechanism.

sakras 4y ago
You can also dramatically reduce the latency by testing before attempting the CAS, which will switch a lot of cache line requests into Shares instead of Owns. I didn’t see it in this implementation. But the point of the wait/notify in the post to sleep if I understand correctly. My guess is there is some amount of spurious waking up that’s happening, or multiple threads are woken up by the notify_one (it only guarantees at least one is woken up!) An exponential backoff would reduce the probability of these spurious wakeups colliding dramatically. On a separate note, fairness isn’t always required, just throughput. If you need predictable latency then this lock won’t work for you, but in this case optimizing for mean latency seems more worthwhile.