Re: [PATCH v4] nptl: Add backoff mechanism to spinlock loop

["Guo, Wangyang" <wangyang.guo@intel.com>]

On 5/6/2022 6:44 AM, H.J. Lu via Libc-alpha wrote:
> On Wed, May 4, 2022 at 7:59 PM Guo, Wangyang <wangyang.guo@intel.com> wrote:
>>
>> On 5/5/2022 9:56 AM, H.J. Lu via Libc-alpha wrote:
>>> On Tue, May 3, 2022 at 8:17 PM Wangyang Guo <wangyang.guo@intel.com> wrote:
>>>>
>>>> When mutiple threads waiting for lock at the same time, once lock owner
>>>> releases the lock, waiters will see lock available and all try to lock,
>>>> which may cause an expensive CAS storm.
>>>>
>>>> Binary exponential backoff with random jitter is introduced. As try-lock
>>>> attempt increases, there is more likely that a larger number threads
>>>> compete for adaptive mutex lock, so increase wait time in exponential.
>>>> A random jitter is also added to avoid synchronous try-lock from other
>>>> threads.
>>>>
>>>> v2: Remove read-check before try-lock for performance.
>>>>
>>>> v3:
>>>> 1. Restore read-check since it works well in some platform.
>>>> 2. Make backoff arch dependent, and enable it for x86_64.
>>>> 3. Limit max backoff to reduce latency in large critical section.
>>>>
>>>> v4: Fix strict-prototypes error in sysdeps/nptl/pthread_mutex_backoff.h
>>>>
>>>> Result of pthread-mutex-locks bench
>>>>
>>>> Test Platform: Xeon 8280L (2 socket, 112 CPUs in total)
>>>> First Row: thread number
>>>> First Col: critical section length
>>>> Values: backoff vs upstream, time based, low is better
>>>>
>>>> non-critical-length: 1
>>>>           1       2       4       8       16      32      64      112     140
>>>> 0       0.99    0.58    0.52    0.49    0.43    0.44    0.46    0.52    0.54
>>>> 1       0.98    0.43    0.56    0.50    0.44    0.45    0.50    0.56    0.57
>>>> 2       0.99    0.41    0.57    0.51    0.45    0.47    0.48    0.60    0.61
>>>> 4       0.99    0.45    0.59    0.53    0.48    0.49    0.52    0.64    0.65
>>>> 8       1.00    0.66    0.71    0.63    0.56    0.59    0.66    0.72    0.71
>>>> 16      0.97    0.78    0.91    0.73    0.67    0.70    0.79    0.80    0.80
>>>> 32      0.95    1.17    0.98    0.87    0.82    0.86    0.89    0.90    0.90
>>>> 64      0.96    0.95    1.01    1.01    0.98    1.00    1.03    0.99    0.99
>>>> 128     0.99    1.01    1.01    1.17    1.08    1.12    1.02    0.97    1.02
>>>>
>>>> non-critical-length: 32
>>>>           1       2       4       8       16      32      64      112     140
>>>> 0       1.03    0.97    0.75    0.65    0.58    0.58    0.56    0.70    0.70
>>>> 1       0.94    0.95    0.76    0.65    0.58    0.58    0.61    0.71    0.72
>>>> 2       0.97    0.96    0.77    0.66    0.58    0.59    0.62    0.74    0.74
>>>> 4       0.99    0.96    0.78    0.66    0.60    0.61    0.66    0.76    0.77
>>>> 8       0.99    0.99    0.84    0.70    0.64    0.66    0.71    0.80    0.80
>>>> 16      0.98    0.97    0.95    0.76    0.70    0.73    0.81    0.85    0.84
>>>> 32      1.04    1.12    1.04    0.89    0.82    0.86    0.93    0.91    0.91
>>>> 64      0.99    1.15    1.07    1.00    0.99    1.01    1.05    0.99    0.99
>>>> 128     1.00    1.21    1.20    1.22    1.25    1.31    1.12    1.10    0.99
>>>>
>>>> non-critical-length: 128
>>>>           1       2       4       8       16      32      64      112     140
>>>> 0       1.02    1.00    0.99    0.67    0.61    0.61    0.61    0.74    0.73
>>>> 1       0.95    0.99    1.00    0.68    0.61    0.60    0.60    0.74    0.74
>>>> 2       1.00    1.04    1.00    0.68    0.59    0.61    0.65    0.76    0.76
>>>> 4       1.00    0.96    0.98    0.70    0.63    0.63    0.67    0.78    0.77
>>>> 8       1.01    1.02    0.89    0.73    0.65    0.67    0.71    0.81    0.80
>>>> 16      0.99    0.96    0.96    0.79    0.71    0.73    0.80    0.84    0.84
>>>> 32      0.99    0.95    1.05    0.89    0.84    0.85    0.94    0.92    0.91
>>>> 64      1.00    0.99    1.16    1.04    1.00    1.02    1.06    0.99    0.99
>>>> 128     1.00    1.06    0.98    1.14    1.39    1.26    1.08    1.02    0.98
>>>
>>> For large critical section lengths, the new code can be up to 39% slower.
>>> Is it true?  Are small critical section lengths more common
>> The adaptive mutex is aimed for "quick" locks.
>> Small critical section is more common when user choose to use adaptive
>> pthread_mutex.
> 
> Please update the commit log to document the rationale for this change.
> 
> Thanks.

Done, updated in v5 patch.

> 
> 
>>>
>>>> Signed-off-by: Wangyang Guo <wangyang.guo@intel.com>
>>>> ---
>>>>    nptl/pthread_mutex_lock.c                   | 16 +++++++--
>>>>    sysdeps/nptl/pthreadP.h                     |  1 +
>>>>    sysdeps/nptl/pthread_mutex_backoff.h        | 35 ++++++++++++++++++
>>>>    sysdeps/x86_64/nptl/pthread_mutex_backoff.h | 39 +++++++++++++++++++++
>>>>    4 files changed, 89 insertions(+), 2 deletions(-)
>>>>    create mode 100644 sysdeps/nptl/pthread_mutex_backoff.h
>>>>    create mode 100644 sysdeps/x86_64/nptl/pthread_mutex_backoff.h
>>>>
>>>> diff --git a/nptl/pthread_mutex_lock.c b/nptl/pthread_mutex_lock.c
>>>> index d2e652d151..6e767a8724 100644
>>>> --- a/nptl/pthread_mutex_lock.c
>>>> +++ b/nptl/pthread_mutex_lock.c
>>>> @@ -138,14 +138,26 @@ PTHREAD_MUTEX_LOCK (pthread_mutex_t *mutex)
>>>>             int cnt = 0;
>>>>             int max_cnt = MIN (max_adaptive_count (),
>>>>                                mutex->__data.__spins * 2 + 10);
>>>> +         int spin_count, exp_backoff = 1;
>>>> +         unsigned int jitter = get_jitter ();
>>>>             do
>>>>               {
>>>> -             if (cnt++ >= max_cnt)
>>>> +             /* In each loop, spin count is exponential backoff plus
>>>> +                random jitter, random range is [0, exp_backoff-1].  */
>>>> +             spin_count = exp_backoff + (jitter & (exp_backoff - 1));
>>>> +             cnt += spin_count;
>>>> +             if (cnt >= max_cnt)
>>>>                   {
>>>> +                 /* If cnt exceeds max spin count, just go to wait
>>>> +                    queue.  */
>>>>                     LLL_MUTEX_LOCK (mutex);
>>>>                     break;
>>>>                   }
>>>> -             atomic_spin_nop ();
>>>> +             do
>>>> +               atomic_spin_nop ();
>>>> +             while (--spin_count > 0);
>>>> +             /* Prepare for next loop.  */
>>>> +             exp_backoff = get_next_backoff (exp_backoff);
>>>>               }
>>>>             while (LLL_MUTEX_READ_LOCK (mutex) != 0
>>>>                    || LLL_MUTEX_TRYLOCK (mutex) != 0);
>>>> diff --git a/sysdeps/nptl/pthreadP.h b/sysdeps/nptl/pthreadP.h
>>>> index 601db4ff2b..39af275c25 100644
>>>> --- a/sysdeps/nptl/pthreadP.h
>>>> +++ b/sysdeps/nptl/pthreadP.h
>>>> @@ -33,6 +33,7 @@
>>>>    #include <kernel-features.h>
>>>>    #include <errno.h>
>>>>    #include <internal-signals.h>
>>>> +#include <pthread_mutex_backoff.h>
>>>>    #include "pthread_mutex_conf.h"
>>>>
>>>>
>>>> diff --git a/sysdeps/nptl/pthread_mutex_backoff.h b/sysdeps/nptl/pthread_mutex_backoff.h
>>>> new file mode 100644
>>>> index 0000000000..5b26c22ac7
>>>> --- /dev/null
>>>> +++ b/sysdeps/nptl/pthread_mutex_backoff.h
>>>> @@ -0,0 +1,35 @@
>>>> +/* Pthread mutex backoff configuration.
>>>> +   Copyright (C) 2022 Free Software Foundation, Inc.
>>>> +   This file is part of the GNU C Library.
>>>> +
>>>> +   The GNU C Library is free software; you can redistribute it and/or
>>>> +   modify it under the terms of the GNU Lesser General Public
>>>> +   License as published by the Free Software Foundation; either
>>>> +   version 2.1 of the License, or (at your option) any later version.
>>>> +
>>>> +   The GNU C Library is distributed in the hope that it will be useful,
>>>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>>>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
>>>> +   Lesser General Public License for more details.
>>>> +
>>>> +   You should have received a copy of the GNU Lesser General Public
>>>> +   License along with the GNU C Library; if not, see
>>>> +   <https://www.gnu.org/licenses/>.  */
>>>> +#ifndef _PTHREAD_MUTEX_BACKOFF_H
>>>> +#define _PTHREAD_MUTEX_BACKOFF_H 1
>>>> +
>>>> +static inline unsigned int
>>>> +get_jitter (void)
>>>> +{
>>>> +  /* Arch dependent random jitter, return 0 disables random.  */
>>>> +  return 0;
>>>> +}
>>>> +
>>>> +static inline int
>>>> +get_next_backoff (int backoff)
>>>> +{
>>>> +  /* Next backoff, return 1 disables mutex backoff.  */
>>>> +  return 1;
>>>> +}
>>>> +
>>>> +#endif
>>>> diff --git a/sysdeps/x86_64/nptl/pthread_mutex_backoff.h b/sysdeps/x86_64/nptl/pthread_mutex_backoff.h
>>>> new file mode 100644
>>>> index 0000000000..ec74c3d9db
>>>> --- /dev/null
>>>> +++ b/sysdeps/x86_64/nptl/pthread_mutex_backoff.h
>>>> @@ -0,0 +1,39 @@
>>>> +/* Pthread mutex backoff configuration.
>>>> +   Copyright (C) 2022 Free Software Foundation, Inc.
>>>> +   This file is part of the GNU C Library.
>>>> +
>>>> +   The GNU C Library is free software; you can redistribute it and/or
>>>> +   modify it under the terms of the GNU Lesser General Public
>>>> +   License as published by the Free Software Foundation; either
>>>> +   version 2.1 of the License, or (at your option) any later version.
>>>> +
>>>> +   The GNU C Library is distributed in the hope that it will be useful,
>>>> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
>>>> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
>>>> +   Lesser General Public License for more details.
>>>> +
>>>> +   You should have received a copy of the GNU Lesser General Public
>>>> +   License along with the GNU C Library; if not, see
>>>> +   <https://www.gnu.org/licenses/>.  */
>>>> +#ifndef _PTHREAD_MUTEX_BACKOFF_H
>>>> +#define _PTHREAD_MUTEX_BACKOFF_H 1
>>>> +
>>>> +#include <fast-jitter.h>
>>>> +
>>>> +static inline unsigned int
>>>> +get_jitter (void)
>>>> +{
>>>> +  return get_fast_jitter ();
>>>> +}
>>>> +
>>>> +#define MAX_BACKOFF 16
>>>> +
>>>> +static inline int
>>>> +get_next_backoff (int backoff)
>>>> +{
>>>> +  /* Binary expontial backoff. Limiting max backoff
>>>> +     can reduce latency in large critical section.  */
>>>> +  return (backoff < MAX_BACKOFF) ? backoff << 1 : backoff;
>>>> +}
>>>> +
>>>> +#endif
>>>> --
>>>> 2.35.1
>>>>
>>>
>>>
>>
> 
> 
> --
> H.J.
>