Optimize adaptive spinning mutex code

Change the adaptive spinning code to be elapsed time based instead of
iteration based. The new approach will quickly reduce the amount of
allowed spinning time when it detects that lock contention is resolved
by waiting instead of spinning. We get better results by dynamically
adjusting for elapsed running time instead of trying to fine tune
iteration counts that won't work for all CPU types, speeds, etc.

From observation, lock performance suffers if the spin time is higher
than the minimum wait time. Because of this, QMutex never increases the
spin time, it only reduces the spin time to the minimum observed wait time.
For very long wait times, we disable spinning completely (and always resolve
contention by waiting).

Use QThread::yieldCurrentThread() when spinning on a contended mutex. Comment
from the code: be a good citizen... yielding lets something else run if
there is something to run, but may also relieve memory pressure if not.

Reviewed-by: joao

4 files changed, 25 insertions, 19 deletions

diff --git a/src/corelib/thread/qmutex.cpp b/src/corelib/thread/qmutex.cpp
index 54b3ed4..72f87b7 100644
--- a/src/corelib/thread/qmutex.cpp
+++ b/src/corelib/thread/qmutex.cpp
@@ -45,6 +45,7 @@
 
 #ifndef QT_NO_THREAD
 #include "qatomic.h"
+#include "qelapsedtimer.h"
 #include "qthread.h"
 #include "qmutex_p.h"
 
@@ -439,31 +440,34 @@ void QMutex::lockInternal()
         return;
     }
 
-    int spinCount = 0;
-    int lastSpinCount = d->lastSpinCount;
-
-    enum { AdditionalSpins = 20, SpinCountPenalizationDivisor = 4 };
-    const int maximumSpinCount = lastSpinCount + AdditionalSpins;
-
+    QElapsedTimer elapsedTimer;
+    elapsedTimer.start();
     do {
-        if (spinCount++ > maximumSpinCount) {
-            // didn't get the lock, wait for it
+        if (elapsedTimer.hasExpired(d->maximumSpinTime)) {
+            // didn't get the lock, wait for it, since we're not going to gain anything by spinning more
+            int spinTime = elapsedTimer.restart();
             bool isLocked = d->wait();
             Q_ASSERT_X(isLocked, "QMutex::lock",
                        "Internal error, infinite wait has timed out.");
             Q_UNUSED(isLocked);
 
-            // decrease the lastSpinCount since we didn't actually get the lock by spinning
-            spinCount = -d->lastSpinCount / SpinCountPenalizationDivisor;
-            break;
+            int maximumSpinTime = d->maximumSpinTime;
+            int waitTime = elapsedTimer.elapsed();
+            // adjust the spin count when spinning does not benefit contention performance
+            if (spinTime + waitTime > QMutexPrivate::MaximumSpinTimeThreshold) {
+                // long waits, stop spinning
+                d->maximumSpinTime = 0;
+            } else if (waitTime < maximumSpinTime) {
+                // never spin more than the minimum wait time (otherwise we may perform worse)
+                d->maximumSpinTime = waitTime;
+            }
+            return;
         }
+        // be a good citizen... yielding lets something else run if there is something to run, but may also relieve memory pressure if not
+        QThread::yieldCurrentThread();
     } while (d->contenders != 0 || !d->contenders.testAndSetAcquire(0, 1));
 
-    // adjust the last spin lock count
-    lastSpinCount = d->lastSpinCount;
-    d->lastSpinCount = spinCount >= 0
-                        ? qMax(lastSpinCount, spinCount)
-                        : lastSpinCount + spinCount;
+    // spinning is working, do not change the spin time
 }
 
 /*!
diff --git a/src/corelib/thread/qmutex_p.h b/src/corelib/thread/qmutex_p.h
index 2d45cfb..6de42ad 100644
--- a/src/corelib/thread/qmutex_p.h
+++ b/src/corelib/thread/qmutex_p.h
@@ -72,7 +72,9 @@ public:
     bool wait(int timeout = -1);
     void wakeUp();
 
-    volatile int lastSpinCount;
+    // half of a frame (in ms) at 60fps
+    enum { MaximumSpinTimeThreshold = 8 };
+    volatile int maximumSpinTime;
     Qt::HANDLE owner;
     uint count;
 
diff --git a/src/corelib/thread/qmutex_unix.cpp b/src/corelib/thread/qmutex_unix.cpp
index e872187..48014cc 100644
--- a/src/corelib/thread/qmutex_unix.cpp
+++ b/src/corelib/thread/qmutex_unix.cpp
@@ -74,7 +74,7 @@ static void report_error(int code, const char *where, const char *what)
 
 
 QMutexPrivate::QMutexPrivate(QMutex::RecursionMode mode)
-    : QMutexData(mode), lastSpinCount(0), owner(0), count(0)
+    : QMutexData(mode), maximumSpinTime(MaximumSpinTimeThreshold), owner(0), count(0)
 {
 #if defined(Q_OS_MAC)
     kern_return_t r = semaphore_create(mach_task_self(), &mach_semaphore, SYNC_POLICY_FIFO, 0);
diff --git a/src/corelib/thread/qmutex_win.cpp b/src/corelib/thread/qmutex_win.cpp
index c278f04..89e8b87 100644
--- a/src/corelib/thread/qmutex_win.cpp
+++ b/src/corelib/thread/qmutex_win.cpp
@@ -48,7 +48,7 @@
 QT_BEGIN_NAMESPACE
 
 QMutexPrivate::QMutexPrivate(QMutex::RecursionMode mode)
-    : QMutexData(mode), lastSpinCount(0), owner(0), count(0)
+    : QMutexData(mode), maximumSpinTime(MaximumSpinTimeThreshold), owner(0), count(0)
 {
     event = CreateEvent(0, FALSE, FALSE, 0);
     if (!event)