Skip to contentSkip to conversation

Database regression due to scheduler changes ?

DISCUSSION Brian Twichell 7 participants 17 messages Nov 7, 2005 – Nov 14, 2005 1 message not in the archive

lore
Share & tools
lore
#0 lore raw

Hi,

We observed a 1.5% regression in an OLTP database workload going from 2.6.13-rc4 to 2.6.13-rc5. The regression has been carried forward at least as far as 2.6.14-rc5.

Through experimentation, and through examining the changes that went into 2.6.13-rc5, we found that we can eliminate the regression in 2.6.13-rc5 with one straightforward change: eliminating the NUMA level from the CPU scheduler domain structures.

After observing this, we collected schedstats (provided below) to try to determine how the scheduler behaves differently when the NUMA level is eliminated. It appears to us that the scheduler is having more success in balancing in this case. We tried to duplicate this effect by changing parameters in the NUMA-level and SMP-level domain definitions to increase the aggressiveness of the balancing, but none of the changes could recoup the regression.

We suspect the regression was introduced in the scheduler changes that went into 2.6.13-rc1. However, the regression was hidden from us by a bug in include/asm-ppc64/topology.h that made ppc64 look non-NUMA from 2.6.13-rc1 through 2.6.13-rc4. That bug was fixed in 2.6.13-rc5. Unfortunately the workload does not run to completion on 2.6.12 or 2.6.13-rc1. We have measurements on 2.6.12-rc6-git7 that do not show the regression.

One alternative for fixing this in 2.6.13 would have been to #define ARCH_HAS_SCHED_DOMAINS and to introduce a ppc64-specific version of build_sched_domains that eliminates the NUMA-level domain for small (e.g. 4-way) ppc64 systems. However, ARCH_HAS_SCHED_DOMAINS has been eliminated from 2.6.14, and anyways that solution doesn't seem very encompassing to me.

So, at this point I am soliciting assistance from scheduler experts to determine how this regression can be eliminated. We are keen to prevent this regression from going into the next distro versions. Simply shipping a distro kernel with CONFIG_NUMA off isn't a viable option because we need it for our larger configurations.

Our system configuration is a 4-way 1.9 GHz Power5-based server. As the system supports SMT, it shows eight online CPUs.

Below are the schedstats. The first set is with the NUMA-level domain, while the second set is without the NUMA-level domain.

Cheers,
Brian Twichell

Schedstats (NUMA-level domain included)
----------------------------------------------------------------------
00:09:05--------------------------------------------------------------
2845 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
157( 5.52%) found both queues empty on current cpu
2688( 94.48%) found neither queue empty on current cpu

23287180 schedule()
1( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue

0 active_load_balance()
0 sched_balance_exec()

0.19/1.17 avg runtime/latency over all cpus (ms)

[scheduler domain #0]
1418943 load_balance()

    112240(  7.91%) called while idle
                        499(  0.44%) tried but failed to move any tasks
                      80433( 71.66%) found no busier group
                      31308( 27.89%) succeeded in moving at least one task
                                     (average imbalance:   1.549)
    316022( 22.27%) called while busy
                         21(  0.01%) tried but failed to move any tasks
                     220440( 69.75%) found no busier group
                      95561( 30.24%) succeeded in moving at least one task
                                     (average imbalance:   1.727)
    990681( 69.82%) called when newly idle
                        533(  0.05%) tried but failed to move any tasks
                     808816( 81.64%) found no busier group
                     181332( 18.30%) succeeded in moving at least one task
                                     (average imbalance:   1.500)

         0          sched_balance_exec() tried to push a task

[scheduler domain #1]

    922193          load_balance()
     85822(  9.31%) called while idle
                       4032(  4.70%) tried but failed to move any tasks
                      70982( 82.71%) found no busier group
                      10808( 12.59%) succeeded in moving at least one task
                                     (average imbalance:   1.348)
     27022(  2.93%) called while busy
                        106(  0.39%) tried but failed to move any tasks
                      25478( 94.29%) found no busier group
                       1438(  5.32%) succeeded in moving at least one task
                                     (average imbalance:   1.712)
    809349( 87.76%) called when newly idle
                       6967(  0.86%) tried but failed to move any tasks
                     757097( 93.54%) found no busier group
                      45285(  5.60%) succeeded in moving at least one task
                                     (average imbalance:   1.338)

         0          sched_balance_exec() tried to push a task

[scheduler domain #2]

    825662          load_balance()
     52074(  6.31%) called while idle
                      17791( 34.16%) tried but failed to move any tasks
                      32839( 63.06%) found no busier group
                       1444(  2.77%) succeeded in moving at least one task
                                     (average imbalance:   1.981)
      9524(  1.15%) called while busy
                       1072( 11.26%) tried but failed to move any tasks
                       7654( 80.37%) found no busier group
                        798(  8.38%) succeeded in moving at least one task
                                     (average imbalance:   2.976)
    764064( 92.54%) called when newly idle
                     262831( 34.40%) tried but failed to move any tasks
                     409353( 53.58%) found no busier group
                      91880( 12.03%) succeeded in moving at least one task
                                     (average imbalance:   2.518)

         0          sched_balance_exec() tried to push a task

Schedstats (NUMA-level domain eliminated)
----------------------------------------------------------------------
00:09:03--------------------------------------------------------------
2576 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
118( 4.58%) found both queues empty on current cpu
2458( 95.42%) found neither queue empty on current cpu

23617887 schedule()
1106774 goes idle
0( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue

0 active_load_balance()
0 sched_balance_exec()

0.19/1.10 avg runtime/latency over all cpus (ms)

[scheduler domain #0]
1810988 load_balance()

    153509(  8.48%) called while idle
                        680(  0.44%) tried but failed to move any tasks
                     104906( 68.34%) found no busier group
                      47923( 31.22%) succeeded in moving at least one task
                                     (average imbalance:   1.658)
    317016( 17.51%) called while busy
                         30(  0.01%) tried but failed to move any tasks
                     217438( 68.59%) found no busier group
                      99548( 31.40%) succeeded in moving at least one task
                                     (average imbalance:   1.831)
   1340463( 74.02%) called when newly idle
                        762(  0.06%) tried but failed to move any tasks
                    1092960( 81.54%) found no busier group
                     246741( 18.41%) succeeded in moving at least one task
                                     (average imbalance:   1.564)

         0          sched_balance_exec() tried to push a task

[scheduler domain #1]
1244187 load_balance()

    111326(  8.95%) called while idle
                       8396(  7.54%) tried but failed to move any tasks
                      71276( 64.02%) found no busier group
                      31654( 28.43%) succeeded in moving at least one task
                                     (average imbalance:   1.412)
     39138(  3.15%) called while busy
                        220(  0.56%) tried but failed to move any tasks
                      34676( 88.60%) found no busier group
                       4242( 10.84%) succeeded in moving at least one task
                                     (average imbalance:   1.360)
   1093723( 87.91%) called when newly idle
                      15971(  1.46%) tried but failed to move any tasks
                     932422( 85.25%) found no busier group
                     145330( 13.29%) succeeded in moving at least one task
                                     (average imbalance:   1.189)

         0          sched_balance_exec() tried to push a task
#1 lore raw

Brian,
If I am understanding the data you posted, it looks like you are useing
sched_yield extensivly in your database. This is known to have significant problems on SMP machines, and even bigger ones on NUMA machines, in part becouse the process doing the sched_yield may get rescheduled immediatly and not allow other processes to run (to free up whatever resource it's waiting for). This causes the processor to look busy to the scheduler and therefor the scheduler doesn't migrate other processes to the CPU that's spinning on sched_yield. On NUMA machines this is even more noticable as processes now have to migrate through an additional layer of the scheduler.

have to tried eliminating the sched_yield to see what difference it makes?

David Lang

Signature · 2 lines
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
 -- C.A.R. Hoare
#16 lore raw
In reply to Brian Twichell
Quoted 181 lines · Brian Twichell

Hi,

We observed a 1.5% regression in an OLTP database workload going from 2.6.13-rc4 to 2.6.13-rc5. The regression has been carried forward at least as far as 2.6.14-rc5.

Through experimentation, and through examining the changes that went into 2.6.13-rc5, we found that we can eliminate the regression in 2.6.13-rc5 with one straightforward change: eliminating the NUMA level from the CPU scheduler domain structures.

After observing this, we collected schedstats (provided below) to try to determine how the scheduler behaves differently when the NUMA level is eliminated. It appears to us that the scheduler is having more success in balancing in this case. We tried to duplicate this effect by changing parameters in the NUMA-level and SMP-level domain definitions to increase the aggressiveness of the balancing, but none of the changes could recoup the regression.

We suspect the regression was introduced in the scheduler changes that went into 2.6.13-rc1. However, the regression was hidden from us by a bug in include/asm-ppc64/topology.h that made ppc64 look non-NUMA from 2.6.13-rc1 through 2.6.13-rc4. That bug was fixed in 2.6.13-rc5. Unfortunately the workload does not run to completion on 2.6.12 or 2.6.13-rc1. We have measurements on 2.6.12-rc6-git7 that do not show the regression.

One alternative for fixing this in 2.6.13 would have been to #define ARCH_HAS_SCHED_DOMAINS and to introduce a ppc64-specific version of build_sched_domains that eliminates the NUMA-level domain for small (e.g. 4-way) ppc64 systems. However, ARCH_HAS_SCHED_DOMAINS has been eliminated from 2.6.14, and anyways that solution doesn't seem very encompassing to me.

So, at this point I am soliciting assistance from scheduler experts to determine how this regression can be eliminated. We are keen to prevent this regression from going into the next distro versions. Simply shipping a distro kernel with CONFIG_NUMA off isn't a viable option because we need it for our larger configurations.

Our system configuration is a 4-way 1.9 GHz Power5-based server. As the system supports SMT, it shows eight online CPUs.

Below are the schedstats. The first set is with the NUMA-level domain, while the second set is without the NUMA-level domain.

Cheers,
Brian Twichell

Schedstats (NUMA-level domain included)
----------------------------------------------------------------------
00:09:05--------------------------------------------------------------
2845 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
157( 5.52%) found both queues empty on current cpu
2688( 94.48%) found neither queue empty on current cpu

23287180 schedule()
1( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue

0 active_load_balance()
0 sched_balance_exec()

0.19/1.17 avg runtime/latency over all cpus (ms)

[scheduler domain #0]
1418943 load_balance()

    112240(  7.91%) called while idle
                        499(  0.44%) tried but failed to move any tasks
                      80433( 71.66%) found no busier group
                      31308( 27.89%) succeeded in moving at least one task
                                     (average imbalance:   1.549)
    316022( 22.27%) called while busy
                         21(  0.01%) tried but failed to move any tasks
                     220440( 69.75%) found no busier group
                      95561( 30.24%) succeeded in moving at least one task
                                     (average imbalance:   1.727)
    990681( 69.82%) called when newly idle
                        533(  0.05%) tried but failed to move any tasks
                     808816( 81.64%) found no busier group
                     181332( 18.30%) succeeded in moving at least one task
                                     (average imbalance:   1.500)

         0          sched_balance_exec() tried to push a task

[scheduler domain #1]

    922193          load_balance()
     85822(  9.31%) called while idle
                       4032(  4.70%) tried but failed to move any tasks
                      70982( 82.71%) found no busier group
                      10808( 12.59%) succeeded in moving at least one task
                                     (average imbalance:   1.348)
     27022(  2.93%) called while busy
                        106(  0.39%) tried but failed to move any tasks
                      25478( 94.29%) found no busier group
                       1438(  5.32%) succeeded in moving at least one task
                                     (average imbalance:   1.712)
    809349( 87.76%) called when newly idle
                       6967(  0.86%) tried but failed to move any tasks
                     757097( 93.54%) found no busier group
                      45285(  5.60%) succeeded in moving at least one task
                                     (average imbalance:   1.338)

         0          sched_balance_exec() tried to push a task

[scheduler domain #2]

    825662          load_balance()
     52074(  6.31%) called while idle
                      17791( 34.16%) tried but failed to move any tasks
                      32839( 63.06%) found no busier group
                       1444(  2.77%) succeeded in moving at least one task
                                     (average imbalance:   1.981)
      9524(  1.15%) called while busy
                       1072( 11.26%) tried but failed to move any tasks
                       7654( 80.37%) found no busier group
                        798(  8.38%) succeeded in moving at least one task
                                     (average imbalance:   2.976)
    764064( 92.54%) called when newly idle
                     262831( 34.40%) tried but failed to move any tasks
                     409353( 53.58%) found no busier group
                      91880( 12.03%) succeeded in moving at least one task
                                     (average imbalance:   2.518)

         0          sched_balance_exec() tried to push a task

Schedstats (NUMA-level domain eliminated)
----------------------------------------------------------------------
00:09:03--------------------------------------------------------------
2576 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
118( 4.58%) found both queues empty on current cpu
2458( 95.42%) found neither queue empty on current cpu

23617887 schedule()
1106774 goes idle
0( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue

0 active_load_balance()
0 sched_balance_exec()

0.19/1.10 avg runtime/latency over all cpus (ms)

[scheduler domain #0]
1810988 load_balance()

    153509(  8.48%) called while idle
                        680(  0.44%) tried but failed to move any tasks
                     104906( 68.34%) found no busier group
                      47923( 31.22%) succeeded in moving at least one task
                                     (average imbalance:   1.658)
    317016( 17.51%) called while busy
                         30(  0.01%) tried but failed to move any tasks
                     217438( 68.59%) found no busier group
                      99548( 31.40%) succeeded in moving at least one task
                                     (average imbalance:   1.831)
   1340463( 74.02%) called when newly idle
                        762(  0.06%) tried but failed to move any tasks
                    1092960( 81.54%) found no busier group
                     246741( 18.41%) succeeded in moving at least one task
                                     (average imbalance:   1.564)

         0          sched_balance_exec() tried to push a task

[scheduler domain #1]
1244187 load_balance()

    111326(  8.95%) called while idle
                       8396(  7.54%) tried but failed to move any tasks
                      71276( 64.02%) found no busier group
                      31654( 28.43%) succeeded in moving at least one task
                                     (average imbalance:   1.412)
     39138(  3.15%) called while busy
                        220(  0.56%) tried but failed to move any tasks
                      34676( 88.60%) found no busier group
                       4242( 10.84%) succeeded in moving at least one task
Quoted 9 lines
                                     (average imbalance:   1.360)
   1093723( 87.91%) called when newly idle
                      15971(  1.46%) tried but failed to move any tasks
                     932422( 85.25%) found no busier group
                     145330( 13.29%) succeeded in moving at least one task
                                     (average imbalance:   1.189)

         0          sched_balance_exec() tried to push a task

Can you change sched_yield() to usleep(1) or usleep(0) and see if that works. I found that in recent kernels sched_yield() just seems to spin (may not actually spin, but seems to with a high CPU usage).

Cheers,
Dick Johnson
Penguin : Linux version 2.6.13.4 on an i686 machine (5589.55 BogoMips). Warning : 98.36% of all statistics are fiction.
.

****************************************************************
The information transmitted in this message is confidential and may be privileged. Any review, retransmission, dissemination, or other use of this information by persons or entities other than the intended recipient is prohibited. If you are not the intended recipient, please notify Analogic Corporation immediately - by replying to this message or by sending an email to [email protected] - and destroy all copies of this information, including any attachments, without reading or disclosing them.

Thank you.

#2 lore raw
In reply to David Lang
Quoted 2 lines · David Lang

If I am understanding the data you posted, it looks like you are
useing sched_yield extensivly in your database.

Yes, I've seen problems in the past with workloads that use sched_yield heavily.

But bear in mind, the ~2700 sched_yields shown in the schedstats occurred over a 9 minute period. That means that sched_yield is being called at a rate of around 5 per second -- this is not a heavy user of sched_yield.

To put this into a broader perspective, this workload has around 270 tasks, and the context switch rate is around 45,000 per second.

#3 lore raw
Quoted 6 lines · Brian Twichell
Quoted 2 lines · David Lang

If I am understanding the data you posted, it looks like you are
useing sched_yield extensivly in your database.

Quoted 7 lines

Yes, I've seen problems in the past with workloads that use sched_yield heavily.

But bear in mind, the ~2700 sched_yields shown in the schedstats occurred over a 9 minute period. That means that sched_yield is being called at a rate of around 5 per second -- this is not a heavy user of sched_yield.

To put this into a broader perspective, this workload has around 270 tasks, and the context switch rate is around 45,000 per second.

Hi,

Thanks for your detailed report (and schedstats analysis). Sorry I didn't see it until now.

I think you are right that the NUMA domain is probably being too constrictive of task balancing, and that is where the regression is coming from.

For some workloads it is definitely important to have the NUMA domain, because it helps spread load over memory controllers as well as CPUs - so I guess eliminating that domain is not a good long term solution.

I would look at changing parameters of SD_NODE_INIT in include/ asm-powerpc/topology.h so they are closer to SD_CPU_INIT parameters (ie. more aggressive).

Reducing min_ and max_interval, busy_factor, cache_hot_time, will all do this.

I would also take a look at removing SD_WAKE_IDLE from the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.

I agree that sched_yield would be unlikely to be a problem at those rates, and either way it doesn't explain the regression.

Signature · 3 lines
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 
#4 lore raw

Hi Nick,

Quoted 4 lines

I would also take a look at removing SD_WAKE_IDLE from the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.

I was wondering how ppc64 ended up with different parameters in the NODE
definitions (added SD_BALANCE_NEWIDLE and SD_WAKE_IDLE) and it looks
like it was Andrew :)

http://lkml.org/lkml/2004/11/2/205

It looks like balancing was not agressive enough on his workload too. Im a bit uneasy with only ppc64 having the two flags though.

Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.

Anton

#5 lore raw
Quoted 9 lines
Quoted 4 lines

I would also take a look at removing SD_WAKE_IDLE from the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.

I was wondering how ppc64 ended up with different parameters in the NODE
definitions (added SD_BALANCE_NEWIDLE and SD_WAKE_IDLE) and it looks
like it was Andrew :)

Quoted 8 lines

http://lkml.org/lkml/2004/11/2/205

It looks like balancing was not agressive enough on his workload too. Im a bit uneasy with only ppc64 having the two flags though.

Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.

Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow down everything else.

M.

#6 lore raw
Quoted 9 lines · Martin J. Bligh
Quoted 3 lines

Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.

Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow
down everything else.

Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.

On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.

Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?

Thanks,
Nick

Signature · 3 lines
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 
#7 lore raw

Nick Piggin wrote:

[...]

Quoted 3 lines

be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?

To clarify, I'm not suggesting you should go one way or the other for POWER4/5, but if you did have regressions I would be interested at least so I can try helping platforms that do use balance on clone.

Thanks,
Nick

Signature · 3 lines
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 
#8 lore raw
In reply to Nick Piggin
Quoted 13 lines
Quoted 8 lines
Quoted 3 lines

Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.

Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow down everything else.

Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.

Quoted 8 lines

On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.

Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?

Anything fork/exec-y should show it's slower. Most stuff either forks and execs (in case it's silly to do it twice, and much cheaper to do it at exec time), or it's a clone, in which case a different set of rules applies for what you want (and actually, I suspect fork w/o exec is much the same).

Of course the pig is you can't determine at fork whether it'll exec or not, so you optimise for the common case, which is "do exec", unless given a hint otherwise.

For clone, and I suspect fork w/o exec, you have a tightly coupled group of processes that really would like to be close to each other. If you have 1 app on the whole system, you *may* want it spread across the system. If you have nr_apps >= nr_nodes, you probably want them node local. Determining which workload you have is messy, and may change.

Tweak the freak benchmark, not everything else ;-)

M.

#9 lore raw
In reply to Nick Piggin
Quoted 12 lines · Nick Piggin
Quoted 9 lines · Martin J. Bligh
Quoted 3 lines

Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.

Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow
down everything else.

Quoted 7 lines

Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.

On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.

although if the primary workload is short-lived tasks and you don't do balance-on-fork/clone won't you have trouble ever balancing things? (anything that you do move over will probably exit quickly and put you right back where you started)

at the risk of a slowdown from an extra test it almost sounds like what is needed is to get feedback from the last scheduled balance attempt and use that to decide per-fork what to do.

for example say the scheduled balance attempt leaves a per-cpu value that has it's high bit tested every fork/clone (and then rotated left 1 bit) and if it's a 1 do a balance for this new process.

with a reasonable sized item (I would guess the default int size would probably be the most efficiant to process, but even 8 bits may be enough) the scheduled balance attempt can leave quite an extensive range of behavior, from 'always balance' to 'never balance' to 'balance every 5th and 8th fork', etc.

Quoted 4 lines

Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?

even though people will point out that it's a brin-dead workload (that should be converted to a state machine) I would expect that most fork-per-connection servers would show problems if the work per connection is small

David Lang

Signature · 2 lines
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
 -- C.A.R. Hoare
#10 lore raw
Quoted 19 lines · --On Monday, November 07, 2005 18:04:23 -0800 David Lang…
Quoted 17 lines · Nick Piggin
Quoted 10 lines · Martin J. Bligh
Quoted 3 lines

Im also considering adding balance on fork for ppc64, it seems like a lot of people like to run stream like benchmarks and Im getting tired of telling them to lock their threads down to cpus.

Please don't screw up everything else just for stream. It's a silly frigging benchmark. There's very little real-world stuff that really needs balance on fork, as opposed to balance on clone, and it'll slow down everything else.

Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.

Quoted 5 lines
Quoted 3 lines

On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.

although if the primary workload is short-lived tasks and you don't do balance-on-fork/clone won't you have trouble ever balancing things?

(anything that you do move over will probably exit quickly and put you right back where you started)

If you fork without execing a lot, with no hints, and they all exit quickly, then yes. But I don't think that's a common workload ;-)

Quoted 5 lines

at the risk of a slowdown from an extra test it almost sounds like what is needed is to get feedback from the last scheduled balance attempt and use that to decide per-fork what to do.

for example say the scheduled balance attempt leaves a per-cpu value that has it's high bit tested every fork/clone (and then rotated left 1 bit) and if it's a 1 do a balance for this new process.

with a reasonable sized item (I would guess the default int size would probably be the most efficiant to process, but even 8 bits may be enough) the scheduled balance attempt can leave quite an extensive range of behavior, from 'always balance' to 'never balance' to 'balance every 5th and 8th fork', etc.

That might work, yes. But I'd prefer to see a real workload that suffers before worrying about it too much. You have something in mind?

Quoted 6 lines
Quoted 4 lines

Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?

even though people will point out that it's a brin-dead workload (that should be converted to a state machine) I would expect that most fork-per-connection servers would show problems if the work per connection is small

I suspect most of those are either inetd (exec's) or multiple servers that service requests by now. maybe not. Threads might be quicker if it's heavy anyway ;-)

M.

#11 lore raw
In reply to David Lang
Quoted 7 lines · David Lang
Quoted 5 lines · Nick Piggin

Long lived and memory intensive cloned or forked tasks will often [but far from always :(] want to be put on another memory controller from their siblings.

Quoted 7 lines
Quoted 3 lines

On workloads where there are lots of short lived ones (some bloated java programs), the load balancer should normally detect this and cut the balance-on-fork/clone.

although if the primary workload is short-lived tasks and you don't do balance-on-fork/clone won't you have trouble ever balancing things? (anything that you do move over will probably exit quickly and put you right back where you started)

You'll have no trouble if things *need* to be balanced, because that would imply the runqueue length average is significantly above the lengths of other runqueues.

As far as the extra test goes, it's really a miniscule overhead compared with the fork / clone cost itself, and can be really worthwhile if we get it right.

Quoted 9 lines
Quoted 5 lines

Of course there are going to be cases where this fails. I haven't seen significant slowdowns in tests, although I'm sure there would be some at least small regressions. Have you seen any? Do you have any tests in mind that might show a problem?

even though people will point out that it's a brin-dead workload (that should be converted to a state machine) I would expect that most fork-per-connection servers would show problems if the work per connection is small

Well it may be brain-dead, but if people use them (and they do) then I would really be interested to see results.

I did testing with some things like apache and volanomark, however I was not able to make out much difference on my setups. Though obviously that's not to say that there won't be with other software or other workloads / architectures etc.

Signature · 3 lines
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 
#15 lore raw
In reply to David Lang
Quoted 3 lines · David Lang

Brian,
If I am understanding the data you posted, it looks like you are useing
sched_yield extensivly in your database. This is known to have significant problems on SMP machines, and even bigger ones on NUMA machines, in part becouse the process doing the sched_yield may get rescheduled immediatly and not allow other processes to run (to free up whatever resource it's waiting for). This causes the processor to look busy to the scheduler and therefor the scheduler doesn't migrate other processes to the CPU that's spinning on sched_yield. On NUMA machines this is even more noticable as processes now have to migrate through an additional layer of the scheduler.

I have an application designed on Linux where the only processes running are 'init' and those integral to the application. Each communicates using mutual exclusion & semaphores across a shared file/memory backing.

The application was designed to be as close intrinsically as to what Linux does--manage processes. There's only 1 thread per process, and each process has a different executable for its own task.

One day I plan to extend this application across multiple CPUs using either SMP or NUMA. Therefore a lot of the mutual exclusion routines I've coded in use sched_yield().

What should I do instead to alleviate the problem of causing the processor to look busy? In this case I _want_ other processes to be migrated over to the CPU in order to free up the critical section faster.

A simple test using a 2-cpu SMP system resulted in sched_yield() being a lot faster than using futexes, but I don't know for the NUMA case.

Best regards,
-Byron

--

Byron Stanoszek                         Ph: (330) 644-3059
Systems Programmer                      Fax: (330) 644-8110
Commercial Timesharing Inc.             Email: [email protected]
#17 lore raw
In reply to linux-os (Dick Johnson)
Quoted 5 lines · linux-os (Dick Johnson)

Can you change sched_yield() to usleep(1) or usleep(0) and see if that works. I found that in recent kernels sched_yield() just seems to spin (may not actually spin, but seems to with a high CPU usage).

I've told you that it *does* spin and always has. Even with 2.4 kernels. In fact, it is *specified* to spin, anything else would be a bug.

Caveat: it also yields the CPU, but only if there is another runnable task with a higher priority (which is meaningless between SCHED_OTHER tasks, though we try to do something sane there too).

Secondly, Brian actually pinpointed the source of the regression and it is not sched_yield(), nor has sched_yield changed since the regression. So wouldn't this just be a wild goose chase.

Nick

Signature · 3 lines
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 
#12 lore raw
In reply to Nick Piggin
Quoted 5 lines · Nick Piggin

I think you are right that the NUMA domain is probably being too constrictive of task balancing, and that is where the regression is coming from.

Quoted 8 lines

For some workloads it is definitely important to have the NUMA domain, because it helps spread load over memory controllers as well as CPUs - so I guess eliminating that domain is not a good long term solution.

I would look at changing parameters of SD_NODE_INIT in include/ asm-powerpc/topology.h so they are closer to SD_CPU_INIT parameters (ie. more aggressive).

I ran with the following:

topology.h 2005-11-08 13:17:15.000000000 -0600 renamed from topology.h.orig 2005-11-08 13:11:57.000000000 -0600 +4 -4
@@ -43,11 +43,11 @@ static inline int node_to_first_cpu(int
       .span                   = CPU_MASK_NONE,        \
       .parent                 = NULL,                 \
       .groups                 = NULL,                 \
-       .min_interval           = 8,                    \
-       .max_interval           = 32,                   \
-       .busy_factor            = 32,                   \
+       .min_interval           = 1,                    \
+       .max_interval           = 4,                    \
+       .busy_factor            = 64,                   \
       .imbalance_pct          = 125,                  \
-       .cache_hot_time         = (10*1000000),         \
+       .cache_hot_time         = (5*1000000/2),        \
       .cache_nice_tries       = 1,                    \
       .per_cpu_gain           = 100,                  \
       .flags                  = SD_LOAD_BALANCE       \

There was no improvement in performance. The schedstats from this run follow:

2516 sys_sched_yield()
0( 0.00%) found (only) active queue empty on current cpu 0( 0.00%) found (only) expired queue empty on current cpu
46( 1.83%) found both queues empty on current cpu
2470( 98.17%) found neither queue empty on current cpu

22969106 schedule()
694922 goes idle
3( 0.00%) switched active and expired queues 0( 0.00%) used existing active queue

0 active_load_balance()
0 sched_balance_exec()

0.19/1.28 avg runtime/latency over all cpus (ms)

[scheduler domain #0]
1153606 load_balance()

     82580(  7.16%) called while idle
                        488(  0.59%) tried but failed to move any tasks
                      63876( 77.35%) found no busier group
                      18216( 22.06%) succeeded in moving at least one task
                                     (average imbalance:   1.526)
    317610( 27.53%) called while busy
                         15(  0.00%) tried but failed to move any tasks
                     220139( 69.31%) found no busier group
                      97456( 30.68%) succeeded in moving at least one task
                                     (average imbalance:   1.752)
    753416( 65.31%) called when newly idle
                        487(  0.06%) tried but failed to move any tasks
                     624132( 82.84%) found no busier group
                     128797( 17.10%) succeeded in moving at least one task
                                     (average imbalance:   1.531)

         0          sched_balance_exec() tried to push a task

[scheduler domain #1]

    715638          load_balance()
     68533(  9.58%) called while idle
                       3140(  4.58%) tried but failed to move any tasks
                      60357( 88.07%) found no busier group
                       5036(  7.35%) succeeded in moving at least one task
                                     (average imbalance:   1.251)
     22486(  3.14%) called while busy
                         64(  0.28%) tried but failed to move any tasks
                      21352( 94.96%) found no busier group
                       1070(  4.76%) succeeded in moving at least one task
                                     (average imbalance:   1.922)
    624619( 87.28%) called when newly idle
                       5218(  0.84%) tried but failed to move any tasks
                     591970( 94.77%) found no busier group
                      27431(  4.39%) succeeded in moving at least one task
                                     (average imbalance:   1.382)

         0          sched_balance_exec() tried to push a task

[scheduler domain #2]

    685164          load_balance()
     63247(  9.23%) called while idle
                       7280( 11.51%) tried but failed to move any tasks
                      52200( 82.53%) found no busier group
                       3767(  5.96%) succeeded in moving at least one task
                                     (average imbalance:   1.361)
     24729(  3.61%) called while busy
                        418(  1.69%) tried but failed to move any tasks
                      21025( 85.02%) found no busier group
                       3286( 13.29%) succeeded in moving at least one task
                                     (average imbalance:   3.579)
    597188( 87.16%) called when newly idle
                      67577( 11.32%) tried but failed to move any tasks
                     371377( 62.19%) found no busier group
                     158234( 26.50%) succeeded in moving at least one task
                                     (average imbalance:   2.146)

         0          sched_balance_exec() tried to push a task
Quoted 5 lines

I would also take a look at removing SD_WAKE_IDLE from the flags. This flag should make balancing more aggressive, but it can have problems when applied to a NUMA domain due to too much task movement.

Independent from the run above, I ran with the following:

topology.h 2005-11-08 19:34:25.000000000 -0600 renamed from topology.h.orig 2005-11-08 19:32:19.000000000 -0600 +0 -1
@@ -53,7 +53,6 @@ static inline int node_to_first_cpu(int
       .flags                  = SD_LOAD_BALANCE       \
                               | SD_BALANCE_EXEC       \
                               | SD_BALANCE_NEWIDLE    \
-                               | SD_WAKE_IDLE          \
                               | SD_WAKE_BALANCE,      \
       .last_balance           = jiffies,              \
       .balance_interval       = 1,                    \

There was no improvement in performance.

I didn't expect any change in performance this time, because I don't think the SD_WAKE_IDLE flag is effective in the NUMA domain, due to the following code in wake_idle:

       for_each_domain(cpu, sd) {
               if (sd->flags & SD_WAKE_IDLE) {
                       cpus_and(tmp, sd->span, p->cpus_allowed);
                       for_each_cpu_mask(i, tmp) {
                               if (idle_cpu(i))
                                       return i;
                       }
               }
               else
                       break;
       }

If I read that loop correctly it stops at the first domain which doesn't have SD_WAKE_IDLE set, which is the CPU domain (see SD_CPU_INIT), and thus it never gets to the NUMA domain.

Thanks for the suggestions Nick. Andrew raises some good questions that I will address tomorrow.

Cheers,
Brian

#14 lore raw
In reply to a message not in the archive
Quoted 15 lines · Nick Piggin

Just one other thing - A couple of fields aren't actually getting initialised at all, which I didn't pick up on.

This bug looks to have been due to a mismerge between the common asm-powerpc directory and one of my scheduler changes somewhere along the line.

If you get time to try this out, that would be great.

===================================================================

include/asm-powerpc/topology.h static inline int node_to_first_cpu(int · line 60

Quoted 10 lines
include/asm-powerpc/topology.h +4 -0
@@ -51,6 +51,10 @@ static inline int node_to_first_cpu(int 
 	.cache_hot_time		= (10*1000000),		\
 	.cache_nice_tries	= 1,			\
 	.per_cpu_gain		= 100,			\
+	.busy_idx		= 3,			\
+	.idle_id		= 1,			\
+	.newidle_idx		= 2,			\
+	.wake_idx		= 1,			\
 	.flags			= SD_LOAD_BALANCE	\
 				| SD_BALANCE_EXEC	\
 				| SD_BALANCE_NEWIDLE	\

Nick,

That patch eliminates the regression on 2.6.13-rc5. Thanks !! We are currently evaluating it with other workloads.

It also gives a boost on 2.6.14, but unfortunately we are still 1% regressed on 2.6.14. (The regression on 2.6.14 was larger than the regression on 2.6.13-rc5.) We're trying to isolate the 2.6.14 regression now. I'll let you know if we isolate it to a scheduler change.

Cheers,
Brian