sched: prefer an idle cpu vs an idle sibling for BALANCE_WAKE

[ sorry if you get this twice, it seems like the first submission got lost ]

At Facebook we have a pretty heavily multi-threaded application that is sensitive to latency. We have been pulling forward the old SD_WAKE_IDLE code because it gives us a pretty significant performance gain (like 20%). It turns out this is because there are cases where the scheduler puts our task on a busy CPU when there are idle CPU's in the system. We verify this by reading the cpu_delay_req_avg_us from the scheduler netlink stuff. With our crappy patch we get much lower numbers vs baseline.

SD_BALANCE_WAKE is supposed to find us an idle cpu to run on, however it is just looking for an idle sibling, preferring affinity over all else. This is not helpful in all cases, and SD_BALANCE_WAKE's job is to find us an idle cpu, not garuntee affinity. Fix this by first trying to find an idle sibling, and then if the cpu is not idle fall through to the logic to find an idle cpu. With this patch we get slightly better performance than with our forward port of SD_WAKE_IDLE. Thanks,

Signed-off-by Josef Bacik <[email protected]>

Acked-by Rik van Riel <[email protected]>

---
 kernel/sched/fair.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

kernel/sched/fair.c +0 -0

index 241213b..03dafa3 100644

Quoted 10 lines · Josef Bacik

[ sorry if you get this twice, it seems like the first submission got lost ]

At Facebook we have a pretty heavily multi-threaded application that is sensitive to latency. We have been pulling forward the old SD_WAKE_IDLE code because it gives us a pretty significant performance gain (like 20%). It turns out this is because there are cases where the scheduler puts our task on a busy CPU when there are idle CPU's in the system. We verify this by reading the cpu_delay_req_avg_us from the scheduler netlink stuff. With our crappy patch we get much lower numbers vs baseline.

Quoted 7 lines

SD_BALANCE_WAKE is supposed to find us an idle cpu to run on, however it is just looking for an idle sibling, preferring affinity over all else. This is not helpful in all cases, and SD_BALANCE_WAKE's job is to find us an idle cpu, not garuntee affinity. Fix this by first trying to find an idle sibling, and then if the cpu is not idle fall through to the logic to find an idle cpu. With this patch we get slightly better performance than with our forward port of SD_WAKE_IDLE. Thanks,

The job description isn't really find idle. it's find least loaded.

Quoted 20 lines

Signed-off-by Josef Bacik <[email protected]>

Acked-by Rik van Riel <[email protected]>

---
 kernel/sched/fair.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

kernel/sched/fair.c +2 -1

index 241213b..03dafa3 100644
@@ -4766,7 +4766,8 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 
 	if (sd_flag & SD_BALANCE_WAKE) {
 		new_cpu = select_idle_sibling(p, prev_cpu);
-		goto unlock;
+		if (idle_cpu(new_cpu))
+			goto unlock;
 	}
 

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f · line 4773

Quoted 1 line

kernel/sched/fair.c +0 -0

 	while (sd) {

Instead of doing what for most will be a redundant idle_cpu() call, perhaps a couple cycles can be saved if you move the sd assignment above affine_sd assignment, and say if (!sd || idle_cpu(new_cpu)) ?

Isn't sd == NULL is most cases if you don't move the sd assignment before the affine_sd assignment?

Quoted 2 lines · Morten Rasmussen

Isn't sd == NULL is most cases if you don't move the sd assignment before the affine_sd assignment?

sd will usually be NULL regardless of where the assignment is, as SD_BALANCE_WAKE is usually off in ->flags. Josef is turning it on.

Quoted 5 lines · Mike Galbraith

Quoted 2 lines · Morten Rasmussen

Isn't sd == NULL is most cases if you don't move the sd assignment before the affine_sd assignment?

Quoted 2 lines

sd will usually be NULL regardless of where the assignment is, as SD_BALANCE_WAKE is usually off in ->flags. Josef is turning it on.

Right. SD_BALANCE_WAKE needs to set in the sd flags and the assignment has to happen before the break for this to work. I just don't see SD_BALANCE_WAKE being enabled for the sched_domain anywhere in the patch?

SD_BALANCE_WAKE is supposed to find us an idle cpu to run on, however

it is just looking for an idle sibling, preferring affinity over all else.

This is not helpful in all cases, and SD_BALANCE_WAKE's job is to find us an idle cpu, not garuntee affinity.

Fix this by first
trying to find an idle sibling, and then if the cpu is not idle fall through to the logic to find an idle cpu. With this patch we get slightly better performance than with our forward port of SD_WAKE_IDLE.

So maybe you want something like the below; that cures the thing Morten raised, and we continue looking for sd, even after we found affine_sd.

It also avoids the pointless idle_cpu() check Mike raised by making select_idle_sibling() return -1 if it doesn't find anything.

Then it continues doing the full balance IFF sd was set, which is keyed off of sd->flags.

And note (as Mike already said), BALANCE_WAKE does _NOT_ look for idle CPUs, it looks for the least loaded CPU. And its damn expensive.

Rewriting this entire thing is somewhere on the todo list :/

So maybe you want something like the below; that cures the thing Morten raised, and we continue looking for sd, even after we found affine_sd.

It also avoids the pointless idle_cpu() check Mike raised by making select_idle_sibling() return -1 if it doesn't find anything.

Then it continues doing the full balance IFF sd was set, which is keyed off of sd->flags.

And note (as Mike already said), BALANCE_WAKE does _NOT_ look for idle CPUs, it looks for the least loaded CPU. And its damn expensive.

Rewriting this entire thing is somewhere on the todo list :/

for_each_lower_domain(sd) {
         sg = sd->groups;
         do {
                 if (!cpumask_intersects(sched_group_cpus(sg),
                                         tsk_cpus_allowed(p)))
                         goto next;

                 for_each_cpu(i, sched_group_cpus(sg)) {
                         if (i == target || !idle_cpu(i))
                                 goto next;
                 }

                 return cpumask_first_and(sched_group_cpus(sg),
                                 tsk_cpus_allowed(p));
next:
                 sg = sg->next
         } while (sg != sd->groups);
}

We get all the schedule groups for the schedule domain and if any of the cpu's are not idle or the target then we skip the whole scheduling group. Isn't the scheduling group a group of CPU's? Why can't we pick an idle CPU in the group that has a none idle cpu or the target cpu? Thanks,

Quoted 10 lines · Peter Zijlstra

So maybe you want something like the below; that cures the thing Morten raised, and we continue looking for sd, even after we found affine_sd.

It also avoids the pointless idle_cpu() check Mike raised by making select_idle_sibling() return -1 if it doesn't find anything.

Then it continues doing the full balance IFF sd was set, which is keyed off of sd->flags.

Quoted 6 lines

And note (as Mike already said), BALANCE_WAKE does _NOT_ look for idle CPUs, it looks for the least loaded CPU. And its damn expensive.

Rewriting this entire thing is somewhere on the todo list :/

Ok I got this patch to give me the same performance as all our other crap, just need to apply this incremental

kernel/sched/fair.c +0 -0

index b71eb2b..e11cfec 100644
@@ -4761,13 +4761,10 @@ select_task_rq_fair(struct task_struct *p, int 

prev_cpu, int sd_flag, int wake_f

  		if (tmp->flags & sd_flag)
  			sd = tmp;

Quoted 13 lines · Josef Bacik

Ok I got this patch to give me the same performance as all our other crap, just need to apply this incremental

kernel/sched/fair.c +0 -0

index b71eb2b..e11cfec 100644
@@ -4761,13 +4761,10 @@ select_task_rq_fair(struct task_struct *p, int

prev_cpu, int sd_flag, int wake_f

   		if (tmp->flags & sd_flag)
   			sd = tmp;

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f · line 4764

Quoted 3 lines

kernel/sched/fair.c +0 -2

-		else if (!want_affine || (want_affine && affine_sd))
-			break;
   	}

That bit worries me a bit, because that causes us to have a weird definition for what sd is.

Without WAKE_AFFINE, sd is the biggest domain with BALANCE_WAKE (or any other sd_flag) set.

But with WAKE_AFFINE, its the first domain that satisfies the wake affine constraint of covering both the previous and waking cpu. It basically reduces sd to affine_sd.

Quoted 13 lines · Josef Bacik

Ok I got this patch to give me the same performance as all our other crap, just need to apply this incremental

kernel/sched/fair.c +0 -0

index b71eb2b..e11cfec 100644
@@ -4761,13 +4761,10 @@ select_task_rq_fair(struct task_struct *p, int

prev_cpu, int sd_flag, int wake_f

   		if (tmp->flags & sd_flag)
   			sd = tmp;

kernel/sched/fair.c

Quoted 3 lines

kernel/sched/fair.c +0 -2

-		else if (!want_affine || (want_affine && affine_sd))
-			break;
   	}

That bit worries me a bit, because that causes us to have a weird definition for what sd is.

Without WAKE_AFFINE, sd is the biggest domain with BALANCE_WAKE (or any other sd_flag) set.

But with WAKE_AFFINE, its the first domain that satisfies the wake affine constraint of covering both the previous and waking cpu. It basically reduces sd to affine_sd.

But now that I re-read your response I think this is even more what you were worried about than less.

Basically it comes down to if sd isn't set then we get shit performance.
I realize that this magic to find an idle cpu when sd is set is pretty
heavy handed, but it's obviously helpful in our case.

So let me ask this question. When do we want to do the heavy handed search and when do we not? With WAKE_AFFINE what is our ultimate goal vs the other SD's? If we don't have an sd that matches our sd_flags what should we be doing, should we just go with whatever cpu we're on and carry on? Thanks,

Josef

There is a policy vs mechanism thing here. Ingo and Peter are worried about the overhead in the mechanism of finding an idle CPU. Your measurements show that the policy of finding an idle CPU is the correct one.

Quoted 4 lines · Rik van Riel

There is a policy vs mechanism thing here. Ingo and Peter are worried about the overhead in the mechanism of finding an idle CPU. Your measurements show that the policy of finding an idle CPU is the correct one.

For his workload; I'm sure I can find a workload where it hurts.

In fact, I'm fairly sure Mike knows one from the top of his head, seeing how he's the one playing about trying to shrink that idle search :-)

Quoted 4 lines · Rik van Riel

There is a policy vs mechanism thing here. Ingo and Peter are worried about the overhead in the mechanism of finding an idle CPU. Your measurements show that the policy of finding an idle CPU is the correct one.

For his workload; I'm sure I can find a workload where it hurts.

In fact, I'm fairly sure Mike knows one from the top of his head, seeing how he's the one playing about trying to shrink that idle search :-)

Quoted 7 lines · Peter Zijlstra

Quoted 4 lines · Rik van Riel

There is a policy vs mechanism thing here. Ingo and Peter are worried about the overhead in the mechanism of finding an idle CPU. Your measurements show that the policy of finding an idle CPU is the correct one.

Quoted 4 lines

For his workload; I'm sure I can find a workload where it hurts.

In fact, I'm fairly sure Mike knows one from the top of his head, seeing how he's the one playing about trying to shrink that idle search :-)

Like anything where scheduling latency doesn't heavily dominate. Even if searching were free, bounces aren't, even for the very light.

Quoted 13 lines · Mike Galbraith

Quoted 11 lines · Peter Zijlstra

Quoted 4 lines · Rik van Riel

There is a policy vs mechanism thing here. Ingo and Peter are worried about the overhead in the mechanism of finding an idle CPU. Your measurements show that the policy of finding an idle CPU is the correct one.

For his workload; I'm sure I can find a workload where it hurts.

In fact, I'm fairly sure Mike knows one from the top of his head, seeing how he's the one playing about trying to shrink that idle search :-)

Quoted 3 lines

Like anything where scheduling latency doesn't heavily dominate. Even if searching were free, bounces aren't, even for the very light.

If scheduling latency doesn't hurt then making the search shouldn't matter should it? I get that migrations aren't free, but it seems like they can't hurt that much.

This application is huge, it's our
webserver, we're doing like 400 requests per second on these things, and hands down moving stuff to idle cpus is beating the pants off of staying on the same cpu. Is there a specific workload I could build a test for that you think this approach would hurt? Thanks,

Quoted 14 lines · Josef Bacik

Quoted 13 lines · Mike Galbraith

Quoted 11 lines · Peter Zijlstra

Quoted 4 lines · Rik van Riel

There is a policy vs mechanism thing here. Ingo and Peter are worried about the overhead in the mechanism of finding an idle CPU. Your measurements show that the policy of finding an idle CPU is the correct one.

For his workload; I'm sure I can find a workload where it hurts.

In fact, I'm fairly sure Mike knows one from the top of his head, seeing how he's the one playing about trying to shrink that idle search :-)

Quoted 7 lines

Quoted 3 lines

Like anything where scheduling latency doesn't heavily dominate. Even if searching were free, bounces aren't, even for the very light.

If scheduling latency doesn't hurt then making the search shouldn't matter should it? I get that migrations aren't free, but it seems like they can't hurt that much.

Nah, they don't hurt much :)

commit e0a79f529d5ba2507486d498b25da40911d95cf6

Author: Mike Galbraith <[email protected]>
Date:   Mon Jan 28 12:19:25 2013 +0100

sched: Fix select_idle_sibling() bouncing cow syndrome

If the previous CPU is cache affine and idle, select it.

The current implementation simply traverses the sd_llc domain, taking the first idle CPU encountered, which walks buddy pairs hand in hand over the package, inflicting excruciating pain.

1 tbench pair (worst case) in a 10 core + SMT package:

pre 15.22 MB/sec 1 procs
post 252.01 MB/sec 1 procs

Quoted 5 lines

This application is huge, it's our
webserver, we're doing like 400 requests per second on these things, and hands down moving stuff to idle cpus is beating the pants off of staying on the same cpu. Is there a specific workload I could build a test for that you think this approach would hurt? Thanks,

Search cost hurts fast movers, as does dragging even a small footprint all over the place, as you can see above.

Eesh ok, do you happen to remember how you ran tbench so I can add it to my tests here? In addition to fixing this problem we're also interested in tracking performance of new kernels so we don't have to do this "what the hell went wrong in the last 6 releases" dance every year, so I'm throwing every performance thing we find useful in our test infrastructure. Thanks,

Josef

Quoted 8 lines · Josef Bacik

Eesh ok, do you happen to remember how you ran tbench so I can add it to my tests here? In addition to fixing this problem we're also interested in tracking performance of new kernels so we don't have to do this "what the hell went wrong in the last 6 releases" dance every year, so I'm throwing every performance thing we find useful in our test infrastructure. Thanks,

Josef

Start a tbench server, then tbench -t 30 1 localhost. You're unlikely to find anything as painful as that bouncing cow bug was, but you won't have to look hard at all to find bounce pain.

There are also other loads like your server where waking to an idle cpu dominates all else, pgbench is one of those. In that case, you've got a 1:N waker/wakee relationship, and what matters above ALL else is when the mother of all work (the single server thread) wants a CPU, it had better get it NOW, else the load stalls. Likewise, 'mom' being preempted hurts truckloads. Perhaps your server has a similar thing going on, keeping wakees the hell away from the waker rules all.

Quoted 8 lines · Mike Galbraith

There are also other loads like your server where waking to an idle cpu dominates all else, pgbench is one of those. In that case, you've got a 1:N waker/wakee relationship, and what matters above ALL else is when the mother of all work (the single server thread) wants a CPU, it had better get it NOW, else the load stalls. Likewise, 'mom' being preempted hurts truckloads. Perhaps your server has a similar thing going on, keeping wakees the hell away from the waker rules all.

Yeah our server has two waker threads (one per numa node) and then the N number of wakee threads. I'll run tbench and pgbench with the new patches and see if there's a degredation. Thanks,

Ok I got this patch to give me the same performance as all our other crap, just need to apply this incremental

kernel/sched/fair.c +0 -0

index b71eb2b..e11cfec 100644
@@ -4761,13 +4761,10 @@ select_task_rq_fair(struct task_struct *p, int

prev_cpu, int sd_flag, int wake_f

         if (tmp->flags & sd_flag)
             sd = tmp;

     }

     if (sd_flag & SD_BALANCE_WAKE) {

So maybe you want something like the below; that cures the thing Morten raised, and we continue looking for sd, even after we found affine_sd.

It also avoids the pointless idle_cpu() check Mike raised by making select_idle_sibling() return -1 if it doesn't find anything.

Then it continues doing the full balance IFF sd was set, which is keyed off of sd->flags.

And note (as Mike already said), BALANCE_WAKE does _NOT_ look for idle CPUs, it looks for the least loaded CPU. And its damn expensive.

Rewriting this entire thing is somewhere on the todo list :/

Ugh I'm sorry, I've been running tests trying to get the numbers to look good when I noticed I was getting some inconsistencies in my results. Turns out I never actually tested your patch just plain, I had been testing it with BALANCE_WAKE, because I was under the assumption that was what was best for our workload. Since then I had fixed all of our scripts and such and noticed that it actually super duper sucks for us.
So testing with this original patch everything is significantly better
(this is with the default SD flags set, no changes at all).

So now that I've wasted a good bit of my time and everybody elses, can we go about pushing this patch upstream? If you are happy with it the way it is I'll go ahead and pull it into our kernels and just watch to make sure it ends upstream at some point. Thanks,

kernel/sched/fair.c +2 -2

@@ -5022,22 +5026,28 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 		 * If both cpu and prev_cpu are part of this domain,
 		 * cpu is a valid SD_WAKE_AFFINE target.
 		 */
-		if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
-		    cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
+		if (want_affine && !affine_sd &&
+		    (tmp->flags & SD_WAKE_AFFINE) &&

Quoted 8 lines · Peter Zijlstra

kernel/sched/fair.c +2 -2

@@ -5022,22 +5026,28 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
  		 * If both cpu and prev_cpu are part of this domain,
  		 * cpu is a valid SD_WAKE_AFFINE target.
  		 */
-		if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
-		    cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
+		if (want_affine && !affine_sd &&
+		    (tmp->flags & SD_WAKE_AFFINE) &&

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f · line 5038

Quoted 10 lines

kernel/sched/fair.c +3 -2

+		    cpumask_test_cpu(prev_cpu, sched_domain_span(tmp)))
  			affine_sd = tmp;
-			break;
-		}
 
  		if (tmp->flags & sd_flag)
  			sd = tmp;
+		else if (!want_affine || (want_affine && affine_sd))
+			break;
  	}

Hm, new_cpu == cpu.

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f · line 5043

Quoted 5 lines

kernel/sched/fair.c +3 -1

-	if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))
+	if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync)) {
  		prev_cpu = cpu;
+		sd = NULL; /* WAKE_AFFINE trumps BALANCE_WAKE */
+	}

If branch above is not taken, new_cpu remains cpu.

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f · line 5051

Quoted 9 lines

kernel/sched/fair.c +5 -2

  	if (sd_flag & SD_BALANCE_WAKE) {
-		new_cpu = select_idle_sibling(p, prev_cpu);
-		goto unlock;
+		int tmp = select_idle_sibling(p, prev_cpu);
+		if (tmp >= 0) {
+			new_cpu = tmp;
+			goto unlock;
+		}
  	}

If select_idle_sibling() returns -1, new_cpu remains cpu.

Quoted 1 line

Quoted 1 line

  	while (sd) {

If sd == NULL, we fall through and try to pull wakee despite nacked-by tsk_cpus_allowed() or wake_affine().

Quoted 5 lines · Mike Galbraith

On Thu, 2015-05-28 at 13:05 +0200, Peter Zijlstra wrote:

If sd == NULL, we fall through and try to pull wakee despite nacked-by tsk_cpus_allowed() or wake_affine().

So maybe add a check in the if (sd_flag & SD_BALANCE_WAKE) for something like this

if (tmp >= 0) {
	new_cpu = tmp;
	goto unlock;
} else if (!want_affine) {
	new_cpu = prev_cpu;
}

so we can make sure we're not being pushed onto a cpu that we aren't allowed on? Thanks,

Quoted 17 lines · Josef Bacik

Quoted 5 lines · Mike Galbraith

On Thu, 2015-05-28 at 13:05 +0200, Peter Zijlstra wrote:

If sd == NULL, we fall through and try to pull wakee despite nacked-by tsk_cpus_allowed() or wake_affine().

So maybe add a check in the if (sd_flag & SD_BALANCE_WAKE) for something like this

if (tmp >= 0) {
	new_cpu = tmp;
	goto unlock;
} else if (!want_affine) {
	new_cpu = prev_cpu;
}

Quoted 2 lines

so we can make sure we're not being pushed onto a cpu that we aren't allowed on? Thanks,

The buglet is a messenger methinks. You saying the patch helped without SD_BALANCE_WAKE being set is why I looked. The buglet would seem to say that preferring cache is not harming your load after all. It now sounds as though wake_wide() may be what you're squabbling with.

Things aren't adding up all that well.

Quoted 21 lines · Mike Galbraith

Quoted 17 lines · Josef Bacik

Quoted 5 lines · Mike Galbraith

On Thu, 2015-05-28 at 13:05 +0200, Peter Zijlstra wrote:

If sd == NULL, we fall through and try to pull wakee despite nacked-by tsk_cpus_allowed() or wake_affine().

So maybe add a check in the if (sd_flag & SD_BALANCE_WAKE) for something like this

if (tmp >= 0) {
	new_cpu = tmp;
	goto unlock;
} else if (!want_affine) {
	new_cpu = prev_cpu;
}

Quoted 2 lines

so we can make sure we're not being pushed onto a cpu that we aren't allowed on? Thanks,

Quoted 6 lines

The buglet is a messenger methinks. You saying the patch helped without SD_BALANCE_WAKE being set is why I looked. The buglet would seem to say that preferring cache is not harming your load after all. It now sounds as though wake_wide() may be what you're squabbling with.

Things aren't adding up all that well.

Yeah I'm horribly confused. The other thing is I had to switch clusters (I know, I know, I'm changing the parameters of the test). So these new boxes are haswell boxes, but basically the same otherwise, 2 socket 12 core with HT, just newer/faster CPUs. I'll re-run everything again and give the numbers so we're all on the same page again, but as it stands now I think we have this

3.10 with wake_idle forward ported - good
4.0 stock - 20% perf drop
4.0 w/ Peter's patch - good
4.0 w/ Peter's patch + SD_BALANCE_WAKE - 5% perf drop

I can do all these iterations again to verify, is there any other permutation you'd like to see? Thanks,

Quoted 41 lines · Josef Bacik

Quoted 21 lines · Mike Galbraith

Quoted 17 lines · Josef Bacik

Quoted 5 lines · Mike Galbraith

On Thu, 2015-05-28 at 13:05 +0200, Peter Zijlstra wrote:

If sd == NULL, we fall through and try to pull wakee despite nacked-by tsk_cpus_allowed() or wake_affine().

So maybe add a check in the if (sd_flag & SD_BALANCE_WAKE) for something like this

if (tmp >= 0) {
	new_cpu = tmp;
	goto unlock;
} else if (!want_affine) {
	new_cpu = prev_cpu;
}

Quoted 2 lines

so we can make sure we're not being pushed onto a cpu that we aren't allowed on? Thanks,

Quoted 6 lines

The buglet is a messenger methinks. You saying the patch helped without SD_BALANCE_WAKE being set is why I looked. The buglet would seem to say that preferring cache is not harming your load after all. It now sounds as though wake_wide() may be what you're squabbling with.

Things aren't adding up all that well.

Yeah I'm horribly confused. The other thing is I had to switch clusters (I know, I know, I'm changing the parameters of the test). So these new boxes are haswell boxes, but basically the same otherwise, 2 socket 12 core with HT, just newer/faster CPUs. I'll re-run everything again and give the numbers so we're all on the same page again, but as it stands now I think we have this

3.10 with wake_idle forward ported - good
4.0 stock - 20% perf drop
4.0 w/ Peter's patch - good
4.0 w/ Peter's patch + SD_BALANCE_WAKE - 5% perf drop

Quoted 2 lines

I can do all these iterations again to verify, is there any other permutation you'd like to see? Thanks,

Yeah, after re-baseline, please apply/poke these buttons individually in 4.0-virgin.

(cat /sys/kernel/debug/sched_features, prepend NO_, echo it back)

Now for 3.10 vs 4.0 our request duration time is the same if not slightly better on 4.0, so once the workers are doing their job everything is a-ok.

The problem is the probability the select queue >= 1 is way different on 4.0 vs 3.10. Normally this graph looks like an S, it's essentially 0 up to some RPS (requests per second) threshold and then shoots up to 100% after the threshold. I'll make a table of these graphs that hopefully makes sense, the numbers are different from run to run because of traffic and such, the test and control are both run at the same time. The header is the probability the select queue >=1

		25%	50%	75%

4.0 plain: 371 388 402
control: 386 394 402
difference: 15 6 0

So with 4.0 its basically a straight line, at lower RPS we are getting a higher probability of a select queue >= 1. We are measuring the cpu delay avg ms thing from the scheduler netlink stuff which is how I noticed it was scheduler related, our cpu delay is way higher on 4.0 than it is on 3.10 or 4.0 with the wake idle patch.

So the next test is NO_PREFER_IDLE. This is slightly better than 4.0 plain

		25%	50%	75%

NO_PREFER_IDLE: 399 401 414
control: 385 408 416
difference: 14 7 2

The numbers don't really show it well, but the graphs are closer together, it's slightly more s shaped, but still not great.

Next is NO_WAKE_WIDE, which is horrible

		25%	50%	75%

NO_WAKE_WIDE: 315 344 369
control: 373 380 388
difference: 58 36 19

This isn't even in the same ballpark, it's a way worse regression than plain.

The next bit is NO_WAKE_WIDE|NO_PREFER_IDLE, which is just as bad

		25%	50%	75%

EVERYTHING: 327 360 383
control: 381 390 399
difference: 54 30 19

Hm. Seems what this load should like best is if we detect 1:N, skip all of the routine gyrations, ie move the N (workers) infrequently, expend search cycles frequently only on the 1 (dispatch).

Ponder..

Hm. Seems what this load should like best is if we detect 1:N, skip all of the routine gyrations, ie move the N (workers) infrequently, expend search cycles frequently only on the 1 (dispatch).

Ponder..

If we're (read /me) on track, the bellow should help. Per my tracing, it may want a wee bit of toning down actually, though when I trace virgin source I expect to see the same, namely Xorg and friends having "wide-load" tattooed across their hindquarters earlier than they should.

Hm. Piddling with pgbench, which doesn't seem to collapse into a quivering heap when load exceeds cores these days, deltas weren't all that impressive, but it does appreciate the extra effort a bit, and a bit more when clients receive it as well.

If you test, and have time to piddle, you could try letting wake_wide() return 1 + sched_feat(WAKE_WIDE_IDLE) instead of adding only if wakee is the dispatcher.

Numbers from my little desktop box.

NO_WAKE_WIDE_IDLE
postgres@homer:~> pgbench.sh

clients 8       tps = 116697.697662
clients 12      tps = 115160.230523
clients 16      tps = 115569.804548
clients 20      tps = 117879.230514
clients 24      tps = 118281.753040
clients 28      tps = 116974.796627
clients 32      tps = 119082.163998   avg   117092.239   1.000

WAKE_WIDE_IDLE
postgres@homer:~> pgbench.sh

clients 8       tps = 124351.735754
clients 12      tps = 124419.673135
clients 16      tps = 125050.716498
clients 20      tps = 124813.042352
clients 24      tps = 126047.442307
clients 28      tps = 125373.719401
clients 32      tps = 126711.243383   avg   125252.510   1.069   1.000

WAKE_WIDE_IDLE (clients as well as server)
postgres@homer:~> pgbench.sh

clients 8       tps = 130539.795246
clients 12      tps = 128984.648554
clients 16      tps = 130564.386447
clients 20      tps = 129149.693118
clients 24      tps = 130211.119780
clients 28      tps = 130325.355433
clients 32      tps = 129585.656963   avg   129908.665   1.109   1.037

Quoted 31 lines · Mike Galbraith

Hm. Piddling with pgbench, which doesn't seem to collapse into a quivering heap when load exceeds cores these days, deltas weren't all that impressive, but it does appreciate the extra effort a bit, and a bit more when clients receive it as well.

If you test, and have time to piddle, you could try letting wake_wide() return 1 + sched_feat(WAKE_WIDE_IDLE) instead of adding only if wakee is the dispatcher.

Numbers from my little desktop box.

NO_WAKE_WIDE_IDLE
postgres@homer:~> pgbench.sh

clients 8       tps = 116697.697662
clients 12      tps = 115160.230523
clients 16      tps = 115569.804548
clients 20      tps = 117879.230514
clients 24      tps = 118281.753040
clients 28      tps = 116974.796627
clients 32      tps = 119082.163998   avg   117092.239   1.000

WAKE_WIDE_IDLE
postgres@homer:~> pgbench.sh

clients 8       tps = 124351.735754
clients 12      tps = 124419.673135
clients 16      tps = 125050.716498
clients 20      tps = 124813.042352
clients 24      tps = 126047.442307
clients 28      tps = 125373.719401
clients 32      tps = 126711.243383   avg   125252.510   1.069   1.000

Quoted 9 lines

WAKE_WIDE_IDLE (clients as well as server)
postgres@homer:~> pgbench.sh

clients 8       tps = 130539.795246
clients 12      tps = 128984.648554
clients 16      tps = 130564.386447
clients 20      tps = 129149.693118
clients 24      tps = 130211.119780
clients 28      tps = 130325.355433
clients 32      tps = 129585.656963   avg   129908.665   1.109   1.037

I have time for twiddling, we're carrying ye olde WAKE_IDLE until we get this solved upstream and then I'll rip out the old and put in the new, I'm happy to screw around until we're all happy. I'll throw this in a kernel this morning and run stuff today. Barring any issues with the testing infrastructure I should have results today. Thanks,

Quoted 32 lines · Josef Bacik

Quoted 31 lines · Mike Galbraith

Hm. Piddling with pgbench, which doesn't seem to collapse into a quivering heap when load exceeds cores these days, deltas weren't all that impressive, but it does appreciate the extra effort a bit, and a bit more when clients receive it as well.

If you test, and have time to piddle, you could try letting wake_wide() return 1 + sched_feat(WAKE_WIDE_IDLE) instead of adding only if wakee is the dispatcher.

Numbers from my little desktop box.

NO_WAKE_WIDE_IDLE
postgres@homer:~> pgbench.sh

clients 8       tps = 116697.697662
clients 12      tps = 115160.230523
clients 16      tps = 115569.804548
clients 20      tps = 117879.230514
clients 24      tps = 118281.753040
clients 28      tps = 116974.796627
clients 32      tps = 119082.163998   avg   117092.239   1.000

WAKE_WIDE_IDLE
postgres@homer:~> pgbench.sh

clients 8       tps = 124351.735754
clients 12      tps = 124419.673135
clients 16      tps = 125050.716498
clients 20      tps = 124813.042352
clients 24      tps = 126047.442307
clients 28      tps = 125373.719401
clients 32      tps = 126711.243383   avg   125252.510   1.069   1.000

Quoted 9 lines

Quoted 9 lines

WAKE_WIDE_IDLE (clients as well as server)
postgres@homer:~> pgbench.sh

clients 8       tps = 130539.795246
clients 12      tps = 128984.648554
clients 16      tps = 130564.386447
clients 20      tps = 129149.693118
clients 24      tps = 130211.119780
clients 28      tps = 130325.355433
clients 32      tps = 129585.656963   avg   129908.665   1.109   1.037

I had a typo in my script, so those desktop box numbers were all doing the same number of clients. It doesn't invalidate anything, but the individual deltas are just run to run variance.. not to mention that single cache box is not all that interesting for this anyway. That happens when interconnect becomes a player.

Quoted 5 lines

I have time for twiddling, we're carrying ye olde WAKE_IDLE until we get this solved upstream and then I'll rip out the old and put in the new, I'm happy to screw around until we're all happy. I'll throw this in a kernel this morning and run stuff today. Barring any issues with the testing infrastructure I should have results today. Thanks,

I'll be interested in your results. Taking pgbench to a little NUMA box, I'm seeing _nada_ outside of variance with master (crap). I have a way to win significantly for _older_ kernels, and that win over master _may_ provide some useful insight, but I don't trust postgres/pgbench as far as I can toss the planet, so don't have a warm fuzzy about trying to use it to approximate your real world load.

BTW, what's your topology look like (numactl --hardware).

So the NO_WAKE_WIDE_IDLE results are very good, almost the same as the baseline with a slight regression at lower RPS and a slight improvement at high RPS.

Quoted 3 lines · Josef Bacik

So the NO_WAKE_WIDE_IDLE results are very good, almost the same as the baseline with a slight regression at lower RPS and a slight improvement at high RPS.

Good. I can likely drop the rest then (I like dinky, so do CPUs;). I'm not real keen on the feature unless your numbers are really good, and odds are that ain't gonna happen.

Quoted 9 lines · Mike Galbraith

Quoted 3 lines · Josef Bacik

So the NO_WAKE_WIDE_IDLE results are very good, almost the same as the baseline with a slight regression at lower RPS and a slight improvement at high RPS.

Good. I can likely drop the rest then (I like dinky, so do CPUs;). I'm not real keen on the feature unless your numbers are really good, and odds are that ain't gonna happen.

More extensive testing in pedantic-man mode increased my confidence of that enough to sign off and ship the dirt simple version. Any further twiddles should grow their own wings if they want to fly anyway, the simplest form helps your real world load, as well as the not so real pgbench, my numbers for that below.

The WAKE_WIDE_IDLE run was basically the same so I'm good with the KISS version. I'll run that through the load tests this morning and let you know how it goes. I'm still seeing a slight regression at lower RPS, but it's like 1-2%, compared to ~15%.

Quoted 9 lines · Mike Galbraith

Quoted 3 lines · Josef Bacik

So the NO_WAKE_WIDE_IDLE results are very good, almost the same as the baseline with a slight regression at lower RPS and a slight improvement at high RPS.

Good. I can likely drop the rest then (I like dinky, so do CPUs;). I'm not real keen on the feature unless your numbers are really good, and odds are that ain't gonna happen.

More extensive testing in pedantic-man mode increased my confidence of that enough to sign off and ship the dirt simple version. Any further twiddles should grow their own wings if they want to fly anyway, the simplest form helps your real world load, as well as the not so real pgbench, my numbers for that below.

virgin master, 2 socket box
postgres@nessler:~> pgbench.sh

clients 12      tps = 96233.854271     1.000
clients 24      tps = 142234.686166    1.000
clients 36      tps = 148433.534531    1.000
clients 48      tps = 133105.634302    1.000
clients 60      tps = 128903.080371    1.000
clients 72      tps = 128591.821782    1.000
clients 84      tps = 114445.967116    1.000
clients 96      tps = 109803.557524    1.000    avg   125219.017   1.000

V3 (KISS, below)
postgres@nessler:~> pgbench.sh

clients 12      tps = 120793.023637    1.255
clients 24      tps = 144668.961468    1.017
clients 36      tps = 156705.239251    1.055
clients 48      tps = 152004.886893    1.141
clients 60      tps = 138582.113864    1.075
clients 72      tps = 136286.891104    1.059
clients 84      tps = 137420.986043    1.200
clients 96      tps = 135199.060242    1.231   avg   140207.645   1.119   1.000

V2 NO_WAKE_WIDE_IDLE
postgres@nessler:~> pgbench.sh

clients 12      tps = 121821.966162    1.265
clients 24      tps = 146446.388366    1.029
clients 36      tps = 151373.362190    1.019
clients 48      tps = 156806.730746    1.178
clients 60      tps = 133933.491567    1.039
clients 72      tps = 131460.489424    1.022
clients 84      tps = 130859.340261    1.143
clients 96      tps = 130787.476584    1.191   avg   137936.155   1.101   0.983

V2 WAKE_WIDE_IDLE (crawl in a hole feature, you're dead) postgres@nessler:~> pgbench.sh

clients 12      tps = 121297.791570
clients 24      tps = 145939.488312
clients 36      tps = 155336.090263
clients 48      tps = 149018.245323
clients 60      tps = 136730.079391
clients 72      tps = 134886.116831
clients 84      tps = 130493.283398
clients 96      tps = 126043.336074

sched: beef up wake_wide()

Josef Bacik reported that Facebook sees better performance with their 1:N load (1 dispatch/node, N workers/node) when carrying an old patch to try very hard to wake to an idle CPU. While looking at wake_wide(), I noticed that it doesn't pay attention to wakeup of the 1:N waker, returning 1 only when the 1:N waker is waking one of its minions.

Correct that, and don't bother doing domain traversal when we know that all we need to do is check for an idle cpu.

Signed-off-by Mike Galbraith <[email protected]>

kernel/sched/fair.c +8 -0

+/*
+ * Detect 1:N waker/wakee relationship via a switching-frequency heuristic.
+ * A waker of many should wake a different task than the one last awakened
+ * at a frequency roughly N times higher than one of its wakees.  In order
+ * to determine whether we should let the load spread vs consolodating to
+ * shared cache, we look for a minimum 'flip' frequency of llc_size in one
+ * partner, and a factor of lls_size higher frequency in the other.  With
+ * both conditions met, we can be relatively sure that we are seeing a 1:N

kernel/sched/fair.c +1 -0

+	return 1;
 }

@@ -5021,14 +5015,17 @@ select_task_rq_fair(struct task_struct *
 {
 	struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
 	int cpu = smp_processor_id();

kernel/sched/fair.c +1 -0

+
 	for_each_domain(cpu, tmp) {
 		if (!(tmp->flags & SD_LOAD_BALANCE))
 			continue;

Quoted 17 lines · Mike Galbraith

kernel/sched/fair.c +12 -0

+/*
+ * Detect 1:N waker/wakee relationship via a switching-frequency heuristic.
+ * A waker of many should wake a different task than the one last awakened
+ * at a frequency roughly N times higher than one of its wakees.  In order
+ * to determine whether we should let the load spread vs consolodating to
+ * shared cache, we look for a minimum 'flip' frequency of llc_size in one
+ * partner, and a factor of lls_size higher frequency in the other.  With
+ * both conditions met, we can be relatively sure that we are seeing a 1:N
+ * relationship, and that load size exceeds socket size.
+ */
 static int wake_wide(struct task_struct *p)
 {
+	unsigned int waker_flips = current->wakee_flips;
+	unsigned int wakee_flips = p->wakee_flips;
 	int factor = this_cpu_read(sd_llc_size);

kernel/sched/fair.c static long effective_load(struct task_g · line 4750

Quoted 2 lines

kernel/sched/fair.c +2 -0

+	if (waker_flips < wakee_flips)
+		swap(waker_flips, wakee_flips);

This makes the wakee/waker names useless, the end result is more like wakee_flips := client_flips, waker_flips := server_flips.

kernel/sched/fair.c static long effective_load(struct task_g · line 4752

Quoted 2 lines

kernel/sched/fair.c +2 -0

+	if (wakee_flips < factor || waker_flips < wakee_flips * factor)
+		return 0;

I don't get the first condition... why would the client ever flip? It only talks to that one server.

Quoted 8 lines

kernel/sched/fair.c +1 -0

@@ -5021,14 +5015,17 @@ select_task_rq_fair(struct task_struct *
 {
 	struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
 	int cpu = smp_processor_id();
+	int new_cpu = prev_cpu;
 	int want_affine = 0;
 	int sync = wake_flags & WF_SYNC;
 

kernel/sched/fair.c select_task_rq_fair(struct task_struct * · line 5027

Quoted 6 lines

kernel/sched/fair.c +5 -0

 	rcu_read_lock();
+	if (sd_flag & SD_BALANCE_WAKE) {
+		want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, tsk_cpus_allowed(p));
+		if (!want_affine)
+			goto select_idle;
+	}

So this preserves/makes worse the bug Morten spotted, even without want_affine we should still attempt SD_BALANCE_WAKE if set.

Quoted 18 lines · Peter Zijlstra

Quoted 17 lines · Mike Galbraith

kernel/sched/fair.c +12 -0

+/*
+ * Detect 1:N waker/wakee relationship via a switching-frequency heuristic.
+ * A waker of many should wake a different task than the one last awakened
+ * at a frequency roughly N times higher than one of its wakees.  In order
+ * to determine whether we should let the load spread vs consolodating to
+ * shared cache, we look for a minimum 'flip' frequency of llc_size in one
+ * partner, and a factor of lls_size higher frequency in the other.  With
+ * both conditions met, we can be relatively sure that we are seeing a 1:N
+ * relationship, and that load size exceeds socket size.
+ */
 static int wake_wide(struct task_struct *p)
 {
+	unsigned int waker_flips = current->wakee_flips;
+	unsigned int wakee_flips = p->wakee_flips;
 	int factor = this_cpu_read(sd_llc_size);

Quoted 5 lines

kernel/sched/fair.c static long effective_load(struct task_g · line 4750

Quoted 2 lines

kernel/sched/fair.c +2 -0

+	if (waker_flips < wakee_flips)
+		swap(waker_flips, wakee_flips);

This makes the wakee/waker names useless, the end result is more like wakee_flips := client_flips, waker_flips := server_flips.

True, perhaps a rename is in order.

Quoted 6 lines · Mike Galbraith

static int wake_wide(struct task_struct *p)
{

(quoted diff) +2 -0

+	unsigned int waker_flips = current->wakee_flips;
+	unsigned int wakee_flips = p->wakee_flips;
 	int factor = this_cpu_read(sd_llc_size);

Review

Quoted 2 lines

(quoted diff) +2 -0

+	if (waker_flips < wakee_flips)
+		swap(waker_flips, wakee_flips);

This makes the wakee/waker names useless, the end result is more like wakee_flips := client_flips, waker_flips := server_flips.

Review

Quoted 2 lines

(quoted diff) +2 -0

+	if (wakee_flips < factor || waker_flips < wakee_flips * factor)
+		return 0;

I don't get the first condition... why would the client ever flip? It only talks to that one server.

Quoted 8 lines

(quoted diff) +1 -0

@@ -5021,14 +5015,17 @@ select_task_rq_fair(struct task_struct *
 {
 	struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
 	int cpu = smp_processor_id();
+	int new_cpu = prev_cpu;
 	int want_affine = 0;
 	int sync = wake_flags & WF_SYNC;
 

Review select_task_rq_fair(struct task_struct * · line 5027

Quoted 6 lines

(quoted diff) +5 -0

 	rcu_read_lock();
+	if (sd_flag & SD_BALANCE_WAKE) {
+		want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, tsk_cpus_allowed(p));
+		if (!want_affine)
+			goto select_idle;
+	}

So this preserves/makes worse the bug Morten spotted, even without want_affine we should still attempt SD_BALANCE_WAKE if set.

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines · Mike Galbraith

  static int wake_wide(struct task_struct *p)
  {

(quoted diff) +2 -0

+	unsigned int waker_flips = current->wakee_flips;
+	unsigned int wakee_flips = p->wakee_flips;
  	int factor = this_cpu_read(sd_llc_size);

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	if (waker_flips < wakee_flips)
+		swap(waker_flips, wakee_flips);

This makes the wakee/waker names useless, the end result is more like wakee_flips := client_flips, waker_flips := server_flips.

I settled on master/slave plus hopefully improved comment block.

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	if (wakee_flips < factor || waker_flips < wakee_flips * factor)
+		return 0;

I don't get the first condition... why would the client ever flip? It only talks to that one server.

(tightening heuristic up a bit by one means or another would be good, but "if it ain't broke, don't fix it" applies for this patchlet)

Quoted 8 lines

Quoted 8 lines

kernel/sched/fair.c +1 -0

@@ -5021,14 +5015,17 @@ select_task_rq_fair(struct task_struct *
  {
  	struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
  	int cpu = smp_processor_id();
+	int new_cpu = prev_cpu;
  	int want_affine = 0;
  	int sync = wake_flags & WF_SYNC;
 

Quoted 9 lines

Review select_task_rq_fair(struct task_struct * · line 5027

Quoted 6 lines

(quoted diff) +5 -0

  	rcu_read_lock();
+	if (sd_flag & SD_BALANCE_WAKE) {
+		want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, tsk_cpus_allowed(p));
+		if (!want_affine)
+			goto select_idle;
+	}

So this preserves/makes worse the bug Morten spotted, even without want_affine we should still attempt SD_BALANCE_WAKE if set.

Fixed. wake_wide() may override want_affine as before, want_affine may override other ->flags as before, but a surviving domain selection now results in a full balance instead of a select_idle_sibling() call.

sched: beef up wake_wide()

Josef Bacik reported that Facebook sees better performance with their 1:N load (1 dispatch/node, N workers/node) when carrying an old patch to try very hard to wake to an idle CPU. While looking at wake_wide(), I noticed that it doesn't pay attention to the wakeup of a many partner waker, returning 1 only when waking one of its many partners.

Correct that, letting explicit domain flags override the heuristic.

While at it, adjust task_struct bits, we don't need a 64bit counter.

Signed-off-by Mike Galbraith <[email protected]>

Tested-by Josef Bacik <[email protected]>

Quoted 7 lines · Peter Zijlstra

Quoted 6 lines · Mike Galbraith

  static int wake_wide(struct task_struct *p)
  {

(quoted diff) +2 -0

+	unsigned int waker_flips = current->wakee_flips;
+	unsigned int wakee_flips = p->wakee_flips;
  	int factor = this_cpu_read(sd_llc_size);

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	if (waker_flips < wakee_flips)
+		swap(waker_flips, wakee_flips);

This makes the wakee/waker names useless, the end result is more like wakee_flips := client_flips, waker_flips := server_flips.

I settled on master/slave plus hopefully improved comment block.

Quoted 5 lines

Review

Quoted 2 lines

(quoted diff) +2 -0

+	if (wakee_flips < factor || waker_flips < wakee_flips * factor)
+		return 0;

I don't get the first condition... why would the client ever flip? It only talks to that one server.

(tightening heuristic up a bit by one means or another would be good, but "if it ain't broke, don't fix it" applies for this patchlet)

Quoted 8 lines

Quoted 8 lines

kernel/sched/fair.c +1 -0

@@ -5021,14 +5015,17 @@ select_task_rq_fair(struct task_struct *
  {
  	struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
  	int cpu = smp_processor_id();
+	int new_cpu = prev_cpu;
  	int want_affine = 0;
  	int sync = wake_flags & WF_SYNC;
 

Quoted 9 lines

Review select_task_rq_fair(struct task_struct * · line 5027

Quoted 6 lines

(quoted diff) +5 -0

  	rcu_read_lock();
+	if (sd_flag & SD_BALANCE_WAKE) {
+		want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, tsk_cpus_allowed(p));
+		if (!want_affine)
+			goto select_idle;
+	}

So this preserves/makes worse the bug Morten spotted, even without want_affine we should still attempt SD_BALANCE_WAKE if set.

Fixed. wake_wide() may override want_affine as before, want_affine may override other ->flags as before, but a surviving domain selection now results in a full balance instead of a select_idle_sibling() call.

sched: beef up wake_wide()

Josef Bacik reported that Facebook sees better performance with their 1:N load (1 dispatch/node, N workers/node) when carrying an old patch to try very hard to wake to an idle CPU. While looking at wake_wide(), I noticed that it doesn't pay attention to the wakeup of a many partner waker, returning 1 only when waking one of its many partners.

Correct that, letting explicit domain flags override the heuristic.

While at it, adjust task_struct bits, we don't need a 64bit counter.

Signed-off-by Mike Galbraith <[email protected]>

Tested-by Josef Bacik <[email protected]>

Not quite as awesome but still better than the baseline so we're good. Thanks,

Quoted 2 lines · Josef Bacik

Not quite as awesome but still better than the baseline so we're good. Thanks,

I personally like the other much better. We're not doing the user any favor by making the thing balance when SD_BALANCE_WAKE is set. Until such time as it ceases to be horribly painful, we're just paying a few cycles to help a theoretically existing masochist torture his box.

Quoted 2 lines · Josef Bacik

Not quite as awesome but still better than the baseline so we're good. Thanks,

I personally like the other much better. We're not doing the user any favor by making the thing balance when SD_BALANCE_WAKE is set. Until such time as it ceases to be horribly painful, we're just paying a few cycles to help a theoretically existing masochist torture his box.

OK, how about something like the below; it tightens things up by applying two rules:

- We really should not continue looking for a balancing domain once SD_LOAD_BALANCE is not set.

- SD (balance) flags should really be set in a single contiguous range, always starting at the bottom.

The latter means what if !want_affine and the (first) sd doesn't have BALANCE_WAKE set, we're done. Getting rid of (most of) that iteration junk you didn't like..

Hmm?

Quoted 13 lines · Peter Zijlstra

OK, how about something like the below; it tightens things up by applying two rules:

- We really should not continue looking for a balancing domain once SD_LOAD_BALANCE is not set.

- SD (balance) flags should really be set in a single contiguous range, always starting at the bottom.

The latter means what if !want_affine and the (first) sd doesn't have BALANCE_WAKE set, we're done. Getting rid of (most of) that iteration junk you didn't like..

Quoted 1 line

Hmm?

Yeah, that's better. It's not big hairy deal either way, it just bugged me to knowingly toss those cycles out the window ;-)

select_idle_sibling() looks kinda funny down there, but otoh when the day comes (hah) that we can just balance, it's closer to the exit.

Quoted 17 lines · Mike Galbraith

Quoted 14 lines · Peter Zijlstra

OK, how about something like the below; it tightens things up by applying two rules:

- We really should not continue looking for a balancing domain once SD_LOAD_BALANCE is not set.

- SD (balance) flags should really be set in a single contiguous range, always starting at the bottom.

The latter means what if !want_affine and the (first) sd doesn't have BALANCE_WAKE set, we're done. Getting rid of (most of) that iteration junk you didn't like..

Hmm?

Quoted 5 lines

Yeah, that's better. It's not big hairy deal either way, it just bugged me to knowingly toss those cycles out the window ;-)

select_idle_sibling() looks kinda funny down there, but otoh when the day comes (hah) that we can just balance, it's closer to the exit.

Right, not too pretty, does this look beter?

kernel/sched/fair.c +2 -1

@@ -5041,17 +5037,17 @@ select_task_rq_fair(struct task_struct *
 
 		if (tmp->flags & sd_flag)
 			sd = tmp;
+		else if (!want_affine)
+			break;
 	}
 
-	if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))

There's a buglet,

We'll not look for a idle cpu when wake_wide() naks want_affine.

Quoted 3 lines · Mike Galbraith

There's a buglet,

We'll not look for a idle cpu when wake_wide() naks want_affine.

*sigh* indeed.. fixing that'll bring us very close to what we started out wiht..

The one XXX there raises the question on whether we should always so select_idle_sibling() if we do not have a suitable balance flag, or only on wakeups.

Quoted 11 lines · Peter Zijlstra

Quoted 3 lines · Mike Galbraith

There's a buglet,

We'll not look for a idle cpu when wake_wide() naks want_affine.

*sigh* indeed.. fixing that'll bring us very close to what we started out wiht..

The one XXX there raises the question on whether we should always so select_idle_sibling() if we do not have a suitable balance flag, or only on wakeups.

That's what I've been sitting here waffling over, finally convinced myself that should the user turn FORX/EXEC off, he shouldn't find that a substitute quietly slipped in.. though otoh.. crap, guess I'm not done waffling after all. Yeah, this will work just fine ;-)

(typos fixed)

We happy with this or should I wait for more patches to fly by before I test something ;)?

Quoted 2 lines · Josef Bacik

We happy with this or should I wait for more patches to fly by before I test something ;)?

Yeah, it should be The End time.

In fact, select_idle_sibling() is already too expensive on current server hardware (far too damn many cpus in a LLC domain).

Quoted 2 lines · Peter Zijlstra

In fact, select_idle_sibling() is already too expensive on current server hardware (far too damn many cpus in a LLC domain).

Yup. I've played with rate limiting motion per task because of that. Packages have gotten way too damn big.

Quoted 7 lines · Mike Galbraith

Quoted 2 lines · Peter Zijlstra

In fact, select_idle_sibling() is already too expensive on current server hardware (far too damn many cpus in a LLC domain).

Yup. I've played with rate limiting motion per task because of that. Packages have gotten way too damn big.

What's the biggest you've seen?

Quoted 2 lines

What's the biggest you've seen?

Quoted 3 lines · Ingo Molnar

Quoted 2 lines

What's the biggest you've seen?

Wikipedia here: http://en.wikipedia.org/wiki/Haswell_%28microarchitecture%29

Tell us HSW-E[PX] have 18 cores 36 thread SKUs.

But yes, what Mike says, its bound to only get bigger.

Quoted 3 lines · Ingo Molnar

Quoted 2 lines

What's the biggest you've seen?

Wikipedia here: http://en.wikipedia.org/wiki/Haswell_%28microarchitecture%29

Tell us HSW-E[PX] have 18 cores 36 thread SKUs.

But yes, what Mike says, its bound to only get bigger.

At Facebook we have a pretty heavily multi-threaded application that is sensitive to latency. We have been pulling forward the old SD_WAKE_IDLE code because it gives us a pretty significant performance gain (like 20%). It turns out this is because there are cases where the scheduler puts our task on a busy CPU when there are idle CPU's in the system. We verify this by reading the cpu_delay_req_avg_us from the scheduler netlink stuff. With our crappy patch we get much lower numbers vs baseline.