From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by sourceware.org (Postfix) with ESMTPS id 4C4773857825 for ; Fri, 6 May 2022 01:52:42 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 4C4773857825 X-IronPort-AV: E=McAfee;i="6400,9594,10338"; a="268461379" X-IronPort-AV: E=Sophos;i="5.91,203,1647327600"; d="scan'208";a="268461379" Received: from orsmga006.jf.intel.com ([10.7.209.51]) by fmsmga103.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 05 May 2022 18:52:40 -0700 X-IronPort-AV: E=Sophos;i="5.91,203,1647327600"; d="scan'208";a="537648632" Received: from guowangy-mobl1.ccr.corp.intel.com (HELO [10.249.172.180]) ([10.249.172.180]) by orsmga006-auth.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 05 May 2022 18:52:39 -0700 Message-ID: Date: Fri, 6 May 2022 09:52:36 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.8.0 Subject: Re: [PATCH v4] nptl: Add backoff mechanism to spinlock loop Content-Language: en-US To: "H.J. Lu" Cc: libc-alpha@sourceware.org References: <20220504025849.13449-1-wangyang.guo@intel.com> <20220504031710.60677-1-wangyang.guo@intel.com> <02f7eba1-1461-6d26-3a28-958401219844@intel.com> From: "Guo, Wangyang" In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Status: No, score=-13.5 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, NICE_REPLY_A, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 06 May 2022 01:52:44 -0000 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 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 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 >>>> --- >>>> 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 >>>> #include >>>> #include >>>> +#include >>>> #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 >>>> + . */ >>>> +#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 >>>> + . */ >>>> +#ifndef _PTHREAD_MUTEX_BACKOFF_H >>>> +#define _PTHREAD_MUTEX_BACKOFF_H 1 >>>> + >>>> +#include >>>> + >>>> +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. >