Small Mutex Implementation?

Question

The relatively large size of std::mutex on different platforms (e.g. 40 or even 80 bytes) is often explained as ensuring the mutexes don't occupy the same cache-lines and so don't incur logically unnecessary fetches and synchronization activity.

However a std::mutex is commonly embedded in a larger object and its very size is (almost by design) a detriment to true sharing.

What is a good designs for a minimal mutex?

A one-byte spin-lock design is fairly trivial but a 'true' mutex in which threads suspend until notified is more of a challenge. I can't find a portable way for a thread to notify another thread to unsuspend/unsleep without resorting to a mutex.

You can work around that by using std::unique_ptr if you really care about the in-place size — ratchet freak, Apr 05 '17 at 09:15
Note that mutexes are typically not movable, so adding an indirection is often helpful, even when the mutex itself needs little memory. — CodesInChaos, Apr 05 '17 at 09:20
@ratchetfreak But an indirection just adds a further overhead and (practically) guarantees a failure of true-sharing. I don't see how that helps anything. — Persixty, Apr 05 '17 at 10:02
@CodesInChaos The normal object semantics would be to not try and copy/assign the mutex of a given object. — Persixty, Apr 05 '17 at 10:04
The overhead of the mutex itself is probably larger than any cache miss of the pointer chase. — ratchet freak, Apr 05 '17 at 10:12

CodesInChaos · Accepted Answer · 2017-06-20T15:18:44.400

2

WTF::Lock, the locking library used by WebKit sounds like what you need. The link above describes the design in detail.

The most important points for you are:

The Mutex only uses one byte, which is enough for a spin-lock.
It switches from spin-locking to blocking for longer waits. This is implemented via thread queues which are separated from the mutex itself.

I'm not sure how usable the library is without WebKit, but the design principles described in the linked post are generally applicable. For example there is a popular Rust locking library with the same design.

edited Jun 20 '17 at 15:18

answered Apr 05 '17 at 09:38

CodesInChaos

5,697
4
19
26

Thanks. That may be useful. It's certainly a where with the number of threads far fewer than objects the chances of contention are normally low. It's also true that many critical sections will be short but could be long. So an adaptive model that spins for a while before 'really' blocking would help. – Persixty Apr 05 '17 at 10:29
I've had a look now and the answer is "very useful". The juicy bit is down in an object called the ParkingLot. For each 'parked' thread create a thread-local std::mutex and a std::condition_variable that you notify to unpark the thread. In the case of WebKit this is done via a global hash-table but there are plenty of alternatives about how a thread releasing a lock unparks threads queued up behind it. Implementation is even easier with the C++ `thread_local` storage class specifier. :) https://trac.webkit.org/browser/webkit/releases/WebKitGTK/webkit-2.14/Source/WTF/wtf/ParkingLot.cpp – Persixty Apr 06 '17 at 11:20

Small Mutex Implementation?

1 Answers1