Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1260779 > unrolled thread

Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-02 17:40 +0100
    Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-03 00:00 +0100
      Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Waiman Long <waiman.long@hpe.com> - 2015-11-05 17:50 +0100
        Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-05 18:00 +0100
    Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Waiman Long <waiman.long@hpe.com> - 2015-11-05 17:10 +0100
      Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Peter Zijlstra <peterz@infradead.org> - 2015-11-05 17:40 +0100
        Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next  node cacheline Waiman Long <waiman.long@hpe.com> - 2015-11-05 18:00 +0100

#1260779 — Re: [PATCH tip/locking/core v9 2/6] locking/qspinlock: prefetch next node cacheline

On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
> A queue head CPU, after acquiring the lock, will have to notify
> the next CPU in the wait queue that it has became the new queue
> head. This involves loading a new cacheline from the MCS node of the
> next CPU. That operation can be expensive and add to the latency of
> locking operation.
> 
> This patch addes code to optmistically prefetch the next MCS node
> cacheline if the next pointer is defined and it has been spinning
> for the MCS lock for a while. This reduces the locking latency and
> improves the system throughput.
> 
> Using a locking microbenchmark on a Haswell-EX system, this patch
> can improve throughput by about 5%.

How does it affect IVB-EX (which you were testing earlier IIRC)?

> Signed-off-by: Waiman Long <Waiman.Long@hpe.com>
> ---
>  kernel/locking/qspinlock.c |   21 +++++++++++++++++++++
>  1 files changed, 21 insertions(+), 0 deletions(-)
> 
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index 7868418..c1c8a1a 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -396,6 +396,7 @@ queue:
>  	 * p,*,* -> n,*,*
>  	 */
>  	old = xchg_tail(lock, tail);
> +	next = NULL;
>  
>  	/*
>  	 * if there was a previous node; link it and wait until reaching the
> @@ -407,6 +408,16 @@ queue:
>  
>  		pv_wait_node(node);
>  		arch_mcs_spin_lock_contended(&node->locked);
> +
> +		/*
> +		 * While waiting for the MCS lock, the next pointer may have
> +		 * been set by another lock waiter. We optimistically load
> +		 * the next pointer & prefetch the cacheline for writing
> +		 * to reduce latency in the upcoming MCS unlock operation.
> +		 */
> +		next = READ_ONCE(node->next);
> +		if (next)
> +			prefetchw(next);
>  	}

OK so far I suppose. Since we already read node->locked, which is in the
same cacheline, also reading node->next isn't extra pressure. And we can
then prefetch that cacheline.

>  	/*
> @@ -426,6 +437,15 @@ queue:
>  		cpu_relax();
>  
>  	/*
> +	 * If the next pointer is defined, we are not tail anymore.
> +	 * In this case, claim the spinlock & release the MCS lock.
> +	 */
> +	if (next) {
> +		set_locked(lock);
> +		goto mcs_unlock;
> +	}
> +
> +	/*
>  	 * claim the lock:
>  	 *
>  	 * n,0,0 -> 0,0,1 : lock, uncontended
> @@ -458,6 +478,7 @@ queue:
>  	while (!(next = READ_ONCE(node->next)))
>  		cpu_relax();
>  
> +mcs_unlock:
>  	arch_mcs_spin_unlock_contended(&next->locked);
>  	pv_kick_node(lock, next);
>  

This however appears an independent optimization. Is it worth it? Would
we not already have observed a val != tail in this case? At which point
we're just adding extra code for no gain.

That is, if we observe @next, must we then not also observe val != tail?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1261044

On Mon, Nov 02, 2015 at 05:36:26PM +0100, Peter Zijlstra wrote:
> On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
> > @@ -426,6 +437,15 @@ queue:
> >  		cpu_relax();
> >  
> >  	/*
> > +	 * If the next pointer is defined, we are not tail anymore.
> > +	 * In this case, claim the spinlock & release the MCS lock.
> > +	 */
> > +	if (next) {
> > +		set_locked(lock);
> > +		goto mcs_unlock;
> > +	}
> > +
> > +	/*
> >  	 * claim the lock:
> >  	 *
> >  	 * n,0,0 -> 0,0,1 : lock, uncontended
> > @@ -458,6 +478,7 @@ queue:
> >  	while (!(next = READ_ONCE(node->next)))
> >  		cpu_relax();
> >  
> > +mcs_unlock:
> >  	arch_mcs_spin_unlock_contended(&next->locked);
> >  	pv_kick_node(lock, next);
> >  
> 
> This however appears an independent optimization. Is it worth it? Would
> we not already have observed a val != tail in this case? At which point
> we're just adding extra code for no gain.
> 
> That is, if we observe @next, must we then not also observe val != tail?

Not quite; the ordering is the other way around. If we observe next we
must also observe val != tail. But its a narrow thing. Is it really
worth it?
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1263417

On 11/02/2015 05:54 PM, Peter Zijlstra wrote:
> On Mon, Nov 02, 2015 at 05:36:26PM +0100, Peter Zijlstra wrote:
>> On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
>>> @@ -426,6 +437,15 @@ queue:
>>>   		cpu_relax();
>>>
>>>   	/*
>>> +	 * If the next pointer is defined, we are not tail anymore.
>>> +	 * In this case, claim the spinlock&  release the MCS lock.
>>> +	 */
>>> +	if (next) {
>>> +		set_locked(lock);
>>> +		goto mcs_unlock;
>>> +	}
>>> +
>>> +	/*
>>>   	 * claim the lock:
>>>   	 *
>>>   	 * n,0,0 ->  0,0,1 : lock, uncontended
>>> @@ -458,6 +478,7 @@ queue:
>>>   	while (!(next = READ_ONCE(node->next)))
>>>   		cpu_relax();
>>>
>>> +mcs_unlock:
>>>   	arch_mcs_spin_unlock_contended(&next->locked);
>>>   	pv_kick_node(lock, next);
>>>
>> This however appears an independent optimization. Is it worth it? Would
>> we not already have observed a val != tail in this case? At which point
>> we're just adding extra code for no gain.
>>
>> That is, if we observe @next, must we then not also observe val != tail?
> Not quite; the ordering is the other way around. If we observe next we
> must also observe val != tail. But its a narrow thing. Is it really
> worth it?

If we observe next, we will observe val != tail sooner or later. It is 
not possible for it to clear the tail code in the lock. The tail xchg 
will guarantee that.

Another alternative is to do something like

+    if (!next)
          while (!(next = READ_ONCE(node->next)))
             cpu_relax();

Please let me know if that is more acceptable to you.

Cheers,
Longman
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1263427

On Thu, Nov 05, 2015 at 11:42:27AM -0500, Waiman Long wrote:
> If we observe next, we will observe val != tail sooner or later. It is not
> possible for it to clear the tail code in the lock. The tail xchg will
> guarantee that.
> 
> Another alternative is to do something like
> 
> +    if (!next)
>          while (!(next = READ_ONCE(node->next)))
>             cpu_relax();
> 

Yes maybe, although the main reason I fell over this was because it was
a separate change (and not mentioned in the Changelog).

Although the above would need braces (per CodingStyle), so:

	if (!next) {
		while (!(next = READ_ONCE(node->next)))
			cpu_relax();
	}



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1263369

On 11/02/2015 11:36 AM, Peter Zijlstra wrote:
> On Fri, Oct 30, 2015 at 07:26:33PM -0400, Waiman Long wrote:
>> A queue head CPU, after acquiring the lock, will have to notify
>> the next CPU in the wait queue that it has became the new queue
>> head. This involves loading a new cacheline from the MCS node of the
>> next CPU. That operation can be expensive and add to the latency of
>> locking operation.
>>
>> This patch addes code to optmistically prefetch the next MCS node
>> cacheline if the next pointer is defined and it has been spinning
>> for the MCS lock for a while. This reduces the locking latency and
>> improves the system throughput.
>>
>> Using a locking microbenchmark on a Haswell-EX system, this patch
>> can improve throughput by about 5%.
> How does it affect IVB-EX (which you were testing earlier IIRC)?

My testing on IVB-EX indicated that if the critical section is really 
short, the change may actually slow thing a bit in some cases. However, 
when the critical section is long enough that the prefetch overhead can 
be hidden within the lock acquisition loop, there will be a performance 
boost.

>> Signed-off-by: Waiman Long<Waiman.Long@hpe.com>
>> ---
>>   kernel/locking/qspinlock.c |   21 +++++++++++++++++++++
>>   1 files changed, 21 insertions(+), 0 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
>> index 7868418..c1c8a1a 100644
>> --- a/kernel/locking/qspinlock.c
>> +++ b/kernel/locking/qspinlock.c
>> @@ -396,6 +396,7 @@ queue:
>>   	 * p,*,* ->  n,*,*
>>   	 */
>>   	old = xchg_tail(lock, tail);
>> +	next = NULL;
>>
>>   	/*
>>   	 * if there was a previous node; link it and wait until reaching the
>> @@ -407,6 +408,16 @@ queue:
>>
>>   		pv_wait_node(node);
>>   		arch_mcs_spin_lock_contended(&node->locked);
>> +
>> +		/*
>> +		 * While waiting for the MCS lock, the next pointer may have
>> +		 * been set by another lock waiter. We optimistically load
>> +		 * the next pointer&  prefetch the cacheline for writing
>> +		 * to reduce latency in the upcoming MCS unlock operation.
>> +		 */
>> +		next = READ_ONCE(node->next);
>> +		if (next)
>> +			prefetchw(next);
>>   	}
> OK so far I suppose. Since we already read node->locked, which is in the
> same cacheline, also reading node->next isn't extra pressure. And we can
> then prefetch that cacheline.
>
>>   	/*
>> @@ -426,6 +437,15 @@ queue:
>>   		cpu_relax();
>>
>>   	/*
>> +	 * If the next pointer is defined, we are not tail anymore.
>> +	 * In this case, claim the spinlock&  release the MCS lock.
>> +	 */
>> +	if (next) {
>> +		set_locked(lock);
>> +		goto mcs_unlock;
>> +	}
>> +
>> +	/*
>>   	 * claim the lock:
>>   	 *
>>   	 * n,0,0 ->  0,0,1 : lock, uncontended
>> @@ -458,6 +478,7 @@ queue:
>>   	while (!(next = READ_ONCE(node->next)))
>>   		cpu_relax();
>>
>> +mcs_unlock:
>>   	arch_mcs_spin_unlock_contended(&next->locked);
>>   	pv_kick_node(lock, next);
>>
> This however appears an independent optimization. Is it worth it? Would
> we not already have observed a val != tail in this case? At which point
> we're just adding extra code for no gain.
>
> That is, if we observe @next, must we then not also observe val != tail?

Observing next implies val != tail, but the reverse may not be true. The 
branch is done before we observe val != tail. Yes, it is an optimization 
to avoid reading node->next again if we have already observed next. I 
have observed a very minor performance boost with that change without 
the prefetch.

Cheers,
Longman

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1263407

On Thu, Nov 05, 2015 at 11:06:48AM -0500, Waiman Long wrote:

> >How does it affect IVB-EX (which you were testing earlier IIRC)?
> 
> My testing on IVB-EX indicated that if the critical section is really short,
> the change may actually slow thing a bit in some cases. However, when the
> critical section is long enough that the prefetch overhead can be hidden
> within the lock acquisition loop, there will be a performance boost.

> >>@@ -426,6 +437,15 @@ queue:
> >>  		cpu_relax();
> >>
> >>  	/*
> >>+	 * If the next pointer is defined, we are not tail anymore.
> >>+	 * In this case, claim the spinlock&  release the MCS lock.
> >>+	 */
> >>+	if (next) {
> >>+		set_locked(lock);
> >>+		goto mcs_unlock;
> >>+	}
> >>+
> >>+	/*
> >>  	 * claim the lock:
> >>  	 *
> >>  	 * n,0,0 ->  0,0,1 : lock, uncontended
> >>@@ -458,6 +478,7 @@ queue:
> >>  	while (!(next = READ_ONCE(node->next)))
> >>  		cpu_relax();
> >>
> >>+mcs_unlock:
> >>  	arch_mcs_spin_unlock_contended(&next->locked);
> >>  	pv_kick_node(lock, next);
> >>
> >This however appears an independent optimization. Is it worth it? Would
> >we not already have observed a val != tail in this case? At which point
> >we're just adding extra code for no gain.
> >
> >That is, if we observe @next, must we then not also observe val != tail?
> 
> Observing next implies val != tail, but the reverse may not be true. The
> branch is done before we observe val != tail. Yes, it is an optimization to
> avoid reading node->next again if we have already observed next. I have
> observed a very minor performance boost with that change without the
> prefetch.

This is all good information to have in the Changelog. And since these
are two independent changes, two patches would have been the right
format.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [next] | [standalone]

#1263425

On 11/05/2015 11:39 AM, Peter Zijlstra wrote:
> On Thu, Nov 05, 2015 at 11:06:48AM -0500, Waiman Long wrote:
>
>>> How does it affect IVB-EX (which you were testing earlier IIRC)?
>> My testing on IVB-EX indicated that if the critical section is really short,
>> the change may actually slow thing a bit in some cases. However, when the
>> critical section is long enough that the prefetch overhead can be hidden
>> within the lock acquisition loop, there will be a performance boost.
>>>> @@ -426,6 +437,15 @@ queue:
>>>>   		cpu_relax();
>>>>
>>>>   	/*
>>>> +	 * If the next pointer is defined, we are not tail anymore.
>>>> +	 * In this case, claim the spinlock&   release the MCS lock.
>>>> +	 */
>>>> +	if (next) {
>>>> +		set_locked(lock);
>>>> +		goto mcs_unlock;
>>>> +	}
>>>> +
>>>> +	/*
>>>>   	 * claim the lock:
>>>>   	 *
>>>>   	 * n,0,0 ->   0,0,1 : lock, uncontended
>>>> @@ -458,6 +478,7 @@ queue:
>>>>   	while (!(next = READ_ONCE(node->next)))
>>>>   		cpu_relax();
>>>>
>>>> +mcs_unlock:
>>>>   	arch_mcs_spin_unlock_contended(&next->locked);
>>>>   	pv_kick_node(lock, next);
>>>>
>>> This however appears an independent optimization. Is it worth it? Would
>>> we not already have observed a val != tail in this case? At which point
>>> we're just adding extra code for no gain.
>>>
>>> That is, if we observe @next, must we then not also observe val != tail?
>> Observing next implies val != tail, but the reverse may not be true. The
>> branch is done before we observe val != tail. Yes, it is an optimization to
>> avoid reading node->next again if we have already observed next. I have
>> observed a very minor performance boost with that change without the
>> prefetch.
> This is all good information to have in the Changelog. And since these
> are two independent changes, two patches would have been the right
> format.

Yep, I will separate it into 2 patches and include additional 
information in the changelog.

Cheers,
Longman
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web