* [PATCH 1/1] mutex: prevent optimistic spinning from spinning longer than neccessary (Repost)
@ 2010-08-18 22:00 Tim Chen
2010-08-19 11:05 ` Ingo Molnar
0 siblings, 1 reply; 5+ messages in thread
From: Tim Chen @ 2010-08-18 22:00 UTC (permalink / raw)
To: peterz, mingo, Andrew Morton; +Cc: linux-kernel, Andi Kleen, Tony Luck
I didn't get any feedback on this post sent a while back. So I'm
reposting it to see if I can get some comments back this time.
There is a scalability issue for current implementation of optimistic
mutex spin in the kernel. It is found on a 8 node 64 core Nehalem-EX
system (HT mode).
The intention of the optimistic mutex spin is to busy wait and spin on a
mutex if the owner of the mutex is running, in the hope that the mutex
will be released soon and be acquired, without the thread
trying to acquire mutex going to sleep. However,
when we have a large number of threads, contending for the mutex, we could
have the mutex grabbed by other thread, and then another ……, and we will keep
spinning, wasting cpu cycles and adding to the contention. One
possible fix is to quit spinning and put the current thread on wait-list
if mutex lock switch to a new owner while we spin, indicating heavy
contention (see the patch included).
I did some testing on a 8 socket Nehalem-EX system with a total of 64
cores. Using Ingo's test-mutex program that creates/delete files with
256 threads (http://lkml.org/lkml/2006/1/8/50) , I see the following
speed up after putting in the mutex spin fix:
./mutex-test V 256 10
Ops/sec
2.6.34 62864
With fix 197200
Repeating the test with Aim7 fserver workload, again there is a speed up
with the fix:
Jobs/min
2.6.34 91657
With fix 149325
To look at the impact on the distribution of mutex acquisition time, I
collected the mutex acquisition time on Aim7 fserver workload with some
instrumentation. The average acquisition time is reduced by 48% and
number of contentions reduced by 32%.
#contentions Time to acquire mutex (cycles)
2.6.34 72973 44765791
With fix 49210 23067129
The histogram of mutex acquisition time is listed below. The
acquisition time is in 2^bin cycles. We see that without the fix, the
acquisition time is mostly around 2^26 cycles. With the fix, we the
distribution get spread out a lot more towards the lower cycles,
starting from 2^13. However, there is an increase of the tail
distribution with the fix at 2^28 and 2^29 cycles. It seems a
small price to pay for the reduced average acquisition time and also
getting the cpu to do useful work.
Mutex acquisition time distribution (acq time = 2^bin cycles):
2.6.34 With Fix
bin #occurrence % #occurrence %
11 2 0.00% 120 0.24%
12 10 0.01% 790 1.61%
13 14 0.02% 2058 4.18%
14 86 0.12% 3378 6.86%
15 393 0.54% 4831 9.82%
16 710 0.97% 4893 9.94%
17 815 1.12% 4667 9.48%
18 790 1.08% 5147 10.46%
19 580 0.80% 6250 12.70%
20 429 0.59% 6870 13.96%
21 311 0.43% 1809 3.68%
22 255 0.35% 2305 4.68%
23 317 0.44% 916 1.86%
24 610 0.84% 233 0.47%
25 3128 4.29% 95 0.19%
26 63902 87.69% 122 0.25%
27 619 0.85% 286 0.58%
28 0 0.00% 3536 7.19%
29 0 0.00% 903 1.83%
30 0 0.00% 0 0.00%
Regards,
Tim
Signed-off-by: Tim Chen <tim.c.chen@linux.intel.com>
diff -ur linux-2.6.34/kernel/sched.c linux-2.6.34-fix/kernel/sched.c
--- linux-2.6.34/kernel/sched.c 2010-05-16 14:17:36.000000000 -0700
+++ linux-2.6.34-fix/kernel/sched.c 2010-06-04 10:28:33.564777030 -0700
@@ -3815,8 +3815,11 @@
/*
* Owner changed, break to re-assess state.
*/
- if (lock->owner != owner)
+ if (lock->owner != owner) {
+ if (lock->owner)
+ return 0;
break;
+ }
/*
* Is that owner really running on that cpu?
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH 1/1] mutex: prevent optimistic spinning from spinning longer than neccessary (Repost)
2010-08-18 22:00 [PATCH 1/1] mutex: prevent optimistic spinning from spinning longer than neccessary (Repost) Tim Chen
@ 2010-08-19 11:05 ` Ingo Molnar
2010-08-19 22:24 ` Tim Chen
0 siblings, 1 reply; 5+ messages in thread
From: Ingo Molnar @ 2010-08-19 11:05 UTC (permalink / raw)
To: Tim Chen, Linus Torvalds, Thomas Gleixner,
Frédéric Weisbecker
Cc: peterz, Andrew Morton, linux-kernel, Andi Kleen, Tony Luck
* Tim Chen <tim.c.chen@linux.intel.com> wrote:
> I didn't get any feedback on this post sent a while back. So I'm
> reposting it to see if I can get some comments back this time.
>
> There is a scalability issue for current implementation of optimistic
> mutex spin in the kernel. It is found on a 8 node 64 core Nehalem-EX
> system (HT mode).
>
> The intention of the optimistic mutex spin is to busy wait and spin on a
> mutex if the owner of the mutex is running, in the hope that the mutex
> will be released soon and be acquired, without the thread
> trying to acquire mutex going to sleep. However,
> when we have a large number of threads, contending for the mutex, we could
> have the mutex grabbed by other thread, and then another ……, and we will keep
> spinning, wasting cpu cycles and adding to the contention. One
> possible fix is to quit spinning and put the current thread on wait-list
> if mutex lock switch to a new owner while we spin, indicating heavy
> contention (see the patch included).
>
> I did some testing on a 8 socket Nehalem-EX system with a total of 64
> cores. Using Ingo's test-mutex program that creates/delete files with
> 256 threads (http://lkml.org/lkml/2006/1/8/50) , I see the following
> speed up after putting in the mutex spin fix:
>
> ./mutex-test V 256 10
> Ops/sec
> 2.6.34 62864
> With fix 197200
>
> Repeating the test with Aim7 fserver workload, again there is a speed up
> with the fix:
>
> Jobs/min
> 2.6.34 91657
> With fix 149325
>
> To look at the impact on the distribution of mutex acquisition time, I
> collected the mutex acquisition time on Aim7 fserver workload with some
> instrumentation. The average acquisition time is reduced by 48% and
> number of contentions reduced by 32%.
>
> #contentions Time to acquire mutex (cycles)
> 2.6.34 72973 44765791
> With fix 49210 23067129
>
> The histogram of mutex acquisition time is listed below. The
> acquisition time is in 2^bin cycles. We see that without the fix, the
> acquisition time is mostly around 2^26 cycles. With the fix, we the
> distribution get spread out a lot more towards the lower cycles,
> starting from 2^13. However, there is an increase of the tail
> distribution with the fix at 2^28 and 2^29 cycles. It seems a
> small price to pay for the reduced average acquisition time and also
> getting the cpu to do useful work.
>
> Mutex acquisition time distribution (acq time = 2^bin cycles):
> 2.6.34 With Fix
> bin #occurrence % #occurrence %
> 11 2 0.00% 120 0.24%
> 12 10 0.01% 790 1.61%
> 13 14 0.02% 2058 4.18%
> 14 86 0.12% 3378 6.86%
> 15 393 0.54% 4831 9.82%
> 16 710 0.97% 4893 9.94%
> 17 815 1.12% 4667 9.48%
> 18 790 1.08% 5147 10.46%
> 19 580 0.80% 6250 12.70%
> 20 429 0.59% 6870 13.96%
> 21 311 0.43% 1809 3.68%
> 22 255 0.35% 2305 4.68%
> 23 317 0.44% 916 1.86%
> 24 610 0.84% 233 0.47%
> 25 3128 4.29% 95 0.19%
> 26 63902 87.69% 122 0.25%
> 27 619 0.85% 286 0.58%
> 28 0 0.00% 3536 7.19%
> 29 0 0.00% 903 1.83%
> 30 0 0.00% 0 0.00%
>
> Regards,
> Tim
>
> Signed-off-by: Tim Chen <tim.c.chen@linux.intel.com>
> diff -ur linux-2.6.34/kernel/sched.c linux-2.6.34-fix/kernel/sched.c
> --- linux-2.6.34/kernel/sched.c 2010-05-16 14:17:36.000000000 -0700
> +++ linux-2.6.34-fix/kernel/sched.c 2010-06-04 10:28:33.564777030 -0700
> @@ -3815,8 +3815,11 @@
> /*
> * Owner changed, break to re-assess state.
> */
> - if (lock->owner != owner)
> + if (lock->owner != owner) {
> + if (lock->owner)
> + return 0;
> break;
> + }
>
> /*
> * Is that owner really running on that cpu?
These are some rather impressive speedups!
Have you tried to see what performance effects this change has on smaller
boxes? Just to see what flip side (if any) this change has.
Thanks,
Ingo
^ permalink raw reply [flat|nested] 5+ messages in thread* Re: [PATCH 1/1] mutex: prevent optimistic spinning from spinning longer than neccessary (Repost)
2010-08-19 11:05 ` Ingo Molnar
@ 2010-08-19 22:24 ` Tim Chen
2010-08-20 13:19 ` Ingo Molnar
0 siblings, 1 reply; 5+ messages in thread
From: Tim Chen @ 2010-08-19 22:24 UTC (permalink / raw)
To: Ingo Molnar
Cc: Tim Chen, Linus Torvalds, Thomas Gleixner,
Frédéric Weisbecker, peterz, Andrew Morton,
linux-kernel, Andi Kleen, Tony Luck
> Ingo wrote:
>
> These are some rather impressive speedups!
>
> Have you tried to see what performance effects this change has on
smaller
> boxes? Just to see what flip side (if any) this change has.
>
I've done similar experiments with 2.6.35 kernel on smaller boxes. One is
on a dual-socket Westmere box (12 cores total, with HT). Another
experiment is on an old dual-socket Core 2 box (4 cores total, no HT)
On the 12-core Westmere box, I see a 250% increase for Ingo's mutex-test
program with my mutex patch but no significant difference in aim7's
fserver workload.
On the 4-core Core 2 box, I see the difference with the patch for both
mutex-test and aim7 fserver are negligible.
So far, it seems like the patch has not caused regression on smaller
systems. We'll put it through more workloads to check.
Tim
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 1/1] mutex: prevent optimistic spinning from spinning longer than neccessary (Repost)
2010-08-19 22:24 ` Tim Chen
@ 2010-08-20 13:19 ` Ingo Molnar
2010-08-20 16:54 ` Tim Chen
0 siblings, 1 reply; 5+ messages in thread
From: Ingo Molnar @ 2010-08-20 13:19 UTC (permalink / raw)
To: Tim Chen
Cc: Linus Torvalds, Thomas Gleixner, Frédéric Weisbecker,
peterz, Andrew Morton, linux-kernel, Andi Kleen, Tony Luck
* Tim Chen <tim.c.chen@linux.intel.com> wrote:
> > Ingo wrote:
> >
> > These are some rather impressive speedups!
> >
> > Have you tried to see what performance effects this change has on
> smaller
> > boxes? Just to see what flip side (if any) this change has.
> >
>
> I've done similar experiments with 2.6.35 kernel on smaller boxes. One is
> on a dual-socket Westmere box (12 cores total, with HT). Another
> experiment is on an old dual-socket Core 2 box (4 cores total, no HT)
>
> On the 12-core Westmere box, I see a 250% increase for Ingo's mutex-test
> program with my mutex patch but no significant difference in aim7's
> fserver workload.
>
> On the 4-core Core 2 box, I see the difference with the patch for both
> mutex-test and aim7 fserver are negligible.
Great!
> So far, it seems like the patch has not caused regression on smaller
> systems. We'll put it through more workloads to check.
Thanks! The performance results you've posted so far IMO more than justifies
its inclusion.
Ingo
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 1/1] mutex: prevent optimistic spinning from spinning longer than neccessary (Repost)
2010-08-20 13:19 ` Ingo Molnar
@ 2010-08-20 16:54 ` Tim Chen
0 siblings, 0 replies; 5+ messages in thread
From: Tim Chen @ 2010-08-20 16:54 UTC (permalink / raw)
To: Ingo Molnar
Cc: Linus Torvalds, Thomas Gleixner, Frédéric Weisbecker,
peterz, Andrew Morton, linux-kernel, Andi Kleen, Tony Luck
On Fri, 2010-08-20 at 15:19 +0200, Ingo Molnar wrote:
>
> Thanks! The performance results you've posted so far IMO more than justifies
> its inclusion.
>
> Ingo
Thanks to everyone for your review. I've updated the patch to add
comments explaining the change per suggestion from Andrew.
Signed-off-by: Tim Chen <tim.c.chen@linux.intel.com>
diff --git a/kernel/sched.c b/kernel/sched.c
index 41541d7..3747d04 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -3865,8 +3865,15 @@ int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner)
/*
* Owner changed, break to re-assess state.
*/
- if (lock->owner != owner)
+ if (lock->owner != owner) {
+ /* if lock has switched to a different owner,
+ * we have heavy contention. Return 0 to
+ * quit optimistic spinning and not contend further.
+ */
+ if (lock->owner)
+ return 0;
break;
+ }
/*
* Is that owner really running on that cpu?
^ permalink raw reply related [flat|nested] 5+ messages in thread
end of thread, other threads:[~2010-08-20 17:03 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2010-08-18 22:00 [PATCH 1/1] mutex: prevent optimistic spinning from spinning longer than neccessary (Repost) Tim Chen
2010-08-19 11:05 ` Ingo Molnar
2010-08-19 22:24 ` Tim Chen
2010-08-20 13:19 ` Ingo Molnar
2010-08-20 16:54 ` Tim Chen
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox