[PATCH] *BAD* implementation of Mutex with spinning

[Nadav Har'El]

This is a bad patch, to serve as a lesson, not to be used ;-)

This is another implementation of a mutex with a bit of spinning, using
a completely different technique from the previously posted patched.

In this patch, when a lock() sees the mutex is contended it doesn't spin
on the "handoff" protocol. Rather, it goes on to put itself on the wait
queue normally, and spins checking if it was woken up, before actually
sleeping. The thinking was that if someone wakes up during that spinning,
the wakeup is much faster (doesn't involve a context switch or an IPI -
just checking if waiter.t became 0).

Unfortunately, the performance of this patch sucks pretty bad:

For the 2 and 4-thread lock/unlock-loop benchmark, performance is
significantly improved over the no-spinning baseline, but it unfortunately
slower than the spinlock or our previous spinning mutex patch.
While we avoid a real context switch, we still pay the costs of several
additional atomic operations - to push and pop the queue, to set the
thread state, etc.

For the 20-thread benchmark, this patch makes it significantly *slower*!
The problem is that the thread doing the spinning has just now put itself
as the *last* of 20 waiting on the wait queue, so it will likely futily
spin, wasting CPU, until the end of the spin, without being woken up.
We can probably avoid this slowdown, by not spinning if the wait queue
is "too long" (?), but this technique will never make the 20-thread
benchmark run more efficiently than the non-spinning mutex.

Please do not commit this patch, but as usual, feel free to try it on
your favorite benchmark.

Signed-off-by: Nadav Har'El <n...@cloudius-systems.com>
---
core/lfmutex.cc | 22 ++++++++++++++++++++++
1 file changed, 22 insertions(+)

--- .before/core/lfmutex.cc 2014-07-29 00:32:56.896608299 +0300
+++ .after/core/lfmutex.cc 2014-07-29 00:32:56.896608299 +0300
@@ -110,6 +110,28 @@ void mutex::lock()
}
}
}
+ // Before going to sleep, try to spin a bit waiting for another thread
+ // to wake us up. The idea is that waking us up while we're still awake is
+ // much more efficient, as it involves no context switches or IPIs.
+ // FIXME: do not spin on UP.
+ for (register int c = 0; c < 1000; c++) {
+ // If the lock holder got preempted, we would better be served
+ // by going to sleep and let it run again, than futile spinning.
+ // Especially if the lock holder wants to run on this CPU.
+ // FIXME: what if thread exits while we want to check if it's
+ // running? as soon as we find holder, it might already be gone :(
+ auto holder = owner.load(std::memory_order_relaxed);
+ if (holder && !holder->running()) {
+ break;
+ }
+ // waiter.t is not an atomic variable, so the compiler may cache
+ // it in this loop. Barrier makes sure it doesn't.
+ if (waiter.woken()) {
+ break;
+ }
+ barrier();
+ asm volatile ("pause");
+ }

// Wait until another thread pops us from the wait queue and wakes us up.
trace_mutex_lock_wait(this);