From: Waiman Long <waiman.long@hp.com> To: Thomas Gleixner <tglx@linutronix.de> Cc: Ingo Molnar <mingo@redhat.com>, "H. Peter Anvin" <hpa@zytor.com>, Arnd Bergmann <arnd@arndb.de>, linux-arch@vger.kernel.org, x86@kernel.org, linux-kernel@vger.kernel.org, Peter Zijlstra <peterz@infradead.org>, Steven Rostedt <rostedt@goodmis.org>, Andrew Morton <akpm@linux-foundation.org>, Richard Weinberger <richard@nod.at>, Catalin Marinas <catalin.marinas@arm.com>, Greg Kroah-Hartman <gregkh@linuxfoundation.org>, Matt Fleming <matt.fleming@intel.com>, Herbert Xu <herbert@gondor.hengli.com.au>, Akinobu Mita <akinobu.mita@gmail.com>, Rusty Russell <rusty@rustcorp.com.au>, Michel Lespinasse <walken@google.com>, Andi Kleen <andi@firstfloor.org>, Rik van Riel <riel@redhat.com>, "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>, Linus Torvalds <torvalds@linux-foundation.org>, "Chandramouleeswaran, Aswin" <aswin@hp.com>, "Norton, Scott J" <scott.norton@hp.com> Subject: Re: [PATCH RFC 1/2] qrwlock: A queue read/write lock implementation Date: Thu, 18 Jul 2013 10:19:07 -0400 [thread overview] Message-ID: <51E7F95B.9050202@hp.com> (raw) In-Reply-To: <alpine.DEB.2.02.1307181210330.4089@ionos.tec.linutronix.de> On 07/18/2013 06:22 AM, Thomas Gleixner wrote: > Waiman, > > On Mon, 15 Jul 2013, Waiman Long wrote: >> On 07/15/2013 06:31 PM, Thomas Gleixner wrote: >>> On Fri, 12 Jul 2013, Waiman Long wrote: >>>> Apparently, the regular read/write lock performs even better than >>>> the queue read/write lock in some cases. This is probably due to the >>> The regular rwlock performs better in most cases. This is the full >>> list comparing both against the ticket lock. >>> >>> qrlock rwlock >>> +20.7 +44.4 >>> +30.1 +42.9 >>> >>> +56.3 +63.3 >>> +52.9 +48.8 >>> >>> +54.4 +65.1 >>> +49.2 +26.5 >>> >>> So you try to sell that qrwlock as a replacement for ticket spinlocks, >>> while at the same time you omit the fact that we have an even better >>> implementation (except for the last test case) already in the >>> kernel. What's the point of this exercise? >> The main point is that the regular rwlock is not fair while the >> queue rwlock is close to as fair as the ticket spinlock. The LWN >> article http://lwn.net/Articles/364583/ mentioned about eliminating >> rwlock altogether precisely because of this unfairness as it can >> cause livelock in certain scenerio. I also saw slides to advise >> again using rwlock because of this. > I'm well aware of this. But that does not explain anything of what I > asked. > >>>> + * has the following advantages: >>>> + * 1. It is more deterministic. Even though there is a slight chance >>>> of >>> Why is it more deterministic than the existing implementation? >> Deterministic means that that a process can acquire a lock within a >> reasonable time period without being starved for a long time. The qrwlock >> grants lock in FIFO order in most cases. That is what I mean by being more >> deterministic. > That's exactly the kind of explanation we want to have in the code and > the changelog. Sometimes I may take things for granted without explaining them in more details. Thank for reminding me and I will try to get more data in to support my arguments. >>>> + * stealing the lock if come at the right moment, the granting of >>>> the >>>> + * lock is mostly in FIFO order. >>>> + * 2. It is faster in high contention situation. >>> Again, why is it faster? >> The current rwlock implementation suffers from a thundering herd problem. >> When many readers are waiting for the lock hold by a writer, they will all >> jump in more or less at the same time when the writer releases the lock. >> That is not the case with qrwlock. It has been shown in many cases that >> avoiding this thundering herd problem can lead to better performance. > That makes sense and wants to be documented as well. You could have > avoided a lot of the discussion if you had included these details > right away. > >>>> + * an increase in lock size is not an issue. >>> So is it faster in the general case or only for the high contention or >>> single thread operation cases? >>> >>> And you still miss to explain WHY it is faster. Can you please explain >>> proper WHY it is faster and WHY we can't apply that technique you >>> implemented for qrwlocks to writer only locks (aka spinlocks) with a >>> smaller lock size? >> I will try to collect more data to justify the usefulness of qrwlock. > And please provide a proper argument why we can't use the same > technique for spinlocks. Of course, we can use the same technique for spinlock. Since we only need 1 bit for lock, we could combine the lock bit with the queue address with a little bit more overhead in term of coding and speed. That will make the new lock 4 bytes in size for 32-bit code & 8 bytes for 64-bit code. That could solve a lot of performance problem that we have with spinlock. However, I am aware that increasing the size of spinlock (for 64-bit systems) may break a lot of inherent alignment in many of the data structures. That is why I am not proposing such a change right now. But if there is enough interest, we could certainly go ahead and see how things go. >>> Aside of that, you are replacing all RW locks unconditionally by this >>> new fangled thing, but did you actually run tests which look at other >>> rwlock usage sites than the particular one you care about? >> Users have the choice of using the old rwlock or the queue rwlock by >> selecting or unselecting the QUEUE_RWLOCK config parameter. I am not >> forcing the unconditional replacement of rwlock by qrwlock. > Looking at patch 2/2: > > +config ARCH_QUEUE_RWLOCK > + def_bool y > > What's conditional about that? Where is the choice? The queue read/write lock replaces the classic read/write lock in the arch-dependent layer. We will need to make changes to each architecture to make queue read/write lock work. The presence of ARCH_QUEUE_RWLOCK just indicates that changes are made in that architecture to support the use of queue read/write lock. It doesn't mean that it is enabled by default. Users still need to choose it (QUEUE_RWLOCK) from the configuration menu. The ARCH_QUEUE_RWLOCK does prevent the menu option from even showing up for those architectures that have not been changed to support this feature. As I don't have test machines for the other architectures to verify the changes, my patch set only enables queue read/write lock for x86 only. >>> You are optimizing for the high frequency writer case. And that's not >>> the primary use case for rwlocks. That's the special use case for the >>> jbd2 journal_state_lock which CANNOT be generalized for all other >>> rwlock usage sites. >> It is true that this lock is kind of optimized for writers. For >> reader heavy code, the performance may not be as good as the rwlock >> for uncontended cases. However, I do believe that the fairness >> attribute of the qrwlock far outweigh the slight performance >> overhead of read lock/unlock. Furthermore, the lock/unlock sequence >> contributes only a very tiny percentage of total CPU time in >> uncontended cases. A slight increase may not really have a material >> impact on performance. Again, as promised, I will try to collect >> some more performance data for reader heavy usage cases. > Yes, please. We really need this information and if it turns out, that > it does not affect reader heavy sides, I have no objections against > the technology itself. I am collecting more performance data right now for the next revision of the patch. I had optimized the fast path of the lock to make write lock 2/3 the time of a spinlock and the read lock is now 1.5X of the spinlock time instead of 2X. Regards, Longman
WARNING: multiple messages have this Message-ID (diff)
From: Waiman Long <waiman.long@hp.com> To: Thomas Gleixner <tglx@linutronix.de> Cc: Ingo Molnar <mingo@redhat.com>, "H. Peter Anvin" <hpa@zytor.com>, Arnd Bergmann <arnd@arndb.de>, linux-arch@vger.kernel.org, x86@kernel.org, linux-kernel@vger.kernel.org, Peter Zijlstra <peterz@infradead.org>, Steven Rostedt <rostedt@goodmis.org>, Andrew Morton <akpm@linux-foundation.org>, Richard Weinberger <richard@nod.at>, Catalin Marinas <catalin.marinas@arm.com>, Greg Kroah-Hartman <gregkh@linuxfoundation.org>, Matt Fleming <matt.fleming@intel.com>, Herbert Xu <herbert@gondor.apana.org.au>, Akinobu Mita <akinobu.mita@gmail.com>, Rusty Russell <rusty@rustcorp.com.au>, Michel Lespinasse <walken@google.com>, Andi Kleen <andi@firstfloor.org>, Rik van Riel <riel@redhat.com>, "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>, Linus Torvalds <torvalds@linux-foundation.org>, "Chandramouleeswaran, Aswin" <aswin@hp.com>, "Norton, Scott J" <scott.norton@hp.com> Subject: Re: [PATCH RFC 1/2] qrwlock: A queue read/write lock implementation Date: Thu, 18 Jul 2013 10:19:07 -0400 [thread overview] Message-ID: <51E7F95B.9050202@hp.com> (raw) In-Reply-To: <alpine.DEB.2.02.1307181210330.4089@ionos.tec.linutronix.de> On 07/18/2013 06:22 AM, Thomas Gleixner wrote: > Waiman, > > On Mon, 15 Jul 2013, Waiman Long wrote: >> On 07/15/2013 06:31 PM, Thomas Gleixner wrote: >>> On Fri, 12 Jul 2013, Waiman Long wrote: >>>> Apparently, the regular read/write lock performs even better than >>>> the queue read/write lock in some cases. This is probably due to the >>> The regular rwlock performs better in most cases. This is the full >>> list comparing both against the ticket lock. >>> >>> qrlock rwlock >>> +20.7 +44.4 >>> +30.1 +42.9 >>> >>> +56.3 +63.3 >>> +52.9 +48.8 >>> >>> +54.4 +65.1 >>> +49.2 +26.5 >>> >>> So you try to sell that qrwlock as a replacement for ticket spinlocks, >>> while at the same time you omit the fact that we have an even better >>> implementation (except for the last test case) already in the >>> kernel. What's the point of this exercise? >> The main point is that the regular rwlock is not fair while the >> queue rwlock is close to as fair as the ticket spinlock. The LWN >> article http://lwn.net/Articles/364583/ mentioned about eliminating >> rwlock altogether precisely because of this unfairness as it can >> cause livelock in certain scenerio. I also saw slides to advise >> again using rwlock because of this. > I'm well aware of this. But that does not explain anything of what I > asked. > >>>> + * has the following advantages: >>>> + * 1. It is more deterministic. Even though there is a slight chance >>>> of >>> Why is it more deterministic than the existing implementation? >> Deterministic means that that a process can acquire a lock within a >> reasonable time period without being starved for a long time. The qrwlock >> grants lock in FIFO order in most cases. That is what I mean by being more >> deterministic. > That's exactly the kind of explanation we want to have in the code and > the changelog. Sometimes I may take things for granted without explaining them in more details. Thank for reminding me and I will try to get more data in to support my arguments. >>>> + * stealing the lock if come at the right moment, the granting of >>>> the >>>> + * lock is mostly in FIFO order. >>>> + * 2. It is faster in high contention situation. >>> Again, why is it faster? >> The current rwlock implementation suffers from a thundering herd problem. >> When many readers are waiting for the lock hold by a writer, they will all >> jump in more or less at the same time when the writer releases the lock. >> That is not the case with qrwlock. It has been shown in many cases that >> avoiding this thundering herd problem can lead to better performance. > That makes sense and wants to be documented as well. You could have > avoided a lot of the discussion if you had included these details > right away. > >>>> + * an increase in lock size is not an issue. >>> So is it faster in the general case or only for the high contention or >>> single thread operation cases? >>> >>> And you still miss to explain WHY it is faster. Can you please explain >>> proper WHY it is faster and WHY we can't apply that technique you >>> implemented for qrwlocks to writer only locks (aka spinlocks) with a >>> smaller lock size? >> I will try to collect more data to justify the usefulness of qrwlock. > And please provide a proper argument why we can't use the same > technique for spinlocks. Of course, we can use the same technique for spinlock. Since we only need 1 bit for lock, we could combine the lock bit with the queue address with a little bit more overhead in term of coding and speed. That will make the new lock 4 bytes in size for 32-bit code & 8 bytes for 64-bit code. That could solve a lot of performance problem that we have with spinlock. However, I am aware that increasing the size of spinlock (for 64-bit systems) may break a lot of inherent alignment in many of the data structures. That is why I am not proposing such a change right now. But if there is enough interest, we could certainly go ahead and see how things go. >>> Aside of that, you are replacing all RW locks unconditionally by this >>> new fangled thing, but did you actually run tests which look at other >>> rwlock usage sites than the particular one you care about? >> Users have the choice of using the old rwlock or the queue rwlock by >> selecting or unselecting the QUEUE_RWLOCK config parameter. I am not >> forcing the unconditional replacement of rwlock by qrwlock. > Looking at patch 2/2: > > +config ARCH_QUEUE_RWLOCK > + def_bool y > > What's conditional about that? Where is the choice? The queue read/write lock replaces the classic read/write lock in the arch-dependent layer. We will need to make changes to each architecture to make queue read/write lock work. The presence of ARCH_QUEUE_RWLOCK just indicates that changes are made in that architecture to support the use of queue read/write lock. It doesn't mean that it is enabled by default. Users still need to choose it (QUEUE_RWLOCK) from the configuration menu. The ARCH_QUEUE_RWLOCK does prevent the menu option from even showing up for those architectures that have not been changed to support this feature. As I don't have test machines for the other architectures to verify the changes, my patch set only enables queue read/write lock for x86 only. >>> You are optimizing for the high frequency writer case. And that's not >>> the primary use case for rwlocks. That's the special use case for the >>> jbd2 journal_state_lock which CANNOT be generalized for all other >>> rwlock usage sites. >> It is true that this lock is kind of optimized for writers. For >> reader heavy code, the performance may not be as good as the rwlock >> for uncontended cases. However, I do believe that the fairness >> attribute of the qrwlock far outweigh the slight performance >> overhead of read lock/unlock. Furthermore, the lock/unlock sequence >> contributes only a very tiny percentage of total CPU time in >> uncontended cases. A slight increase may not really have a material >> impact on performance. Again, as promised, I will try to collect >> some more performance data for reader heavy usage cases. > Yes, please. We really need this information and if it turns out, that > it does not affect reader heavy sides, I have no objections against > the technology itself. I am collecting more performance data right now for the next revision of the patch. I had optimized the fast path of the lock to make write lock 2/3 the time of a spinlock and the read lock is now 1.5X of the spinlock time instead of 2X. Regards, Longman
next prev parent reply other threads:[~2013-07-18 14:19 UTC|newest] Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top 2013-07-13 1:34 [PATCH RFC 0/2] qrwlock: Introducing a queue read/write lock implementation Waiman Long 2013-07-13 1:34 ` Waiman Long 2013-07-13 1:34 ` [PATCH RFC 1/2] qrwlock: A " Waiman Long 2013-07-13 1:34 ` Waiman Long 2013-07-15 14:39 ` Steven Rostedt 2013-07-15 14:39 ` Steven Rostedt 2013-07-15 20:44 ` Waiman Long 2013-07-15 20:44 ` Waiman Long 2013-07-15 22:31 ` Thomas Gleixner 2013-07-15 22:31 ` Thomas Gleixner 2013-07-16 1:19 ` Waiman Long 2013-07-16 1:19 ` Waiman Long 2013-07-18 7:42 ` Ingo Molnar 2013-07-18 7:42 ` Ingo Molnar 2013-07-18 7:42 ` Ingo Molnar 2013-07-18 13:40 ` Waiman Long 2013-07-18 13:40 ` Waiman Long 2013-07-18 13:40 ` Waiman Long 2013-07-19 8:40 ` Ingo Molnar 2013-07-19 8:40 ` Ingo Molnar 2013-07-19 8:40 ` Ingo Molnar 2013-07-19 15:30 ` Waiman Long 2013-07-19 15:30 ` Waiman Long 2013-07-19 15:30 ` Waiman Long 2013-07-22 10:34 ` Ingo Molnar 2013-07-22 10:34 ` Ingo Molnar 2013-07-22 10:34 ` Ingo Molnar 2013-07-24 0:03 ` Waiman Long 2013-07-24 0:03 ` Waiman Long 2013-07-24 0:03 ` Waiman Long 2013-07-18 10:22 ` Thomas Gleixner 2013-07-18 10:22 ` Thomas Gleixner 2013-07-18 14:19 ` Waiman Long [this message] 2013-07-18 14:19 ` Waiman Long 2013-07-21 5:42 ` Raghavendra K T 2013-07-21 5:42 ` Raghavendra K T 2013-07-21 5:42 ` Raghavendra K T 2013-07-23 23:54 ` Waiman Long 2013-07-23 23:54 ` Waiman Long 2013-07-23 23:54 ` Waiman Long 2013-07-13 1:34 ` [PATCH RFC 2/2] x86 qrwlock: Enable x86 to use queue read/write lock Waiman Long 2013-07-13 1:34 ` Waiman Long 2013-07-18 12:55 [PATCH RFC 1/2] qrwlock: A queue read/write lock implementation George Spelvin 2013-07-18 13:43 ` Waiman Long 2013-07-18 18:46 ` George Spelvin 2013-07-19 15:43 ` Waiman Long 2013-07-19 21:11 ` George Spelvin 2013-07-19 21:35 ` Waiman Long 2013-07-18 13:18 George Spelvin
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=51E7F95B.9050202@hp.com \ --to=waiman.long@hp.com \ --cc=akinobu.mita@gmail.com \ --cc=akpm@linux-foundation.org \ --cc=andi@firstfloor.org \ --cc=arnd@arndb.de \ --cc=aswin@hp.com \ --cc=catalin.marinas@arm.com \ --cc=gregkh@linuxfoundation.org \ --cc=herbert@gondor.hengli.com.au \ --cc=hpa@zytor.com \ --cc=linux-arch@vger.kernel.org \ --cc=linux-kernel@vger.kernel.org \ --cc=matt.fleming@intel.com \ --cc=mingo@redhat.com \ --cc=paulmck@linux.vnet.ibm.com \ --cc=peterz@infradead.org \ --cc=richard@nod.at \ --cc=riel@redhat.com \ --cc=rostedt@goodmis.org \ --cc=rusty@rustcorp.com.au \ --cc=scott.norton@hp.com \ --cc=tglx@linutronix.de \ --cc=torvalds@linux-foundation.org \ --cc=walken@google.com \ --cc=x86@kernel.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: linkBe sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.