Skip to contentSkip to conversation

sched: wakeup buddy

RFC PATCH In review Michael Wang 3 participants 16 messages Feb 28, 2013 – Mar 1, 2013

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 sched: wakeup buddy

wake_affine() stuff is trying to bind related tasks closely, but it doesn't work well according to the test on 'perf bench sched pipe' (thanks to Peter).

Besides, pgbench show that blindly using wake_affine() will eat a lot of performance.

Thus, we need a new solution, it should detect the tasks related to each other, bind them closely, take care the balance, latency and performance at the same time.

Feature wakeup buddy seems like a good solution (thanks to Mike for the hint).

The feature introduced waker, wakee pointer and their ref count, along with the new knob sysctl_sched_wakeup_buddy_ref.

Now in select_task_rq_fair(), when current (task B) try to wakeup p (task A), if match:

1. A->waker == B && A->wakee == B
2. A->waker_ref > sysctl_sched_wakeup_buddy_ref
3. A->wakee_ref > sysctl_sched_wakeup_buddy_ref

then A is the wakeup buddy of B, which means A and B is likely to utilize the memory of each other.

Thus, if B is also the wakeup buddy of A, which means no other task has destroyed their relationship, then A is likely to benefit from the cached data of B, make them running closely is likely to gain benefit.

This patch add the feature wakeup buddy, reorganized the logical of wake_affine() stuff with the new feature, by doing these, pgbench and 'perf bench sched pipe' perform better.

Highlight:
Default value of sysctl_sched_wakeup_buddy_ref is 8 temporarily, please let me know if some number perform better on your system, I'd like to make it bigger to make the decision more carefully, so we could provide the solution when it is really needed.

Comments are very welcomed.

Test:

	Test with a 12 cpu X86 server and tip 3.8.0-rc7.

	'perf bench sched pipe' show nearly double improvement.

	pgbench result:
					prev	post

                | db_size | clients |  tps  |   |  tps  |
                +---------+---------+-------+   +-------+
                | 22 MB   |       1 | 10794 |   | 10820 |
                | 22 MB   |       2 | 21567 |   | 21915 |
                | 22 MB   |       4 | 41621 |   | 42766 |
                | 22 MB   |       8 | 53883 |   | 60511 |       +12.30%
                | 22 MB   |      12 | 50818 |   | 57129 |       +12.42%
                | 22 MB   |      16 | 50463 |   | 59345 |       +17.60%
                | 22 MB   |      24 | 46698 |   | 63787 |       +36.59%
                | 22 MB   |      32 | 43404 |   | 62643 |       +44.33%

                | 7484 MB |       1 |  7974 |   |  8014 |
                | 7484 MB |       2 | 19341 |   | 19534 |
                | 7484 MB |       4 | 36808 |   | 38092 |
                | 7484 MB |       8 | 47821 |   | 51968 |       +8.67%
                | 7484 MB |      12 | 45913 |   | 52284 |       +13.88%
                | 7484 MB |      16 | 46478 |   | 54418 |       +17.08%
                | 7484 MB |      24 | 42793 |   | 56375 |       +31.74%
                | 7484 MB |      32 | 36329 |   | 55783 |       +53.55%
                
                | 15 GB   |       1 |  7636 |   |  7880 |       
                | 15 GB   |       2 | 19195 |   | 19477 |
                | 15 GB   |       4 | 35975 |   | 37962 |
                | 15 GB   |       8 | 47919 |   | 51558 |       +7.59%
                | 15 GB   |      12 | 45397 |   | 51163 |       +12.70%
                | 15 GB   |      16 | 45926 |   | 53912 |       +17.39%
                | 15 GB   |      24 | 42184 |   | 55343 |       +31.19%
                | 15 GB   |      32 | 35983 |   | 55358 |       +53.84%
---
 include/linux/sched.h |    8 ++++
 kernel/sched/fair.c   |   97 ++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sysctl.c       |   10 +++++
 3 files changed, 113 insertions(+), 2 deletions(-)
include/linux/sched.h +8 -0
index d211247..c5a02b3 100644
@@ -1235,6 +1235,10 @@ enum perf_event_task_context {
 	perf_nr_task_contexts,
 };
 
+#ifdef CONFIG_SMP
+extern unsigned int sysctl_sched_wakeup_buddy_ref;
+#endif
+
 struct task_struct {
 	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
 	void *stack;
@@ -1245,6 +1249,10 @@ struct task_struct {
 #ifdef CONFIG_SMP
 	struct llist_node wake_entry;
 	int on_cpu;
+	struct task_struct *waker;
+	struct task_struct *wakee;
+	unsigned int waker_ref;
+	unsigned int wakee_ref;
 #endif
 	int on_rq;
 
kernel/sched/fair.c +95 -2

115 lines not on this page · raw message

kernel/sysctl.c +10 -0
index c88878d..6845d24 100644
@@ -424,6 +424,16 @@ static struct ctl_table kern_table[] = {
 		.extra1		= &one,
 	},
 #endif
+#ifdef CONFIG_SMP
+	{
+		.procname	= "sched_wakeup_buddy_ref",
+		.data		= &sysctl_sched_wakeup_buddy_ref,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec_minmax,
+		.extra1		= &one,
+	},
+#endif
 #ifdef CONFIG_PROVE_LOCKING
 	{
 		.procname	= "prove_locking",
Signature · 1 line
1.7.4.1
#1 lore raw

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3441

Quoted 5 lines · Michael Wang
kernel/sched/fair.c +5 -0
+				/*
+				 * current is the only task on rq and it is
+				 * going to sleep, current cpu will be a nice
+				 * candidate for p to run on.
+				 */

The sync hint only means it might be going to sleep soon, and even then, there can still be enough execution overlap to be a win to schedule cross core. Sched pipe numbers will always be much prettier if you do wakeup cpu affine, as it's ~100% scheduler and ~100% sync. You may lose a lot on other stuff if you interpret the hint as gospel truth.

IMHO, sched pipe is a "how fat have I become" benchmark, not "how well do I perform". The scheduler performs well when it makes more work happen. Playing ping-pong with yourself is _exercise_, not a job :)

-Mike

#2 lore raw

Hi, Mike

Thanks for your reply.

Quoted 12 lines · Mike Galbraith

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3441

Quoted 5 lines · Michael Wang
kernel/sched/fair.c +5 -0
+				/*
+				 * current is the only task on rq and it is
+				 * going to sleep, current cpu will be a nice
+				 * candidate for p to run on.
+				 */

The sync hint only means it might be going to sleep soon, and even then, there can still be enough execution overlap to be a win to schedule cross core. Sched pipe numbers will always be much prettier if you do wakeup cpu affine, as it's ~100% scheduler and ~100% sync.

Hmm.. so it's the comparison between 'cache benefit - execution overlap' and 'latency - execution overlap'?

I could not estimate how many latency will be added to wait for current going to sleep (it should be faster than access cold data, isn't it?), but I really like the cache benefit, unless sync doesn't means current is going to sleep every time, but that's the promise of WF_SYNC, isn't it?

You may lose

Quoted 1 line

a lot on other stuff if you interpret the hint as gospel truth.

Could you please give more details on this point?

Quoted 4 lines

IMHO, sched pipe is a "how fat have I become" benchmark, not "how well do I perform". The scheduler performs well when it makes more work happen. Playing ping-pong with yourself is _exercise_, not a job :)

That's right, may be I'm using the wrong description, it's the ops/sec which has been doubled, that means 'fat', correct?

Regards,
Michael Wang

Quoted 9 lines

-Mike

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

#3 lore raw
Quoted 32 lines · Michael Wang

Hi, Mike

Thanks for your reply.

Quoted 12 lines · Mike Galbraith

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3441

Quoted 5 lines · Michael Wang
kernel/sched/fair.c +5 -0
+				/*
+				 * current is the only task on rq and it is
+				 * going to sleep, current cpu will be a nice
+				 * candidate for p to run on.
+				 */

The sync hint only means it might be going to sleep soon, and even then, there can still be enough execution overlap to be a win to schedule cross core. Sched pipe numbers will always be much prettier if you do wakeup cpu affine, as it's ~100% scheduler and ~100% sync.

Hmm.. so it's the comparison between 'cache benefit - execution overlap' and 'latency - execution overlap'?

I could not estimate how many latency will be added to wait for current going to sleep (it should be faster than access cold data, isn't it?), but I really like the cache benefit, unless sync doesn't means current is going to sleep every time, but that's the promise of WF_SYNC, isn't it?

You may lose

Quoted 1 line

a lot on other stuff if you interpret the hint as gospel truth.

Could you please give more details on this point?

Quoted 1 line
Quoted 6 lines
Quoted 3 lines

IMHO, sched pipe is a "how fat have I become" benchmark, not "how well do I perform". The scheduler performs well when it makes more work happen. Playing ping-pong with yourself is _exercise_, not a job :)

That's right, may be I'm using the wrong description, it's the ops/sec which has been doubled, that means 'fat', correct?

I mean could we say that more ops/sec means more works has been done?

Regards,
Michael Wang

Quoted 14 lines

Regards,
Michael Wang

Quoted 9 lines

-Mike

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

#5 lore raw
In reply to Michael Wang
Quoted 18 lines · Michael Wang

Hi, Mike

Thanks for your reply.

Quoted 12 lines · Mike Galbraith

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3441

Quoted 5 lines · Michael Wang
kernel/sched/fair.c +5 -0
+				/*
+				 * current is the only task on rq and it is
+				 * going to sleep, current cpu will be a nice
+				 * candidate for p to run on.
+				 */

The sync hint only means it might be going to sleep soon, and even then, there can still be enough execution overlap to be a win to schedule cross core. Sched pipe numbers will always be much prettier if you do wakeup cpu affine, as it's ~100% scheduler and ~100% sync.

Quoted 2 lines

Hmm.. so it's the comparison between 'cache benefit - execution overlap' and 'latency - execution overlap'?

Yeah. You'll always lose power cross core, and throughput breakeven and win depends on convertible overlap, and how much L2 miss etc costs. For sched pipe there is no win, but for other sync hint users there is.

Quoted 4 lines

I could not estimate how many latency will be added to wait for current going to sleep (it should be faster than access cold data, isn't it?), but I really like the cache benefit, unless sync doesn't means current is going to sleep every time, but that's the promise of WF_SYNC, isn't it?

It would be nice if it _were_ a promise, but it is not, it's a hint.

Quoted 4 lines

You may lose

Quoted 1 line

a lot on other stuff if you interpret the hint as gospel truth.

Could you please give more details on this point?

tbench, mysql+oltp, on and on use the sync hint, many things jabber on localhost, use the sync hint, and have been shown in cold hard numbers to benefit, some things massively from cross core scheduling. You lose for sure at extreme context rates, but it has to be pretty darn high to be a guaranteed loser.

That's why select_idle_sibling() is so very damn annoying.

Quoted 6 lines
Quoted 3 lines

IMHO, sched pipe is a "how fat have I become" benchmark, not "how well do I perform". The scheduler performs well when it makes more work happen. Playing ping-pong with yourself is _exercise_, not a job :)

That's right, may be I'm using the wrong description, it's the ops/sec which has been doubled, that means 'fat', correct?

In this case, it means you're not running a kernel with nohz on a chain, running two schedulers is more expensive than running one, and missing L2 each and every time hurts very badly when the load is ultra skinny.

-Mike

#4 lore raw
In reply to Michael Wang
Quoted 1 line · Michael Wang

I mean could we say that more ops/sec means more works has been done?

Sure. But it's fairly meaningless, it's all scheduler. Real tasks do more than schedule.

-Mike

#6 lore raw
In reply to Mike Galbraith
Quoted 26 lines · Mike Galbraith
Quoted 18 lines · Michael Wang

Hi, Mike

Thanks for your reply.

Quoted 12 lines · Mike Galbraith

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3441

Quoted 5 lines · Michael Wang
kernel/sched/fair.c +5 -0
+				/*
+				 * current is the only task on rq and it is
+				 * going to sleep, current cpu will be a nice
+				 * candidate for p to run on.
+				 */

The sync hint only means it might be going to sleep soon, and even then, there can still be enough execution overlap to be a win to schedule cross core. Sched pipe numbers will always be much prettier if you do wakeup cpu affine, as it's ~100% scheduler and ~100% sync.

Quoted 2 lines

Hmm.. so it's the comparison between 'cache benefit - execution overlap' and 'latency - execution overlap'?

Yeah. You'll always lose power cross core, and throughput breakeven and win depends on convertible overlap, and how much L2 miss etc costs. For sched pipe there is no win, but for other sync hint users there is.

Quoted 6 lines
Quoted 4 lines

I could not estimate how many latency will be added to wait for current going to sleep (it should be faster than access cold data, isn't it?), but I really like the cache benefit, unless sync doesn't means current is going to sleep every time, but that's the promise of WF_SYNC, isn't it?

It would be nice if it _were_ a promise, but it is not, it's a hint.

Bad to know :(

Should we fix it or this is by designed? The comments after WF_SYNC cheated me...

Regards,
Michael Wang

Quoted 26 lines
Quoted 5 lines

You may lose

Quoted 1 line

a lot on other stuff if you interpret the hint as gospel truth.

Could you please give more details on this point?

tbench, mysql+oltp, on and on use the sync hint, many things jabber on localhost, use the sync hint, and have been shown in cold hard numbers to benefit, some things massively from cross core scheduling. You lose for sure at extreme context rates, but it has to be pretty darn high to be a guaranteed loser.

That's why select_idle_sibling() is so very damn annoying.

Quoted 6 lines
Quoted 3 lines

IMHO, sched pipe is a "how fat have I become" benchmark, not "how well do I perform". The scheduler performs well when it makes more work happen. Playing ping-pong with yourself is _exercise_, not a job :)

That's right, may be I'm using the wrong description, it's the ops/sec which has been doubled, that means 'fat', correct?

In this case, it means you're not running a kernel with nohz on a chain, running two schedulers is more expensive than running one, and missing L2 each and every time hurts very badly when the load is ultra skinny.

-Mike

#7 lore raw
Quoted 8 lines · Michael Wang
Quoted 1 line · Mike Galbraith

It would be nice if it _were_ a promise, but it is not, it's a hint.

Bad to know :(

Should we fix it or this is by designed? The comments after WF_SYNC cheated me...

You can't fix it, because it's not busted. You can say "Ok guys, I'm off for a nap RSN" all you want, but that won't guarantee that nobody pokes you, and hands you something more useful to do than snoozing.

-Mike

#8 lore raw
Quoted 5 lines · Mike Galbraith
Quoted 4 lines · Michael Wang
Quoted 1 line · Mike Galbraith

It would be nice if it _were_ a promise, but it is not, it's a hint.

Quoted 8 lines
Quoted 4 lines

Bad to know :(

Should we fix it or this is by designed? The comments after WF_SYNC cheated me...

You can't fix it, because it's not busted. You can say "Ok guys, I'm off for a nap RSN" all you want, but that won't guarantee that nobody pokes you, and hands you something more useful to do than snoozing.

So sync still means current is going to sleep, what you concerned is this promise will be easily broken by other waker, correct?

Hmm.. may be you are right, if 'perf bench sched pipe' is not the one we should care, I have no reason to add this logical currently.

I will remove this plus branch, unless I found other benchmark could benefit a lot from it.

Besides this, how do you think about this idea?

Regards,
Michael Wang

Quoted 9 lines

-Mike

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

#9 lore raw
Quoted 11 lines · Michael Wang
Quoted 10 lines · Mike Galbraith
Quoted 8 lines · Michael Wang
Quoted 1 line · Mike Galbraith

It would be nice if it _were_ a promise, but it is not, it's a hint.

Bad to know :(

Should we fix it or this is by designed? The comments after WF_SYNC cheated me...

Quoted 6 lines
Quoted 3 lines

You can't fix it, because it's not busted. You can say "Ok guys, I'm off for a nap RSN" all you want, but that won't guarantee that nobody pokes you, and hands you something more useful to do than snoozing.

So sync still means current is going to sleep, what you concerned is this promise will be easily broken by other waker, correct?

That makes it a lie, and it can already have been one with no help. Just because you wake one sync does not mean you're not going to find another to wake. Smart tasks are taught to look before they leap.

Quoted 2 lines

Hmm.. may be you are right, if 'perf bench sched pipe' is not the one we should care, I have no reason to add this logical currently.

Well, there is reason to identify task relationships methinks, you just can't rely on the fact that you're alone on the rq at the moment, and doing a sync wakeup to bind tasks. They _will_ lie to you :)

Quoted 4 lines

I will remove this plus branch, unless I found other benchmark could benefit a lot from it.

Besides this, how do you think about this idea?

I like the idea of filtering true buddy pairs, and automagically detecting the point when 1:N wants spreading rather a lot (fwtw). I'll look closer at your method, but when it comes to implementation opinions, the only one I trust comes out of a box in front of me.

I'm somewhat.. "taste challenged", Peter and Ingo have some though :)

-Mike

#11 lore raw
In reply to Michael Wang

Hi Michael,

Quoted 22 lines · Michael Wang

wake_affine() stuff is trying to bind related tasks closely, but it doesn't work well according to the test on 'perf bench sched pipe' (thanks to Peter).

Besides, pgbench show that blindly using wake_affine() will eat a lot of performance.

Thus, we need a new solution, it should detect the tasks related to each other, bind them closely, take care the balance, latency and performance at the same time.

Feature wakeup buddy seems like a good solution (thanks to Mike for the hint).

The feature introduced waker, wakee pointer and their ref count, along with the new knob sysctl_sched_wakeup_buddy_ref.

Now in select_task_rq_fair(), when current (task B) try to wakeup p (task A), if match:

1. A->waker == B && A->wakee == B
2. A->waker_ref > sysctl_sched_wakeup_buddy_ref
3. A->wakee_ref > sysctl_sched_wakeup_buddy_ref

Quoted 6 lines

then A is the wakeup buddy of B, which means A and B is likely to utilize the memory of each other.

Thus, if B is also the wakeup buddy of A, which means no other task has destroyed their relationship, then A is likely to benefit from the cached data of B, make them running closely is likely to gain benefit.

Not sure if it should require bidirectional relationship. Looks like just for benchmarks. Isn't there a one-way relationship that could get a benefit from this? I don't know ;-)

Few nitpicks below..

Quoted 52 lines

This patch add the feature wakeup buddy, reorganized the logical of wake_affine() stuff with the new feature, by doing these, pgbench and 'perf bench sched pipe' perform better.

Highlight:
Default value of sysctl_sched_wakeup_buddy_ref is 8 temporarily, please let me know if some number perform better on your system, I'd like to make it bigger to make the decision more carefully, so we could provide the solution when it is really needed.

Comments are very welcomed.

Test:

	Test with a 12 cpu X86 server and tip 3.8.0-rc7.

	'perf bench sched pipe' show nearly double improvement.

	pgbench result:
					prev	post

                | db_size | clients |  tps  |   |  tps  |
                +---------+---------+-------+   +-------+
                | 22 MB   |       1 | 10794 |   | 10820 |
                | 22 MB   |       2 | 21567 |   | 21915 |
                | 22 MB   |       4 | 41621 |   | 42766 |
                | 22 MB   |       8 | 53883 |   | 60511 |       +12.30%
                | 22 MB   |      12 | 50818 |   | 57129 |       +12.42%
                | 22 MB   |      16 | 50463 |   | 59345 |       +17.60%
                | 22 MB   |      24 | 46698 |   | 63787 |       +36.59%
                | 22 MB   |      32 | 43404 |   | 62643 |       +44.33%

                | 7484 MB |       1 |  7974 |   |  8014 |
                | 7484 MB |       2 | 19341 |   | 19534 |
                | 7484 MB |       4 | 36808 |   | 38092 |
                | 7484 MB |       8 | 47821 |   | 51968 |       +8.67%
                | 7484 MB |      12 | 45913 |   | 52284 |       +13.88%
                | 7484 MB |      16 | 46478 |   | 54418 |       +17.08%
                | 7484 MB |      24 | 42793 |   | 56375 |       +31.74%
                | 7484 MB |      32 | 36329 |   | 55783 |       +53.55%
                
                | 15 GB   |       1 |  7636 |   |  7880 |       
                | 15 GB   |       2 | 19195 |   | 19477 |
                | 15 GB   |       4 | 35975 |   | 37962 |
                | 15 GB   |       8 | 47919 |   | 51558 |       +7.59%
                | 15 GB   |      12 | 45397 |   | 51163 |       +12.70%
                | 15 GB   |      16 | 45926 |   | 53912 |       +17.39%
                | 15 GB   |      24 | 42184 |   | 55343 |       +31.19%
                | 15 GB   |      32 | 35983 |   | 55358 |       +53.84%

---

[SNIP]

Quoted 5 lines
kernel/sched/fair.c +0 -0
index 81fa536..d5acfd8 100644

kernel/sched/fair.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 3182

Quoted 10 lines
kernel/sched/fair.c +7 -0
@@ -3173,6 +3173,75 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 }
 
 /*
+ * Reduce sysctl_sched_wakeup_buddy_ref will reduce the preparation time
+ * to active the wakeup buddy feature, and make it agile, however, this
+ * will increase the risk of misidentify.
+ *
+ * Check wakeup_buddy() for the usage.
+ */
+unsigned int sysctl_sched_wakeup_buddy_ref = 8UL;

It seems that just 8U (or even 8) is enough.

Quoted 19 lines
kernel/sched/fair.c +19 -0
+
+/*
+ * wakeup_buddy() help to check whether p1 is the wakeup buddy of p2.
+ *
+ * Return 1 for yes, 0 for no.
+*/
+static inline int wakeup_buddy(struct task_struct *p1, struct task_struct *p2)
+{
+	if (p1->waker != p2 || p1->wakee != p2)
+		return 0;
+
+	if (p1->waker_ref < sysctl_sched_wakeup_buddy_ref)
+		return 0;
+
+	if (p1->wakee_ref < sysctl_sched_wakeup_buddy_ref)
+		return 0;
+
+	return 1;
+}

[SNIP]

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3494

Quoted 6 lines
kernel/sched/fair.c +2 -0
@@ -3399,6 +3490,8 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)
 unlock:
 	rcu_read_unlock();
 
+	wakeup_ref(p);
+

Why did you call it here? Shouldn't it be on somewhere in the ttwu?

Quoted 24 lines
kernel/sched/fair.c +0 -0
 	return new_cpu;
 }
 
kernel/sysctl.c +10 -0
index c88878d..6845d24 100644
@@ -424,6 +424,16 @@ static struct ctl_table kern_table[] = {
 		.extra1		= &one,
 	},
 #endif
+#ifdef CONFIG_SMP
+	{
+		.procname	= "sched_wakeup_buddy_ref",
+		.data		= &sysctl_sched_wakeup_buddy_ref,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec_minmax,
+		.extra1		= &one,
+	},
+#endif
 #ifdef CONFIG_PROVE_LOCKING
 	{
 		.procname	= "prove_locking",
#12 lore raw
Quoted 3 lines · Namhyung Kim

Not sure if it should require bidirectional relationship. Looks like just for benchmarks. Isn't there a one-way relationship that could get a benefit from this? I don't know ;-)

?? Meaningful relationships are bare minimum bidirectional, how can you describe one connection and have it remain meaningful? I love "her" is unlikely to lead to anything meaningful if "she" doesn't know you exist.

-Mike

#13 lore raw

2013-02-28 (목), 11:06 +0100, Mike Galbraith:

Quoted 9 lines · Namhyung Kim
Quoted 4 lines

Not sure if it should require bidirectional relationship. Looks like just for benchmarks. Isn't there a one-way relationship that could get a benefit from this? I don't know ;-)

?? Meaningful relationships are bare minimum bidirectional, how can you describe one connection and have it remain meaningful? I love "her" is unlikely to lead to anything meaningful if "she" doesn't know you exist.

Maybe I misunderstood something. I was thinking about typical cooperation models like manager-worker, producer-consumer or pipeline and thought that they are usually one-way relationship in terms of the wakeup.

Thanks,
Namhyung

#10 lore raw
In reply to Mike Galbraith
Quoted 23 lines · Mike Galbraith
Quoted 11 lines · Michael Wang
Quoted 10 lines · Mike Galbraith
Quoted 8 lines · Michael Wang
Quoted 1 line · Mike Galbraith

It would be nice if it _were_ a promise, but it is not, it's a hint.

Bad to know :(

Should we fix it or this is by designed? The comments after WF_SYNC cheated me...

Quoted 6 lines
Quoted 3 lines

You can't fix it, because it's not busted. You can say "Ok guys, I'm off for a nap RSN" all you want, but that won't guarantee that nobody pokes you, and hands you something more useful to do than snoozing.

So sync still means current is going to sleep, what you concerned is this promise will be easily broken by other waker, correct?

That makes it a lie, and it can already have been one with no help. Just because you wake one sync does not mean you're not going to find another to wake. Smart tasks are taught to look before they leap.

Quoted 6 lines
Quoted 2 lines

Hmm.. may be you are right, if 'perf bench sched pipe' is not the one we should care, I have no reason to add this logical currently.

Well, there is reason to identify task relationships methinks, you just can't rely on the fact that you're alone on the rq at the moment, and doing a sync wakeup to bind tasks. They _will_ lie to you :)

I see.

Quoted 10 lines
Quoted 5 lines

I will remove this plus branch, unless I found other benchmark could benefit a lot from it.

Besides this, how do you think about this idea?

I like the idea of filtering true buddy pairs, and automagically detecting the point when 1:N wants spreading rather a lot (fwtw). I'll look closer at your method, but when it comes to implementation opinions, the only one I trust comes out of a box in front of me.

And please let me know how it works on your box ;-)

Regards,
Michael Wang

Quoted 11 lines

I'm somewhat.. "taste challenged", Peter and Ingo have some though :)

-Mike

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

#15 lore raw
In reply to Namhyung Kim

Hi, Namhyung

Thanks for your reply.

On 02/28/2013 05:25 PM, Namhyung Kim wrote:
[snip]

Quoted 7 lines
Quoted 3 lines

Thus, if B is also the wakeup buddy of A, which means no other task has destroyed their relationship, then A is likely to benefit from the cached data of B, make them running closely is likely to gain benefit.

Not sure if it should require bidirectional relationship. Looks like just for benchmarks. Isn't there a one-way relationship that could get a benefit from this? I don't know ;-)

That's one point :)

Actually I have tried the one-way case at very beginning, the performance is not good.

I think it was caused by that if A lost interesting on B and walking with C, then make A and B closely won't gain so many benefit, since the cached data of A is likely to benefit C not B now.

Quoted 63 lines

Few nitpicks below..

Quoted 52 lines

This patch add the feature wakeup buddy, reorganized the logical of wake_affine() stuff with the new feature, by doing these, pgbench and 'perf bench sched pipe' perform better.

Highlight:
Default value of sysctl_sched_wakeup_buddy_ref is 8 temporarily, please let me know if some number perform better on your system, I'd like to make it bigger to make the decision more carefully, so we could provide the solution when it is really needed.

Comments are very welcomed.

Test:

	Test with a 12 cpu X86 server and tip 3.8.0-rc7.

	'perf bench sched pipe' show nearly double improvement.

	pgbench result:
					prev	post

                | db_size | clients |  tps  |   |  tps  |
                +---------+---------+-------+   +-------+
                | 22 MB   |       1 | 10794 |   | 10820 |
                | 22 MB   |       2 | 21567 |   | 21915 |
                | 22 MB   |       4 | 41621 |   | 42766 |
                | 22 MB   |       8 | 53883 |   | 60511 |       +12.30%
                | 22 MB   |      12 | 50818 |   | 57129 |       +12.42%
                | 22 MB   |      16 | 50463 |   | 59345 |       +17.60%
                | 22 MB   |      24 | 46698 |   | 63787 |       +36.59%
                | 22 MB   |      32 | 43404 |   | 62643 |       +44.33%

                | 7484 MB |       1 |  7974 |   |  8014 |
                | 7484 MB |       2 | 19341 |   | 19534 |
                | 7484 MB |       4 | 36808 |   | 38092 |
                | 7484 MB |       8 | 47821 |   | 51968 |       +8.67%
                | 7484 MB |      12 | 45913 |   | 52284 |       +13.88%
                | 7484 MB |      16 | 46478 |   | 54418 |       +17.08%
                | 7484 MB |      24 | 42793 |   | 56375 |       +31.74%
                | 7484 MB |      32 | 36329 |   | 55783 |       +53.55%
                
                | 15 GB   |       1 |  7636 |   |  7880 |       
                | 15 GB   |       2 | 19195 |   | 19477 |
                | 15 GB   |       4 | 35975 |   | 37962 |
                | 15 GB   |       8 | 47919 |   | 51558 |       +7.59%
                | 15 GB   |      12 | 45397 |   | 51163 |       +12.70%
                | 15 GB   |      16 | 45926 |   | 53912 |       +17.39%
                | 15 GB   |      24 | 42184 |   | 55343 |       +31.19%
                | 15 GB   |      32 | 35983 |   | 55358 |       +53.84%

---

[SNIP]

Quoted 7 lines
kernel/sched/fair.c +0 -0
index 81fa536..d5acfd8 100644
@@ -3173,6 +3173,75 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 }
 
Quoted 10 lines

kernel/sched/fair.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 3182

Quoted 8 lines
kernel/sched/fair.c +7 -0
 /*
+ * Reduce sysctl_sched_wakeup_buddy_ref will reduce the preparation time
+ * to active the wakeup buddy feature, and make it agile, however, this
+ * will increase the risk of misidentify.
+ *
+ * Check wakeup_buddy() for the usage.
+ */
+unsigned int sysctl_sched_wakeup_buddy_ref = 8UL;

It seems that just 8U (or even 8) is enough.

I will correct it.

Quoted 21 lines
Quoted 20 lines
kernel/sched/fair.c +19 -0
+
+/*
+ * wakeup_buddy() help to check whether p1 is the wakeup buddy of p2.
+ *
+ * Return 1 for yes, 0 for no.
+*/
+static inline int wakeup_buddy(struct task_struct *p1, struct task_struct *p2)
+{
+	if (p1->waker != p2 || p1->wakee != p2)
+		return 0;
+
+	if (p1->waker_ref < sysctl_sched_wakeup_buddy_ref)
+		return 0;
+
+	if (p1->wakee_ref < sysctl_sched_wakeup_buddy_ref)
+		return 0;
+
+	return 1;
+}

[SNIP]

Quoted 8 lines

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags) · line 3494

Quoted 6 lines
kernel/sched/fair.c +2 -0
@@ -3399,6 +3490,8 @@ select_task_rq_fair(struct task_struct *p, int sd_flag, int wake_flags)
 unlock:
 	rcu_read_unlock();
 
+	wakeup_ref(p);
+

Why did you call it here? Shouldn't it be on somewhere in the ttwu?

I'd like to put the changes closely, just another 'bad' habit ;-)

But you notified me that I should add a check on WAKEUP flag, will correct it.

Regards,
Michael Wang

Quoted 32 lines
Quoted 16 lines
kernel/sched/fair.c +0 -0
 	return new_cpu;
 }
 
kernel/sysctl.c +3 -0
index c88878d..6845d24 100644
@@ -424,6 +424,16 @@ static struct ctl_table kern_table[] = {
 		.extra1		= &one,
 	},
 #endif
+#ifdef CONFIG_SMP
+	{
+		.procname	= "sched_wakeup_buddy_ref",

kernel/sysctl.c static struct ctl_table kern_table[] = { · line 439

Quoted 10 lines
kernel/sysctl.c +7 -0
+		.data		= &sysctl_sched_wakeup_buddy_ref,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec_minmax,
+		.extra1		= &one,
+	},
+#endif
 #ifdef CONFIG_PROVE_LOCKING
 	{
 		.procname	= "prove_locking",

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

#14 lore raw
In reply to Namhyung Kim
Quoted 7 lines · Namhyung Kim

2013-02-28 (목), 11:06 +0100, Mike Galbraith:

Quoted 6 lines · Namhyung Kim
Quoted 4 lines

Not sure if it should require bidirectional relationship. Looks like just for benchmarks. Isn't there a one-way relationship that could get a benefit from this? I don't know ;-)

Quoted 8 lines
Quoted 3 lines

?? Meaningful relationships are bare minimum bidirectional, how can you describe one connection and have it remain meaningful? I love "her" is unlikely to lead to anything meaningful if "she" doesn't know you exist.

Maybe I misunderstood something. I was thinking about typical cooperation models like manager-worker, producer-consumer or pipeline and thought that they are usually one-way relationship in terms of the wakeup.

I agree with Mike's point here, relax the restriction usually benefit one model but damage more.

The whole wake_affine() stuff is somewhat blindly, we image that the cache will benefit the wakee but could not estimate how much it is, and the formula contain too many elements, I'd prefer to gamble only when I'm likely to win, that will win less money, but lose less too ;-)

Regards,
Michael Wang

Quoted 11 lines

Thanks,
Namhyung

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