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

Groups > linux.kernel > #1302210 > unrolled thread

Re: [RFC PATCH] alispinlock: acceleration from lock integration on multi-core platform

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: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform Peter Zijlstra <peterz@infradead.org> - 2016-01-05 22:20 +0100
    Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk> - 2016-01-05 22:50 +0100
      Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform Peter Zijlstra <peterz@infradead.org> - 2016-01-06 09:20 +0100
        Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform Peter Zijlstra <peterz@infradead.org> - 2016-01-06 09:30 +0100
          Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk> - 2016-01-06 12:30 +0100
            Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform Ling Ma <ling.ma.program@gmail.com> - 2016-01-08 23:50 +0100
              Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk> - 2016-01-12 15:00 +0100
                Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform Ling Ma <ling.ma.program@gmail.com> - 2016-01-14 09:20 +0100
      Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform Ling Ma <ling.ma.program@gmail.com> - 2016-01-09 00:10 +0100
    Re: [RFC PATCH] alispinlock: acceleration from lock integration on  multi-core platform Ling Ma <ling.ma.program@gmail.com> - 2016-01-09 00:00 +0100

#1302210 — Re: [RFC PATCH] alispinlock: acceleration from lock integration on multi-core platform

On Thu, Dec 31, 2015 at 04:09:34PM +0800, ling.ma.program@gmail.com wrote:
> +void alispinlock(struct ali_spinlock *lock, struct ali_spinlock_info *ali)
> +{
> +	struct ali_spinlock_info *next, *old;
> +
> +	ali->next = NULL;
> +	ali->locked = 1;
> +	old = xchg(&lock->lock_p, ali);
> +
> +	/* If NULL we are the first one */
> +	if (old) {
> +		WRITE_ONCE(old->next, ali);
> +		if(ali->flags & ALI_LOCK_FREE)
> +			return;
> +		while((READ_ONCE(ali->locked)))
> +			cpu_relax_lowlatency();
> +		return;
> +	}
> +	old = READ_ONCE(lock->lock_p);
> +
> +	/* Handle all pending works */
> +repeat:	
> +	if(old == ali)
> +		goto end;
> +
> +	while (!(next = READ_ONCE(ali->next)))
> +		cpu_relax();
> +	
> +	ali->fn(ali->para);
> +	ali->locked = 0;
> +
> +	if(old != next) {
> +		while (!(ali = READ_ONCE(next->next)))
> +			cpu_relax();
> +		next->fn(next->para);
> +		next->locked = 0;
> +		goto repeat;
> +		
> +	} else
> +		ali = next;

So I have a whole bunch of problems with this thing.. For one I object
to this being called a lock. Its much more like an async work queue like
thing.

It suffers the typical problems all those constructs do; namely it
wrecks accountability.

But here that is compounded by the fact that you inject other people's
work into 'your' lock region, thereby bloating lock hold times. Worse,
afaict (from a quick reading) there really isn't a bound on the amount
of work you inject.

This will completely wreck scheduling latency. At the very least the
callback loop should have a need_resched() test on, but even that will
not work if this has IRQs disabled.


And while its a cute collapse of an MCS lock and lockless list style
work queue (MCS after all is a lockless list), saving a few cycles from
the naive spinlock+llist implementation of the same thing, I really
do not see enough justification for any of this.
--
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]

#1302234

> It suffers the typical problems all those constructs do; namely it
> wrecks accountability.

That's "government thinking" ;-) - for most real users throughput is
more important than accountability. With the right API it ought to also
be compile time switchable.

> But here that is compounded by the fact that you inject other people's
> work into 'your' lock region, thereby bloating lock hold times. Worse,
> afaict (from a quick reading) there really isn't a bound on the amount
> of work you inject.

That should be relatively easy to fix but for this kind of lock you
normally get the big wins from stuff that is only a short amount of
executing code. The fairness your trade in the cases it is useful should
be tiny except under extreme load, where the "accountability first"
behaviour would be to fall over in a heap.

If your "lock" involves a lot of work then it probably should be a work
queue or not using this kind of locking.

> And while its a cute collapse of an MCS lock and lockless list style
> work queue (MCS after all is a lockless list), saving a few cycles from
> the naive spinlock+llist implementation of the same thing, I really
> do not see enough justification for any of this.

I've only personally dealt with such locks in the embedded space but
there it was a lot more than a few cycles because you go from


	take lock
						spins
	pull things into cache
	do stuff
	cache lines go write/exclusive
	unlock

						take lock
						move all the cache
						do stuff
						etc

to

	take lock
						queue work
	pull things into cache
	do work 1
	caches line go write/exclusive
	do work 2
	
	unlock
						done

and for the kind of stuff you apply those locks you got big improvements.
Even on crappy little embedded processors cache bouncing hurts. Even
better work merging locks like this tend to improve throughput more the
higher the contention unlike most other lock types.

The claim in the original post is 3x performance but doesn't explain
performance doing what, or which kernel locks were switched and what
patches were used. I don't find the numbers hard to believe for a big big
box, but I'd like to see the actual use case patches so it can be benched
with other workloads and also for latency and the like.

Alan
--
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]

#1302449

On Tue, Jan 05, 2016 at 09:42:27PM +0000, One Thousand Gnomes wrote:
> > It suffers the typical problems all those constructs do; namely it
> > wrecks accountability.
> 
> That's "government thinking" ;-) - for most real users throughput is
> more important than accountability. With the right API it ought to also
> be compile time switchable.

Its to do with having been involved with -rt. RT wants to do
accountability for such things because of PI and sorts.

> > But here that is compounded by the fact that you inject other people's
> > work into 'your' lock region, thereby bloating lock hold times. Worse,
> > afaict (from a quick reading) there really isn't a bound on the amount
> > of work you inject.
> 
> That should be relatively easy to fix but for this kind of lock you
> normally get the big wins from stuff that is only a short amount of
> executing code. The fairness your trade in the cases it is useful should
> be tiny except under extreme load, where the "accountability first"
> behaviour would be to fall over in a heap.
> 
> If your "lock" involves a lot of work then it probably should be a work
> queue or not using this kind of locking.

Sure, but the fact that it was not even mentioned/considered doesn't
give me a warm fuzzy feeling.

> > And while its a cute collapse of an MCS lock and lockless list style
> > work queue (MCS after all is a lockless list), saving a few cycles from
> > the naive spinlock+llist implementation of the same thing, I really
> > do not see enough justification for any of this.
> 
> I've only personally dealt with such locks in the embedded space but
> there it was a lot more than a few cycles because you go from

Nah, what I meant was that you can do the same callback style construct
with a llist and a spinlock.

> The claim in the original post is 3x performance but doesn't explain
> performance doing what, or which kernel locks were switched and what
> patches were used. I don't find the numbers hard to believe for a big big
> box, but I'd like to see the actual use case patches so it can be benched
> with other workloads and also for latency and the like.

Very much agreed, those claims need to be substantiated with actual
patches using this thing and independently verified.
--
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]

#1302458

On Wed, Jan 06, 2016 at 09:16:43AM +0100, Peter Zijlstra wrote:
> On Tue, Jan 05, 2016 at 09:42:27PM +0000, One Thousand Gnomes wrote:
> > > It suffers the typical problems all those constructs do; namely it
> > > wrecks accountability.
> > 
> > That's "government thinking" ;-) - for most real users throughput is
> > more important than accountability. With the right API it ought to also
> > be compile time switchable.
> 
> Its to do with having been involved with -rt. RT wants to do
> accountability for such things because of PI and sorts.

Also, real people really do care about latency too, very bad worst case
spikes to upset things.
--
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]

#1302700

On Wed, 6 Jan 2016 09:21:06 +0100
Peter Zijlstra <peterz@infradead.org> wrote:

> On Wed, Jan 06, 2016 at 09:16:43AM +0100, Peter Zijlstra wrote:
> > On Tue, Jan 05, 2016 at 09:42:27PM +0000, One Thousand Gnomes wrote:
> > > > It suffers the typical problems all those constructs do; namely it
> > > > wrecks accountability.
> > > 
> > > That's "government thinking" ;-) - for most real users throughput is
> > > more important than accountability. With the right API it ought to also
> > > be compile time switchable.
> > 
> > Its to do with having been involved with -rt. RT wants to do
> > accountability for such things because of PI and sorts.
> 
> Also, real people really do care about latency too, very bad worst case
> spikes to upset things.

Some yes - I'm familiar with the way some of the big financial number
crunching jobs need this. There are also people who instead care a lot
about throughput. Anything like this needs to end up with an external API
which looks the same whether the work is done via one thread or the other.

Alan
--
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]

#1305043

[Multipart message — attachments visible in raw view] — view raw

The attachment (alispinlock.tar.bz2) includes original spinlock and
alispinlock ,
we compare them on 70 cores based on kernel 4.3, the alispinlock can
improve performance upto 3x.

the link: https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1035940.html
indicates when we introduce the idea for real application(user space
application  caused the bottle neck from  kernel spinlock )
the spinlock performance is improved by 1.9x (perf top -d1 also tell
us the spinlock cost time is reduced from 25% to 15%).

Appreciate your comments
Ling

2016-01-06 19:24 GMT+08:00 One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>:
> On Wed, 6 Jan 2016 09:21:06 +0100
> Peter Zijlstra <peterz@infradead.org> wrote:
>
>> On Wed, Jan 06, 2016 at 09:16:43AM +0100, Peter Zijlstra wrote:
>> > On Tue, Jan 05, 2016 at 09:42:27PM +0000, One Thousand Gnomes wrote:
>> > > > It suffers the typical problems all those constructs do; namely it
>> > > > wrecks accountability.
>> > >
>> > > That's "government thinking" ;-) - for most real users throughput is
>> > > more important than accountability. With the right API it ought to also
>> > > be compile time switchable.
>> >
>> > Its to do with having been involved with -rt. RT wants to do
>> > accountability for such things because of PI and sorts.
>>
>> Also, real people really do care about latency too, very bad worst case
>> spikes to upset things.
>
> Some yes - I'm familiar with the way some of the big financial number
> crunching jobs need this. There are also people who instead care a lot
> about throughput. Anything like this needs to end up with an external API
> which looks the same whether the work is done via one thread or the other.
>
> Alan

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

#1307425

On Sat, 9 Jan 2016 06:44:15 +0800
Ling Ma <ling.ma.program@gmail.com> wrote:

> The attachment (alispinlock.tar.bz2) includes original spinlock and
> alispinlock ,
> we compare them on 70 cores based on kernel 4.3, the alispinlock can
> improve performance upto 3x.
> 
> the link: https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1035940.html
> indicates when we introduce the idea for real application(user space
> application  caused the bottle neck from  kernel spinlock )
> the spinlock performance is improved by 1.9x (perf top -d1 also tell
> us the spinlock cost time is reduced from 25% to 15%).
> 
> Appreciate your comments

So this has not been applied to actual real kernel locks (ie converted
some of the hot kernel locks to it) and then benchmarked with a real
world workload. This is just for the theoretical locking overhead ?

Alan

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

#1309067

[Multipart message — attachments visible in raw view] — view raw

Alan,

The attachment  (alispinlock.tar.bz2) in last email includes our
sample cases for spinlock.
The attachment (lock_test.tar.bz2) in this email includes the patch on
kernel 4.3v ,
which has been applied to actual real kernel locks:
when we run the user space program (thread.c) on 72cores E5-2699v3,
it cause many hot kernel spinlocks from __kmalloc and kfree  respectively
with original spinlock cpu cost 25% and  92715428576 cycles after
lock/unlock 1000000 times
with ali spinlock cpu cost 15% and  48475891244 cycles after
lock/unlock 1000000 times.
So we say in the real world workload the ali spinlock improve
performance by 1.9x
(92715428576 cycles/48475891244 cycles)

Thanks
Ling

the

2016-01-12 21:50 GMT+08:00 One Thousand Gnomes <gnomes@lxorguk.ukuu.org.uk>:
> On Sat, 9 Jan 2016 06:44:15 +0800
> Ling Ma <ling.ma.program@gmail.com> wrote:
>
>> The attachment (alispinlock.tar.bz2) includes original spinlock and
>> alispinlock ,
>> we compare them on 70 cores based on kernel 4.3, the alispinlock can
>> improve performance upto 3x.
>>
>> the link: https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg1035940.html
>> indicates when we introduce the idea for real application(user space
>> application  caused the bottle neck from  kernel spinlock )
>> the spinlock performance is improved by 1.9x (perf top -d1 also tell
>> us the spinlock cost time is reduced from 25% to 15%).
>>
>> Appreciate your comments
>
> So this has not been applied to actual real kernel locks (ie converted
> some of the hot kernel locks to it) and then benchmarked with a real
> world workload. This is just for the theoretical locking overhead ?
>
> Alan

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

#1305052

> The claim in the original post is 3x performance but doesn't explain
> performance doing what, or which kernel locks were switched and what
> patches were used. I don't find the numbers hard to believe for a big big
> box, but I'd like to see the actual use case patches so it can be benched
> with other workloads and also for latency and the like.
>

We have sent out in email, please review and test it.

Thanks
Ling

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

#1305049

> So I have a whole bunch of problems with this thing.. For one I object
> to this being called a lock. Its much more like an async work queue like
> thing.
Ok, I will fix it.

> It suffers the typical problems all those constructs do; namely it
> wrecks accountability.
Ok, I will fix it.

> But here that is compounded by the fact that you inject other people's
> work into 'your' lock region, thereby bloating lock hold times. Worse,
> afaict (from a quick reading) there really isn't a bound on the amount
> of work you inject.
>
> This will completely wreck scheduling latency. At the very least the
> callback loop should have a need_resched() test on, but even that will
> not work if this has IRQs disabled.
>
>
> And while its a cute collapse of an MCS lock and lockless list style
> work queue (MCS after all is a lockless list), saving a few cycles from
> the naive spinlock+llist implementation of the same thing, I really
> do not see enough justification for any of this.
we can fix it if we really don't need it.

Thanks
Ling

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web