Skip to contentSkip to conversation

Minor scheduler fix to get rid of skipping in xmms

PATCH Andrew Theurer 2 participants 5 messages Sep 11, 2003

lore
Share & tools
lore
#0 lore raw
Quoted 10 lines · Robert Love
Quoted 3 lines

There are a _lot_ of scheduler changes in 2.6-mm, and who knows which ones are an improvement, a detriment, and a noop?

We know that sched-2.6.0-test2-mm2-A3.patch caused the regression, and we now that sched-CAN_MIGRATE_TASK-fix.patch mostly fixed it up.

What we don't know is whether the thing which sched-CAN_MIGRATE_TASK-fix.patch
fixed was the thing which sched-2.6.0-test2-mm2-A3.patch broke.

Sorry for jumping into this late. I didn't even know the can_migrate patch was being discussed, let alone in -mm :). And to be fair, this really is Ingo's aggressive idle steal patch.

Anyway, these patches are somewhat related. It would seem that A3's shortening the tasks' run time would not only slow performance beacuse of cache thrash, but could possibly break CAN_MIGRATE's cache warmth check, right? That in turn would stop load balancing from working well, leading to more idle time, which the CAN_MIGRATE patch sort of bypassed for idle cpus.

I see Nick's balance patch as somewhat harmless, at least combined with A3 patch. However, one concern is that the "ping-pong" steal interval is not really 200ms, but 200ms/(nr_cpus-1), which without A3, could show up as a problem, especially on an 8 way box. In addition, I do think there's a problem with num tasks we steal. It should not be imbalance/2, it should be:
max_load - (node_nr_running / num_cpus_node). If we steal any more than this, which is quite possible with imbalance/2, then it's likely this_cpu now has too many tasks, and some other cpu will steal again. Using *imbalance/2 works fine on 2-way smp, but I'm pretty sure we "over steal" tasks on 4 way and up. Anyway, I'm getting off topic here...

But Steve's latest results have me toally stumped. Why would a patch which shortens run time and probbaly thrashes cache improve a cpu bound workload like JBB? And why would a patch that makes sure idle cpus don't stay idle reduce performance by so much?

Steve, are you absolutely sure your latest results on test5 are correct? Any possibility the original results were the "good" ones?

FWIW, I have seen the CAN_MIGRATE patch make a huge difference, not just in testing, but a -real- enterprise application used in "production". And unlike JBB and Volano, there's no high rate of sched_yield either. They do have a high rate of cswitches, but only because their workload message driven. This patch made a 40% improvement on 4-way on a 2.4 distro kernel that has O(1).

-Andrew Theurer

#1 lore raw
Quoted 10 lines · Andrew Theurer
Quoted 7 lines · Robert Love
Quoted 3 lines

There are a _lot_ of scheduler changes in 2.6-mm, and who knows which ones are an improvement, a detriment, and a noop?

We know that sched-2.6.0-test2-mm2-A3.patch caused the regression, and we now that sched-CAN_MIGRATE_TASK-fix.patch mostly fixed it up.

Quoted 9 lines
Quoted 4 lines

What we don't know is whether the thing which sched-CAN_MIGRATE_TASK-fix.patch
fixed was the thing which sched-2.6.0-test2-mm2-A3.patch broke.

Sorry for jumping into this late. I didn't even know the can_migrate patch was being discussed, let alone in -mm :). And to be fair, this really is Ingo's aggressive idle steal patch.

Anyway, these patches are somewhat related. It would seem that A3's shortening the tasks' run time would not only slow performance beacuse of cache thrash, but could possibly break CAN_MIGRATE's cache warmth check, right? That in turn would stop load balancing from working well, leading to more idle time, which the CAN_MIGRATE patch sort of bypassed for idle cpus.

Yeah thats probably right. Good thinking.

Quoted 3 lines

I see Nick's balance patch as somewhat harmless, at least combined with A3 patch. However, one concern is that the "ping-pong" steal interval is not really 200ms, but 200ms/(nr_cpus-1), which without A3, could show up as a problem, especially on an 8 way box. In addition, I do think there's a problem with num tasks we steal. It should not be imbalance/2, it should be: max_load - (node_nr_running / num_cpus_node). If we steal any more than this, which is quite possible with imbalance/2, then it's likely this_cpu now has too many tasks, and some other cpu will steal again. Using *imbalance/2 works fine on 2-way smp, but I'm pretty sure we "over steal" tasks on 4 way and up. Anyway, I'm getting off topic here...

IIRC max_load is supposed to be the number of tasks on the runqueue being stolen from, isn't it?

#2 lore raw
Quoted 37 lines · Nick Piggin
Quoted 16 lines · Andrew Theurer
Quoted 10 lines · Robert Love
Quoted 2 lines

There are a _lot_ of scheduler changes in 2.6-mm, and who knows which ones are an improvement, a detriment, and a noop?

We know that sched-2.6.0-test2-mm2-A3.patch caused the regression, and we now that sched-CAN_MIGRATE_TASK-fix.patch mostly fixed it up.

What we don't know is whether the thing which sched-CAN_MIGRATE_TASK-fix.patch
fixed was the thing which sched-2.6.0-test2-mm2-A3.patch broke.

Sorry for jumping into this late. I didn't even know the can_migrate patch was being discussed, let alone in -mm :). And to be fair, this really is Ingo's aggressive idle steal patch.

Quoted 6 lines

Anyway, these patches are somewhat related. It would seem that A3's shortening the tasks' run time would not only slow performance beacuse of cache thrash, but could possibly break CAN_MIGRATE's cache warmth check, right? That in turn would stop load balancing from working well, leading to more idle time, which the CAN_MIGRATE patch sort of bypassed for idle cpus.

Yeah thats probably right. Good thinking.

Quoted 10 lines

I see Nick's balance patch as somewhat harmless, at least combined with A3 patch. However, one concern is that the "ping-pong" steal interval is not really 200ms, but 200ms/(nr_cpus-1), which without A3, could show up as a problem, especially on an 8 way box. In addition, I do think there's a problem with num tasks we steal. It should not be imbalance/2, it should
be: max_load - (node_nr_running / num_cpus_node). If we steal any more than this, which is quite possible with imbalance/2, then it's likely this_cpu now has too many tasks, and some other cpu will steal again. Using *imbalance/2 works fine on 2-way smp, but I'm pretty sure we "over steal" tasks on 4 way and up. Anyway, I'm getting off topic here...

Quoted 2 lines

IIRC max_load is supposed to be the number of tasks on the runqueue being stolen from, isn't it?

Yes, but I think I still got this wrong. Ideally, once we finish stealing, the busiest runqueue should not have more than node_nr_runing/nr_cpus_node, but more importantly, this_cpu should not have more than node_nr_running/nr_cpus_node, so maybe it should be:

min(a,b) where
a = max_load - load_average How much we are over the load_average
b = load_average - this_load How much we are under the load_average
load_average = node_nr_runing / nr_cpus_node.
node_nr_running can be summed as we look for the busiest queue, so it should not be too costly.
if min(a,b) is neagtive (this_cpu's runqueue length was greater than load_average) we don't steal at all.

#3 lore raw
Quoted 45 lines · Andrew Theurer
Quoted 39 lines · Nick Piggin
Quoted 17 lines · Andrew Theurer
Quoted 11 lines · Robert Love
Quoted 3 lines

There are a _lot_ of scheduler changes in 2.6-mm, and who knows which ones are an improvement, a detriment, and a noop?

We know that sched-2.6.0-test2-mm2-A3.patch caused the regression, and we now that sched-CAN_MIGRATE_TASK-fix.patch mostly fixed it up.

What we don't know is whether the thing which sched-CAN_MIGRATE_TASK-fix.patch
fixed was the thing which sched-2.6.0-test2-mm2-A3.patch broke.

Sorry for jumping into this late. I didn't even know the can_migrate patch was being discussed, let alone in -mm :). And to be fair, this really is Ingo's aggressive idle steal patch.

Quoted 7 lines

Anyway, these patches are somewhat related. It would seem that A3's shortening the tasks' run time would not only slow performance beacuse of cache thrash, but could possibly break CAN_MIGRATE's cache warmth check, right? That in turn would stop load balancing from working well, leading to more idle time, which the CAN_MIGRATE patch sort of bypassed for idle cpus.

Yeah thats probably right. Good thinking.

Quoted 10 lines

I see Nick's balance patch as somewhat harmless, at least combined with A3
patch. However, one concern is that the "ping-pong" steal interval is not
really 200ms, but 200ms/(nr_cpus-1), which without A3, could show up as a
problem, especially on an 8 way box. In addition, I do think there's a
problem with num tasks we steal. It should not be imbalance/2, it should
be: max_load - (node_nr_running / num_cpus_node). If we steal any more
than this, which is quite possible with imbalance/2, then it's likely
this_cpu now has too many tasks, and some other cpu will steal again. Using *imbalance/2 works fine on 2-way smp, but I'm pretty sure we "over steal" tasks on 4 way and up. Anyway, I'm getting off topic here...

Quoted 3 lines

IIRC max_load is supposed to be the number of tasks on the runqueue being stolen from, isn't it?

Quoted 9 lines

Yes, but I think I still got this wrong. Ideally, once we finish stealing, the busiest runqueue should not have more than node_nr_runing/nr_cpus_node, but more importantly, this_cpu should not have more than node_nr_running/nr_cpus_node, so maybe it should be:

min(a,b) where
a = max_load - load_average How much we are over the load_average
b = load_average - this_load How much we are under the load_average
load_average = node_nr_runing / nr_cpus_node.
node_nr_running can be summed as we look for the busiest queue, so it should not be too costly. if min(a,b) is neagtive (this_cpu's runqueue length was greater than load_average) we don't steal at all.

Oh OK you're thinking about balancing across the entire NUMA. I was just thinking it will eventually settle down, but you're right: its probably better to overdampen the balancing than to underdampen it.

#4 lore raw
Quoted 31 lines
Quoted 22 lines
Quoted 13 lines
Quoted 12 lines

I see Nick's balance patch as somewhat harmless, at least combined with A3 patch. However, one concern is that the "ping-pong" steal interval is not really 200ms, but 200ms/(nr_cpus-1), which without A3, could show up as a problem, especially on an 8 way box. In addition, I do think there's a problem with num tasks we steal. It should not be imbalance/2, it should be: max_load - (node_nr_running / num_cpus_node). If we steal any more than this, which is quite possible with imbalance/2, then it's likely this_cpu now has too many tasks, and some other cpu will steal again. Using *imbalance/2 works fine on 2-way smp, but I'm pretty sure we "over steal" tasks on 4 way and up. Anyway, I'm getting off topic here...

Quoted 2 lines

IIRC max_load is supposed to be the number of tasks on the runqueue being stolen from, isn't it?

Yes, but I think I still got this wrong. Ideally, once we finish stealing, the busiest runqueue should not have more than node_nr_runing/nr_cpus_node, but more importantly, this_cpu should not have more than
node_nr_running/nr_cpus_node, so maybe it should be:

Quoted 8 lines

min(a,b) where
a = max_load - load_average How much we are over the load_average
b = load_average - this_load How much we are under the load_average
load_average = node_nr_runing / nr_cpus_node. node_nr_running can be summed as we look for the busiest queue, so it should not be too costly.
if min(a,b) is neagtive (this_cpu's runqueue length was greater than load_average) we don't steal at all.

Quoted 3 lines

Oh OK you're thinking about balancing across the entire NUMA. I was just thinking it will eventually settle down, but you're right: its probably better to overdampen the balancing than to underdampen it.

Actually this is really geared towards within the node. The goal for each cpu in the node (or just a non NUMA system) should be to steal just enough to have rq->nr_running to be nr_running()/nr_cpus. I'm still not sure how many tasks we should really steal from internode balance.