Add some spinning to mutex_lock()

[nyh]

When very short sections of code (e.g., set a couple of variables) are protected by mutex_lock()/mutex_unlock(), when the lock is busy it is often more efficient, instead of doing a context switch, just try locking again - the other thread will often finish already.

Some implementation ideas:

1. lockfree::mutex::lock() can, after increasing count, spin for a while while count is still > 1, and if during this short spin every time we get to count == 1, we try to take the lock (by taking the "handoff" left by the unlock(), which knows we're trying to get the lock because we increased count). And don't forget the "pause" instruction during that spin :-)
2. Probably a better alternative to the above is, instead of checking count==1 as above, check the handoff directly (see example in try_lock()) - without considering count. The reason is that two threads spinning in lock() will leave count==2 and neither of them will ever see count==1, but a handoff will occur, because unlock() sees count=2 and nobody on the queue.
3. A third alternative is not to use the handoff mechanism at all. I.e., like try_lock()'s code, don't increment count and only loop on a CAS trying to grab the lock when nobody has it. I'm not sure if this alternative is better or worse than the previous one. The loop is slower, but we don't force unlock() to use the handoff mechanism. This alternative also changes the way that lock() works in the uncontended case - previously it did fetch_add, and now we start it with compare_exchange (I don't know which is more efficient).
4. Don't forget NOT to spin on single CPU machines - it can't help :-)

An open question is for how long to spin before resorting to sleeping? Does the amount of spinning need to depend on number of processors, the lock's previous history, other heuristics, or be explicitly configured at compile-time by the programmer for each use? Some thoughts on this issue which were raised in a long email discussion we had:

1. My original thinking was that the programmer knows when critical sections are short, so he can use a different method, say lock_expect_quick(nspins) or lock_expect_quick(nanoseconds) in that case. The time of spin should be determined by the critical section's length, by the time it takes to do a context switch, or both (?).
2. Avi suggested to the above in a more OO manner, adding more types that keep mutex's original lock()/unlock() method names so that lock_guard<> and friends will continue to work. E.g., spinning_mutex. Both types of mutexes can share code using a template, e.g.,

typedef basic_mutex<contention_strategy_spin<50>> spinning_mutex;
typedef basic_mutex<contention_strategy_wait> io_mutex;
typedef basic_mutex<contention_strategy_adaptive> mutex;

1. Glauber suggested to look at the queue's length to see if other threads are waiting already, and if so, don't spin as we don't have much chance (assuming the spin length we chose is the amount of time it takes for one critical section to finish - not more than one). Getting the queue length is not easy, but we do have the "count" we can use (which, however, includes in addition to the queue length also the number of concurrent lock()s which didn't yet manage to put themselves on the queue), and we also know if the queue is empty.
2. Dor and Guy thought that spinning should be adaptive, i.e., consider how much time we spun in previous lock attempts and whether they were successful. E.g., if 100 spins were usually enough, don't spin more than that even if our maximum spin time (perhaps related to the context switch cost) is 1000 spins (i.e. previous experience showed that if after 100 spins we didn't get the lock, it won't help to wait for 1000 spins).
3. Dor and Guy thought that the spin time should be related to the number of vcpus - no spinning on one cpu (of course), spin for time x on 2 cpus, spin for x_1.5 or x_log2(4) on 4 vcpus, etc. Glauber and I thought the spin time should not depend on the number of CPUs.

[slivne]

@nyh can you please add the info we have collected on list to this issue for future reference ....

Once we submit/decide not to ... lets close this issue