[PATCH v2 3/3] Mutex: Optimize adaptive spin algorithm
Kemi Wang
kemi.wang@intel.com
Wed Apr 25 02:59:00 GMT 2018
The pthread adaptive spin mutex spins on the lock for a while before
calling into the kernel to block. But, in the current implementation of
spinning, the spinners go straight back to LLL_MUTEX_TRYLOCK(cmpxchg) when
the lock is contended, it is not a good idea on many targets as that will
force expensive memory synchronization among processors and penalize other
running threads. For example, it constantly floods the system with "read
for ownership" requests, which are much more expensive to process than a
single read. Thus, we only use MO read until we observe the lock to not be
acquired anymore, as suggested by Andi Kleen.
Usually, it is useless to go on spinning on the lock if fail to acquire the
lock when lock is available. That's because the spinner probably does not
have the possibility to acquire the lock during the spin process in case of
severe lock contention. Therefore, it would be better to call into the
kernel to block the thread, as suggested by Tim Chen and we can gain the
benefit at least from:
a) save the CPU time;
b) save power budget;
c) reduce the overhead of cache line bouncing during the spinning.
Test machine:
2-sockets Skylake platform, 112 cores with 62G RAM
Test case: mutex-adaptive-thread (Contended pthread adaptive spin mutex
with global update)
Usage: make bench BENCHSET=mutex-adaptive-thread
Test result:
+----------------+-----------------+-----------------+------------+
| Configuration | Base | Head | % Change |
| | Total iteration | Total iteration | base->head |
+----------------+-----------------+-----------------+------------+
| | Critical section size: 1x |
+----------------+------------------------------------------------+
|1 thread | 7.06542e+08 | 7.08998e+08 | +0.3% |
|2 threads | 5.73018e+07 | 7.20815e+07 | +25.6% |
|3 threads | 3.78511e+07 | 1.15544e+08 | +205.3% |
|4 threads | 2.28214e+07 | 6.57055e+07 | +187.9% |
|28 threads | 1.68839e+07 | 5.19314e+07 | +207.6% |
|56 threads | 1.84983e+07 | 5.06522e+07 | +173.8% |
|112 threads | 2.3568e+07 | 4.95375e+07 | +110.2% |
+----------------+------------------------------------------------+
| | Critical section size: 10x |
+----------------+------------------------------------------------+
|1 thread | 5.40274e+08 | 5.47189e+08 | +1.3% |
|2 threads | 4.55684e+07 | 6.03275e+07 | +32.4% |
|3 threads | 3.05702e+07 | 1.04035e+08 | +240.3% |
|4 threads | 2.17341e+07 | 5.57264e+07 | +156.4% |
|28 threads | 1.39503e+07 | 4.53525e+07 | +225.1% |
|56 threads | 1.50154e+07 | 4.16203e+07 | +177.2% |
|112 threads | 1.90175e+07 | 3.88308e+07 | +104.2% |
+----------------+------------------------------------------------+
| | Critical section size: 100x |
+----------------+------------------------------------------------+
|1 thread | 7.23372e+07 | 7.25654e+07 | +0.3% |
|2 threads | 2.67302e+07 | 2.40265e+07 | -10.1% |
|3 threads | 1.89936e+07 | 2.70759e+07 | +42.6% |
|4 threads | 1.62423e+07 | 2.25097e+07 | +38.6% |
|28 threads | 9.85977e+06 | 1.59003e+07 | +61.3% |
|56 threads | 8.11471e+06 | 1.6344e+07 | +101.4% |
|112 threads | 8.58044e+06 | 1.53827e+07 | +79.3% |
+----------------+------------------------------------------------+
| | Critical section size: 1000x |
+----------------+------------------------------------------------+
|1 thread | 8.16913e+06 | 8.16126e+06 | -0.1% |
|2 threads | 5.82987e+06 | 5.92752e+06 | +1.7% |
|3 threads | 6.05125e+06 | 6.37068e+06 | +5.3% |
|4 threads | 5.91259e+06 | 6.27616e+06 | +6.1% |
|28 threads | 2.40584e+06 | 2.60738e+06 | +8.4% |
|56 threads | 2.32643e+06 | 2.3245e+06 | -0.1% |
|112 threads | 2.32366e+06 | 2.30271e+06 | -0.9% |
+----------------+-----------------+-----------------+------------+
* nptl/pthread_mutex_lock.c: Optimize adaptive spin mutex
ChangLog:
V1->V2: fix format issue
Suggested-by: Andi Kleen <andi.kleen@intel.com>
Suggested-by: Tim Chen <tim.c.chen@intel.com>
Signed-off-by: Kemi Wang <kemi.wang@intel.com>
---
ChangeLog | 4 ++++
nptl/pthread_mutex_lock.c | 32 ++++++++++++++++++--------------
2 files changed, 22 insertions(+), 14 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index 76d2628..4c81693 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2018-04-24 Kemi Wang <kemi.wang@intel.com>
+ * nptl/pthread_mutex_lock.c: Optimize adaptive spin mutex.
+
+2018-04-24 Kemi Wang <kemi.wang@intel.com>
+
* benchtests/bench-mutex-adaptive-thread.c: Microbenchmark for adaptive
spin mutex.
* benchmark/Makefile: Add adaptive spin mutex benchmark.
diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c
index 1519c14..3442c58 100644
--- a/nptl/pthread_mutex_lock.c
+++ b/nptl/pthread_mutex_lock.c
@@ -26,6 +26,7 @@
#include <atomic.h>
#include <lowlevellock.h>
#include <stap-probe.h>
+#include <pthread_mutex_conf.h>
#ifndef lll_lock_elision
#define lll_lock_elision(lock, try_lock, private) ({ \
@@ -124,21 +125,24 @@ __pthread_mutex_lock (pthread_mutex_t *mutex)
if (LLL_MUTEX_TRYLOCK (mutex) != 0)
{
int cnt = 0;
- int max_cnt = MIN (MAX_ADAPTIVE_COUNT,
- mutex->__data.__spins * 2 + 10);
- do
- {
- if (cnt++ >= max_cnt)
- {
- LLL_MUTEX_LOCK (mutex);
- break;
- }
- atomic_spin_nop ();
- }
- while (LLL_MUTEX_TRYLOCK (mutex) != 0);
+ int max_cnt = MIN (__mutex_aconf.spin_count,
+ mutex->__data.__spins * 2 + 100);
+
+ /* MO read while spinning */
+ do
+ {
+ atomic_spin_nop ();
+ }
+ while (atomic_load_relaxed (&mutex->__data.__lock) != 0 &&
+ ++cnt < max_cnt);
+ /* Try to acquire the lock if lock is available or the spin count
+ * is run out, call into kernel to block if fails
+ */
+ if (LLL_MUTEX_TRYLOCK (mutex) != 0)
+ LLL_MUTEX_LOCK (mutex);
- mutex->__data.__spins += (cnt - mutex->__data.__spins) / 8;
- }
+ mutex->__data.__spins += (cnt - mutex->__data.__spins) / 8;
+ }
assert (mutex->__data.__owner == 0);
}
else
--
2.7.4
More information about the Libc-alpha
mailing list