Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[Al Boldi]

Con Kolivas wrote:
> On Monday 30 April 2007 18:05, Michael Gerdau wrote:
> > meanwhile I've redone my numbercrunching tests with the following
> > kernels: 2.6.21.1 (mainline)
> >     2.6.21-sd046
> >     2.6.21-cfs-v6
> > running on a dualcore x86_64.
> > [I will run the same test with 2.6.21.1-cfs-v7 over the next days,
> > likely tonight]
:
:
> > However from these figures it seems as if sd does provide for the
> > fairest (as in equal share for all) scheduling among the 3 schedulers
> > tested.
>
> Looks good, thanks. Ingo's been hard at work since then and has v8 out by
> now. SD has not changed so you wouldn't need to do the whole lot of tests
> on SD again unless you don't trust some of the results.

Well, I tried cfs-v8 and it still shows some nice regressions wrt 
mainline/sd.  SD's nice-levels look rather solid, implying fairness.


Thanks!

--
Al

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[William Lee Irwin III]

Con Kolivas wrote:
>> Looks good, thanks. Ingo's been hard at work since then and has v8 out by
>> now. SD has not changed so you wouldn't need to do the whole lot of tests
>> on SD again unless you don't trust some of the results.

On Thu, May 03, 2007 at 02:11:39AM +0300, Al Boldi wrote:
> Well, I tried cfs-v8 and it still shows some nice regressions wrt 
> mainline/sd.  SD's nice-levels look rather solid, implying fairness.

That's odd. The ->load_weight changes should've improved that quite
a bit. There may be something slightly off in how lag is computed,
or maybe the O(n) lag issue Ying Tang spotted is biting you.

Also, I should say that the nice number affairs don't imply fairness
per se. The way that works is that when tasks have "weights" (like
nice levels in UNIX) the definition of fairness changes so that each
task gets shares of CPU bandwidth proportional to its weight instead
of one share for one task.

It takes a bit closer inspection than feel tests to see if weighted
fairness is properly implemented. One thing to try is running a number
of identical CPU hogs at the same time at different nice levels for a
fixed period of time (e.g. 1 or 2 minutes) so they're in competition
with each other and seeing what percent of the CPU each gets. From
there you can figure out how many shares each is getting for its nice
level. Trying different mixtures of nice levels and different numbers
of tasks should give consistent results for the shares of CPU bandwidth
the CPU hogs get for being at a particular nice level. A scheduler gets
"bonus points" (i.e. is considered better at prioritizing) for the user
being able to specify how the weightings come out. The finer-grained
the control, the more bonus points.

Maybe con might want to take a stab at having users be able to specify
the weights for each nice level individually.

CFS actually has a second set of weights for tasks, namely the
timeslice for a given task. At the moment, they're all equal. It should
be the case that the shorter the timeslice a given task has, the less
latency it gets. So there is a fair amount of room for it to manuever
with respect to feel tests. It really needs to be done numerically to
get results we can be sure mean something.

The way this goes is task t_i gets a percent of the CPU p_i when the
tasks t_1, t_2, ..., t_n are all competing, and task t_i has nice level
n_i. The share corresponding to nice level n_i is then

          p_i
  w_i = -------
        sum p_j

One thing to check for is that if two tasks have the same nice level
that their weights come out about equal. So for t_i and t_j, if n_i
= n_j then you check that at least approximately, w_i = w_j, or even
p_i = p_j, since we're not starting and stopping tasks in the midst of
the test. Also, you can't simplify sum p_j to 1, since the set of tasks
may not be the only things running.

The other thing to do is try a different number of tasks with a
different mix of nice levels. The weight w_i for a given nice
level n_i should be the same even in a different mix of tasks
and nice levels if the nice levels are the same.

If this sounds too far out, there's nothing to worry about. You can
just run the different numbers of tasks with different mixes of nice
levels and post the %cpu numbers. Or if that's still a bit far out
for you, a test that does all this is eventually going to get written.


-- wli

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[Al Boldi]

William Lee Irwin III wrote:
> Con Kolivas wrote:
> >> Looks good, thanks. Ingo's been hard at work since then and has v8 out
> >> by now. SD has not changed so you wouldn't need to do the whole lot of
> >> tests on SD again unless you don't trust some of the results.
>
> On Thu, May 03, 2007 at 02:11:39AM +0300, Al Boldi wrote:
> > Well, I tried cfs-v8 and it still shows some nice regressions wrt
> > mainline/sd.  SD's nice-levels look rather solid, implying fairness.
>
> That's odd. The ->load_weight changes should've improved that quite
> a bit. There may be something slightly off in how lag is computed,
> or maybe the O(n) lag issue Ying Tang spotted is biting you.

Is it not biting you too?

> Also, I should say that the nice number affairs don't imply fairness
> per se. The way that works is that when tasks have "weights" (like
> nice levels in UNIX) the definition of fairness changes so that each
> task gets shares of CPU bandwidth proportional to its weight instead
> of one share for one task.

Ok, but you can easily expose scheduler unfairness by using nice levels as 
relative magnifiers; provided nice levels are implemented correctly.

> It takes a bit closer inspection than feel tests to see if weighted
> fairness is properly implemented. One thing to try is running a number
> of identical CPU hogs at the same time at different nice levels for a
> fixed period of time (e.g. 1 or 2 minutes) so they're in competition
> with each other and seeing what percent of the CPU each gets. From
> there you can figure out how many shares each is getting for its nice
> level. Trying different mixtures of nice levels and different numbers
> of tasks should give consistent results for the shares of CPU bandwidth
> the CPU hogs get for being at a particular nice level. A scheduler gets
> "bonus points" (i.e. is considered better at prioritizing) for the user
> being able to specify how the weightings come out. The finer-grained
> the control, the more bonus points.
>
> Maybe con might want to take a stab at having users be able to specify
> the weights for each nice level individually.
>
> CFS actually has a second set of weights for tasks, namely the
> timeslice for a given task. At the moment, they're all equal. It should
> be the case that the shorter the timeslice a given task has, the less
> latency it gets. So there is a fair amount of room for it to manuever
> with respect to feel tests. It really needs to be done numerically to
> get results we can be sure mean something.
>
> The way this goes is task t_i gets a percent of the CPU p_i when the
> tasks t_1, t_2, ..., t_n are all competing, and task t_i has nice level
> n_i. The share corresponding to nice level n_i is then
>
>           p_i
>   w_i = -------
>         sum p_j
>
> One thing to check for is that if two tasks have the same nice level
> that their weights come out about equal. So for t_i and t_j, if n_i
> = n_j then you check that at least approximately, w_i = w_j, or even
> p_i = p_j, since we're not starting and stopping tasks in the midst of
> the test. Also, you can't simplify sum p_j to 1, since the set of tasks
> may not be the only things running.
>
> The other thing to do is try a different number of tasks with a
> different mix of nice levels. The weight w_i for a given nice
> level n_i should be the same even in a different mix of tasks
> and nice levels if the nice levels are the same.
>
> If this sounds too far out, there's nothing to worry about. You can
> just run the different numbers of tasks with different mixes of nice
> levels and post the %cpu numbers. Or if that's still a bit far out
> for you, a test that does all this is eventually going to get written.

chew.c does exactly that, just make sure sched_granularity_ms >= 5,000,000.


Thanks!

--
Al

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[William Lee Irwin III]

William Lee Irwin III wrote:
>> That's odd. The ->load_weight changes should've improved that quite
>> a bit. There may be something slightly off in how lag is computed,
>> or maybe the O(n) lag issue Ying Tang spotted is biting you.

On Thu, May 03, 2007 at 06:51:43AM +0300, Al Boldi wrote:
> Is it not biting you too?

I'm a kernel programmer. I'm not an objective tester.

It also happens to be the case that I personally have never encountered
a performance problem with any of the schedulers, mainline included, on
any system I use interactively. So my "user experience" is not valuable.


William Lee Irwin III wrote:
>> Also, I should say that the nice number affairs don't imply fairness
>> per se. The way that works is that when tasks have "weights" (like
>> nice levels in UNIX) the definition of fairness changes so that each
>> task gets shares of CPU bandwidth proportional to its weight instead
>> of one share for one task.

On Thu, May 03, 2007 at 06:51:43AM +0300, Al Boldi wrote:
> Ok, but you can easily expose scheduler unfairness by using nice levels as 
> relative magnifiers; provided nice levels are implemented correctly.

This doesn't really fit in with anything I'm aware of.


William Lee Irwin III wrote:
>> The other thing to do is try a different number of tasks with a
>> different mix of nice levels. The weight w_i for a given nice
>> level n_i should be the same even in a different mix of tasks
>> and nice levels if the nice levels are the same.
>> If this sounds too far out, there's nothing to worry about. You can
>> just run the different numbers of tasks with different mixes of nice
>> levels and post the %cpu numbers. Or if that's still a bit far out
>> for you, a test that does all this is eventually going to get written.

On Thu, May 03, 2007 at 06:51:43AM +0300, Al Boldi wrote:
> chew.c does exactly that, just make sure sched_granularity_ms >= 5,000,000.

Please post the source of chew.c


-- wli

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[Al Boldi]

[-- Attachment #1: Type: text/plain, Size: 2177 bytes --]

William Lee Irwin III wrote:
> William Lee Irwin III wrote:
> >> That's odd. The ->load_weight changes should've improved that quite
> >> a bit. There may be something slightly off in how lag is computed,
> >> or maybe the O(n) lag issue Ying Tang spotted is biting you.
>
> On Thu, May 03, 2007 at 06:51:43AM +0300, Al Boldi wrote:
> > Is it not biting you too?
>
> I'm a kernel programmer. I'm not an objective tester.
>
> It also happens to be the case that I personally have never encountered
> a performance problem with any of the schedulers, mainline included, on
> any system I use interactively. So my "user experience" is not valuable.
>
> William Lee Irwin III wrote:
> >> Also, I should say that the nice number affairs don't imply fairness
> >> per se. The way that works is that when tasks have "weights" (like
> >> nice levels in UNIX) the definition of fairness changes so that each
> >> task gets shares of CPU bandwidth proportional to its weight instead
> >> of one share for one task.
>
> On Thu, May 03, 2007 at 06:51:43AM +0300, Al Boldi wrote:
> > Ok, but you can easily expose scheduler unfairness by using nice levels
> > as relative magnifiers; provided nice levels are implemented correctly.
>
> This doesn't really fit in with anything I'm aware of.

You are not the first person that doesn't understand what I'm talking about.  
Don't worry about it.

> William Lee Irwin III wrote:
> >> The other thing to do is try a different number of tasks with a
> >> different mix of nice levels. The weight w_i for a given nice
> >> level n_i should be the same even in a different mix of tasks
> >> and nice levels if the nice levels are the same.
> >> If this sounds too far out, there's nothing to worry about. You can
> >> just run the different numbers of tasks with different mixes of nice
> >> levels and post the %cpu numbers. Or if that's still a bit far out
> >> for you, a test that does all this is eventually going to get written.
>
> On Thu, May 03, 2007 at 06:51:43AM +0300, Al Boldi wrote:
> > chew.c does exactly that, just make sure sched_granularity_ms >=
> > 5,000,000.
>
> Please post the source of chew.c

Attached.


Thanks!

--
Al



[-- Attachment #2: chew.c --]
[-- Type: text/x-csrc, Size: 1136 bytes --]

/*
 * original idea by Chris Friesen.  Thanks.
 */

#include <stdio.h>
#include <sys/time.h>
#include <sys/resource.h>

#define THRESHOLD_USEC 2000

unsigned long long stamp()
{
        struct timeval tv;
        gettimeofday(&tv, 0);
        return (unsigned long long) tv.tv_usec + ((unsigned long long) tv.tv_sec)*1000000;
}


int main()
{
        unsigned long long thresh_ticks = THRESHOLD_USEC;
        unsigned long long cur, last, start, act, delta;
        struct timespec ts;

        sched_rr_get_interval(0, &ts);
        printf("pid %d, prio %3d, interval of %d nsec\n", getpid(), getpriority(PRIO_PROCESS, 0), ts.tv_nsec);

        start = last = stamp();
        while(1) {
                cur = stamp();
                delta = cur-last;
                if (delta > thresh_ticks) {
			act = last - start;
                        printf("pid %d, prio %3d, out for %4llu ms, ran for %4llu ms, load %3llu%\n"
			, getpid(), getpriority(PRIO_PROCESS, 0), delta/1000, act/1000,(act*100)/(cur-start));
                        start = cur = stamp();
                }
                last = cur;
        }

        return 0;
}

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[William Lee Irwin III]

> William Lee Irwin III wrote:
On Thu, May 03, 2007 at 09:42:51AM +0300, Al Boldi wrote:
>         sched_rr_get_interval(0, &ts);
>         printf("pid %d, prio %3d, interval of %d nsec\n", getpid(), getpriority(PRIO_PROCESS, 0), ts.tv_nsec);

Oh dear. What are you trying to figure out from the task's timeslice?
That's not even meaningful in cfs.


On Thu, May 03, 2007 at 09:42:51AM +0300, Al Boldi wrote:
>         start = last = stamp();
>         while(1) {
>                 cur = stamp();
>                 delta = cur-last;
>                 if (delta > thresh_ticks) {
> 			act = last - start;
>                         printf("pid %d, prio %3d, out for %4llu ms, ran for %4llu ms, load %3llu%\n"
> 			, getpid(), getpriority(PRIO_PROCESS, 0), delta/1000, act/1000,(act*100)/(cur-start));
>                         start = cur = stamp();
>                 }
>                 last = cur;
>         }
> 
>         return 0;
> }

This is looking for scheduling latencies, which are necessarily O(tasks).
This is not the way to do it.


-- wli

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[Al Boldi]

William Lee Irwin III wrote:
> On Thu, May 03, 2007 at 09:42:51AM +0300, Al Boldi wrote:
> >         sched_rr_get_interval(0, &ts);
> >         printf("pid %d, prio %3d, interval of %d nsec\n", getpid(),
> > getpriority(PRIO_PROCESS, 0), ts.tv_nsec);
>
> Oh dear. What are you trying to figure out from the task's timeslice?

chew.c is general purpose.  It's not specific to cfs.

> That's not even meaningful in cfs.
>
> On Thu, May 03, 2007 at 09:42:51AM +0300, Al Boldi wrote:
> >         start = last = stamp();
> >         while(1) {
> >                 cur = stamp();
> >                 delta = cur-last;
> >                 if (delta > thresh_ticks) {
> > 			act = last - start;
> >                         printf("pid %d, prio %3d, out for %4llu ms, ran
> > for %4llu ms, load %3llu%\n" , getpid(), getpriority(PRIO_PROCESS, 0),
> > delta/1000, act/1000,(act*100)/(cur-start)); start = cur = stamp();
> >                 }
> >                 last = cur;
> >         }
> >
> >         return 0;
> > }
>
> This is looking for scheduling latencies, which are necessarily O(tasks).

This exposes the actual proc latency/waittime and runtime and cpu load 
irrespective of being O(tasks) or not.

> This is not the way to do it.

You'll need to boot into /bin/sh and run two or more chew.c's to see any 
reasonable results.

Then tell me whether this is the way to do it or not.


Thanks!

--
Al

[REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[Michael Gerdau]

[-- Attachment #1: Type: text/plain, Size: 3451 bytes --]

i list,

meanwhile I've redone my numbercrunching tests with the following kernels:
    2.6.21.1 (mainline)
    2.6.21-sd046
    2.6.21-cfs-v6
running on a dualcore x86_64.
[I will run the same test with 2.6.21.1-cfs-v7 over the next days,
likely tonight]

The tests consist of 3 tasks (named LTMM, LTMB and LTBM). The only
I/O they do is during init and for logging the results, the rest
is just floating point math.

There are 3 scenarios:
    j1 - all 3 tasks run sequentially
	 /proc/sys/kernel/sched_granularity_ns=4000000
	 /proc/sys/kernel/rr_interval=16
    j3 - all 3 tasks run in parallel
	 /proc/sys/kernel/sched_granularity_ns=4000000
	 /proc/sys/kernel/rr_interval=16
    j3big - all 3 tasks run in parallel with timeslice extended
            by 2 magnitudes (not run for mainline)
            /proc/sys/kernel/sched_granularity_ns=400000000
            /proc/sys/kernel/rr_interval=400

All 3 tasks are run while the system does nothing else except for
the "normal" (KDE) daemons. The system had not been used for
interactive work during the tests.

I'm giving user time as provided by the "time" cmd followed by wallclock time
(all values in seconds).

                LTMM
                j1              j3              j3big
2.6.21-cfs-v6    5655.07/ 5682   5437.84/ 5531   5434.04/ 8072
2.6.21-sd-046    5556.44/ 5583   5446.86/ 8037   5407.50/ 8274
2.6.21.1         5417.62/ 5439   5422.37/ 7132   na     /na

                LTMB
                j1              j3              j3big
2.6.21-cfs-v6    7729.81/ 7755   7470.10/10244   7449.16/10186
2.6.21-sd-046    7611.00/ 7626   7573.16/10109   7458.10/10316
2.6.21.1         7438.31/ 7461   7620.72/11087   na     /na

                LTBM
                j1              j3              j3big
2.6.21-cfs-v6    7720.70/ 7746   7567.09/10362   7464.17/10335
2.6.21-sd-046    7431.06/ 7452   7539.83/10600   7474.20/10222
2.6.21.1         7452.80/ 7481   7484.19/ 9570   na     /na

                LTMM+LTMB+LTBM
                j1              j3              j3big
2.6.21-cfs-v6	21105.58/21183  20475.03/26137  20347.37/28593
2.6.21-sd-046	20598.50/20661  20559.85/28746  20339.80/28812
2.6.21.1	20308.73/20381  20527.28/27789  na      /na
	

User time apparently is subject to some variance. I'm particularly surprised
by the wallclock time of scenario j1 and j3 for case LTMM with 2.6.21-cfs-v6.
I'm not sure what to make of this, i.e. whether I had happening something
else on my machine during j1 of LTMM -- that's always been the first test
I ran and it might be that there were still some other jobs running after
the initial boot.

Assuming scenario j1 does constitute the "true" time each task requires and
also assuming each scheduler makes maximum use of the available CPUs (the
tests involve very little I/O) one could compute the expected wallclock time.
However since I suspect the j1 figures of LTMM to be somewhat "dirty" I'll
refrain from it.

However from these figures it seems as if sd does provide for the fairest
(as in equal share for all) scheduling among the 3 schedulers tested.

Best,
Michael
-- 
 Technosis GmbH, Geschäftsführer: Michael Gerdau, Tobias Dittmar
 Sitz Hamburg; HRB 89145 Amtsgericht Hamburg
 Vote against SPAM - see http://www.politik-digital.de/spam/
 Michael Gerdau       email: mgd@technosis.de
 GPG-keys available on request or at public keyserver

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [ck] [REPORT] 2.6.21.1 vs 2.6.21-sd046 vs 2.6.21-cfs-v6

[Con Kolivas]

On Monday 30 April 2007 18:05, Michael Gerdau wrote:
> i list,
>
> meanwhile I've redone my numbercrunching tests with the following kernels:
>     2.6.21.1 (mainline)
>     2.6.21-sd046
>     2.6.21-cfs-v6
> running on a dualcore x86_64.
> [I will run the same test with 2.6.21.1-cfs-v7 over the next days,
> likely tonight]

Thanks for testing.

> The tests consist of 3 tasks (named LTMM, LTMB and LTBM). The only
> I/O they do is during init and for logging the results, the rest
> is just floating point math.
>
> There are 3 scenarios:
>     j1 - all 3 tasks run sequentially
> 	 /proc/sys/kernel/sched_granularity_ns=4000000
> 	 /proc/sys/kernel/rr_interval=16
>     j3 - all 3 tasks run in parallel
> 	 /proc/sys/kernel/sched_granularity_ns=4000000
> 	 /proc/sys/kernel/rr_interval=16
>     j3big - all 3 tasks run in parallel with timeslice extended
>             by 2 magnitudes (not run for mainline)
>             /proc/sys/kernel/sched_granularity_ns=400000000
>             /proc/sys/kernel/rr_interval=400
>
> All 3 tasks are run while the system does nothing else except for
> the "normal" (KDE) daemons. The system had not been used for
> interactive work during the tests.
>
> I'm giving user time as provided by the "time" cmd followed by wallclock
> time (all values in seconds).
>
>                 LTMM
>                 j1              j3              j3big
> 2.6.21-cfs-v6    5655.07/ 5682   5437.84/ 5531   5434.04/ 8072
> 2.6.21-sd-046    5556.44/ 5583   5446.86/ 8037   5407.50/ 8274
> 2.6.21.1         5417.62/ 5439   5422.37/ 7132   na     /na
>
>                 LTMB
>                 j1              j3              j3big
> 2.6.21-cfs-v6    7729.81/ 7755   7470.10/10244   7449.16/10186
> 2.6.21-sd-046    7611.00/ 7626   7573.16/10109   7458.10/10316
> 2.6.21.1         7438.31/ 7461   7620.72/11087   na     /na
>
>                 LTBM
>                 j1              j3              j3big
> 2.6.21-cfs-v6    7720.70/ 7746   7567.09/10362   7464.17/10335
> 2.6.21-sd-046    7431.06/ 7452   7539.83/10600   7474.20/10222
> 2.6.21.1         7452.80/ 7481   7484.19/ 9570   na     /na
>
>                 LTMM+LTMB+LTBM
>                 j1              j3              j3big
> 2.6.21-cfs-v6	21105.58/21183  20475.03/26137  20347.37/28593
> 2.6.21-sd-046	20598.50/20661  20559.85/28746  20339.80/28812
> 2.6.21.1	20308.73/20381  20527.28/27789  na      /na
>
>
> User time apparently is subject to some variance. I'm particularly
> surprised by the wallclock time of scenario j1 and j3 for case LTMM with
> 2.6.21-cfs-v6. I'm not sure what to make of this, i.e. whether I had
> happening something else on my machine during j1 of LTMM -- that's always
> been the first test I ran and it might be that there were still some other
> jobs running after the initial boot.
>
> Assuming scenario j1 does constitute the "true" time each task requires and
> also assuming each scheduler makes maximum use of the available CPUs (the
> tests involve very little I/O) one could compute the expected wallclock
> time. However since I suspect the j1 figures of LTMM to be somewhat "dirty"
> I'll refrain from it.
>
> However from these figures it seems as if sd does provide for the fairest
> (as in equal share for all) scheduling among the 3 schedulers tested.

Looks good, thanks. Ingo's been hard at work since then and has v8 out by now. 
SD has not changed so you wouldn't need to do the whole lot of tests on SD 
again unless you don't trust some of the results.

> Best,
> Michael

-- 
-ck