public inbox for libc-alpha@sourceware.org
 help / color / mirror / Atom feed
From: "Guo, Wangyang" <wangyang.guo@intel.com>
To: "H.J. Lu" <hjl.tools@gmail.com>
Cc: libc-alpha@sourceware.org
Subject: Re: [PATCH v4] nptl: Add backoff mechanism to spinlock loop
Date: Thu, 5 May 2022 10:59:35 +0800	[thread overview]
Message-ID: <02f7eba1-1461-6d26-3a28-958401219844@intel.com> (raw)
In-Reply-To: <CAMe9rOq1Sxt-AVFGUnUA2Z7-D4zFQmZA9sxA0k_Rn+KE3xTnhg@mail.gmail.com>

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.
> 
>> 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
>>
> 
> 


  parent reply	other threads:[~2022-05-05  2:59 UTC|newest]

Thread overview: 28+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-03-28  8:47 [PATCH v2] " Wangyang Guo
2022-03-28 16:41 ` Noah Goldstein
2022-03-30 11:44   ` Guo, Wangyang
2022-03-30 19:39     ` Noah Goldstein
2022-03-30 11:53 ` Adhemerval Zanella
2022-03-30 17:07   ` Noah Goldstein
2022-03-30 17:21     ` Adhemerval Zanella
2022-04-12 11:53       ` Florian Weimer
2022-04-22 13:30         ` Yann Droneaud
2022-04-22 13:32           ` Florian Weimer
2022-04-22 13:35             ` Cristian Rodríguez
2022-04-22 15:25               ` Noah Goldstein
2022-04-26 12:25                 ` Florian Weimer
2022-04-26 12:42                   ` Yann Droneaud
2022-05-04  2:50 ` [PATCH v3] " Wangyang Guo
2022-05-04  2:58 ` Wangyang Guo
2022-05-04  3:17   ` [PATCH v4] " Wangyang Guo
2022-05-05  1:56     ` H.J. Lu
2022-05-05  2:52       ` Noah Goldstein
2022-05-05  2:59       ` Guo, Wangyang [this message]
2022-05-05 22:44         ` H.J. Lu
2022-05-06  1:52           ` Guo, Wangyang
2022-05-06  1:50     ` [PATCH v5] " Wangyang Guo
2022-05-06  3:06       ` H.J. Lu
2022-09-11 20:29         ` Sunil Pandey
2022-09-14  1:26           ` Noah Goldstein
2022-09-29  0:12           ` Noah Goldstein
2022-09-30 13:18             ` FUCKETY FUCK FUCK, PLEASE REMOVE ME FROM THESE EMAILS Darren Tristano

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=02f7eba1-1461-6d26-3a28-958401219844@intel.com \
    --to=wangyang.guo@intel.com \
    --cc=hjl.tools@gmail.com \
    --cc=libc-alpha@sourceware.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).