On 2020/12/15 0:48, Peter Zijlstra wrote:
> We compute the average cost of the total scan, but then use it as a
> per-cpu scan cost when computing the scan proportion. Fix this by
> properly computing a per-cpu scan cost.
>
> This also fixes a bug where we would terminate early (!--nr, case) and
> not account that cost at all.
I'm a bit worried this may introduce a regression under heavy load.
The overhead of adding another cpu_clock() and calculation becomes
significant when sis_scan is throttled by nr.
I'm not sure if it's a good idea to not account the scan cost at all
when sis_scan is throttled, that is, remove the first cpu_clock() as
well. The avg scan cost remains the value when the system is not very
busy, and when the load comes down and span avg idle > span avg cost,
we account the cost again. This should make select_idle_cpu() a bit
faster when the load is very high.
Thanks,
-Aubrey
>
> Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
> ---
> kernel/sched/fair.c | 13 +++++++++----
> 1 file changed, 9 insertions(+), 4 deletions(-)
>
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6144,10 +6144,10 @@ static inline int select_idle_smt(struct
> static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int target)
> {
> struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_idle_mask);
> + int cpu, loops = 1, nr = INT_MAX;
> + int this = smp_processor_id();
> struct sched_domain *this_sd;
> u64 time;
> - int this = smp_processor_id();
> - int cpu, nr = INT_MAX;
>
> this_sd = rcu_dereference(*this_cpu_ptr(&sd_llc));
> if (!this_sd)
> @@ -6175,14 +6175,19 @@ static int select_idle_cpu(struct task_s
> }
>
> for_each_cpu_wrap(cpu, cpus, target) {
> - if (!--nr)
> - return -1;
> if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
> break;
> +
> + if (loops >= nr) {
> + cpu = -1;
> + break;
> + }
> + loops++;
> }
>
> if (sched_feat(SIS_PROP)) {
> time = cpu_clock(this) - time;
> + time = div_u64(time, loops);
> update_avg(&this_sd->avg_scan_cost, time);
> }
>
>
>
On Tue, Dec 15, 2020 at 11:36:35AM +0800, Li, Aubrey wrote:
> On 2020/12/15 0:48, Peter Zijlstra wrote:
> > We compute the average cost of the total scan, but then use it as a
> > per-cpu scan cost when computing the scan proportion. Fix this by
> > properly computing a per-cpu scan cost.
> >
> > This also fixes a bug where we would terminate early (!--nr, case) and
> > not account that cost at all.
>
> I'm a bit worried this may introduce a regression under heavy load.
> The overhead of adding another cpu_clock() and calculation becomes
> significant when sis_scan is throttled by nr.
The thing is, the code as it exists today makes no sense what so ever.
It's plain broken batshit.
We calculate the total scanning time (irrespective of how many CPUs we
touched), and then use that calculate the number of cpus to scan. That's
just daft.
After this patch we calculate the avg cost of scanning 1 cpu and use
that to calculate how many cpus to scan. Which is coherent and sane.
Maybe it can be improved, but that's a completely different thing.
On Tue, Dec 15, 2020 at 08:59:11AM +0100, Peter Zijlstra wrote:
> On Tue, Dec 15, 2020 at 11:36:35AM +0800, Li, Aubrey wrote:
> > On 2020/12/15 0:48, Peter Zijlstra wrote:
> > > We compute the average cost of the total scan, but then use it as a
> > > per-cpu scan cost when computing the scan proportion. Fix this by
> > > properly computing a per-cpu scan cost.
> > >
> > > This also fixes a bug where we would terminate early (!--nr, case) and
> > > not account that cost at all.
> >
> > I'm a bit worried this may introduce a regression under heavy load.
> > The overhead of adding another cpu_clock() and calculation becomes
> > significant when sis_scan is throttled by nr.
>
> The thing is, the code as it exists today makes no sense what so ever.
Which makes it very hard to reason about or change in a "safe" manner as
all sorts of counter-intuitive effects occur.
The series is queued and running and takes 1-2 days. I haven't reviewed
the patches properly (holiday) but it'll be interesting to get some
provisional data at least.
--
Mel Gorman
SUSE Labs
On 2020/12/15 15:59, Peter Zijlstra wrote:
> On Tue, Dec 15, 2020 at 11:36:35AM +0800, Li, Aubrey wrote:
>> On 2020/12/15 0:48, Peter Zijlstra wrote:
>>> We compute the average cost of the total scan, but then use it as a
>>> per-cpu scan cost when computing the scan proportion. Fix this by
>>> properly computing a per-cpu scan cost.
>>>
>>> This also fixes a bug where we would terminate early (!--nr, case) and
>>> not account that cost at all.
>>
>> I'm a bit worried this may introduce a regression under heavy load.
>> The overhead of adding another cpu_clock() and calculation becomes
>> significant when sis_scan is throttled by nr.
>
> The thing is, the code as it exists today makes no sense what so ever.
> It's plain broken batshit.
>
> We calculate the total scanning time (irrespective of how many CPUs we
> touched), and then use that calculate the number of cpus to scan. That's
> just daft.
>
> After this patch we calculate the avg cost of scanning 1 cpu and use
> that to calculate how many cpus to scan. Which is coherent and sane.
I see and all of these make sense to me.
>
> Maybe it can be improved, but that's a completely different thing.
>
OK, I'll go through the workloads in hand and paste the data here.
Thanks,
-Aubrey
On Tue, Dec 15, 2020 at 08:59:11AM +0100, Peter Zijlstra wrote:
> On Tue, Dec 15, 2020 at 11:36:35AM +0800, Li, Aubrey wrote:
> > On 2020/12/15 0:48, Peter Zijlstra wrote:
> > > We compute the average cost of the total scan, but then use it as a
> > > per-cpu scan cost when computing the scan proportion. Fix this by
> > > properly computing a per-cpu scan cost.
> > >
> > > This also fixes a bug where we would terminate early (!--nr, case) and
> > > not account that cost at all.
> >
> > I'm a bit worried this may introduce a regression under heavy load.
> > The overhead of adding another cpu_clock() and calculation becomes
> > significant when sis_scan is throttled by nr.
>
> The thing is, the code as it exists today makes no sense what so ever.
> It's plain broken batshit.
>
> We calculate the total scanning time (irrespective of how many CPUs we
> touched), and then use that calculate the number of cpus to scan. That's
> just daft.
>
> After this patch we calculate the avg cost of scanning 1 cpu and use
> that to calculate how many cpus to scan. Which is coherent and sane.
>
> Maybe it can be improved, but that's a completely different thing.
In general I agree with everything you said so lets talk about the last
sentence.
1. avg_scan_cost is now based on the average scan cost of a rq but
avg_idle is still scaled to the domain size. This is a bit problematic
because it's comparing scan cost of a single rq with the estimated
average idle time of a domain. As a result, the scan depth can be much
larger than it was before the patch and led to some regressions.
2. Accounting for the scan cost of success makes sense but there is a
big difference between a scan that finds an idle CPU and one that fails.
For failures, the scan cost is wasted CPU time where as a success
means that an uncontested CPU is used. This can cause a search to be
truncated earlier than it should be when the domain is lightly loaded.
The patch below attempts to deal with both of those points. The
remaining difficulty is the "fuzz" factor which is necessary to bring
large avg_idle values into a reasonable range for comparing against
avg_scan_cost. The max avg_idle value can be anything but generally the
ceiling is 2*sysctl_sched_migration_cost. I didn't quickly spot a good way
of mapping avg_idle to a range between 0 and sd->span_weight. The obvious
one was (weight*avg_idle/(2*sched_migration_cost)) but it did not work very
well as avg_scan_cost accounts for the full cost of accessing a remote rq.
However, this could be revisited later after this series is sorted out.
Anyway, for the enumerated concerns, how about this on top for your
first patch? It seemed to work well for a few workloads on 3 machines
at least and I'd like to nail this down before considering the remaining
patches. The first run indicated that the first patch offset some of the
benefits of the other patches.
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 65a2f208ada8..1e04a250e8ee 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6156,7 +6156,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
if (sched_feat(SIS_PROP)) {
- u64 avg_cost, avg_idle, span_avg;
+ u64 avg_cost, avg_idle;
/*
* Due to large variance we need a large fuzz factor;
@@ -6164,25 +6164,25 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
*/
avg_idle = this_rq()->avg_idle / 512;
avg_cost = this_sd->avg_scan_cost + 1;
-
- span_avg = sd->span_weight * avg_idle;
- if (span_avg > 4*avg_cost)
- nr = div_u64(span_avg, avg_cost);
- else
+ nr = div_u64(avg_idle, avg_cost);
+ if (nr < 4)
nr = 4;
time = cpu_clock(this);
}
for_each_cpu_wrap(cpu, cpus, target) {
- if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
+ if (available_idle_cpu(cpu) || sched_idle_cpu(cpu)) {
+ /* Adjust cost of a successful scan */
+ loops <<= 2;
+
break;
+ }
- if (loops >= nr) {
+ if (++loops >= nr) {
cpu = -1;
break;
}
- loops++;
}
if (sched_feat(SIS_PROP)) {
--
Mel Gorman
SUSE Labs
On 01/08/21 10:27, Mel Gorman wrote:
> for_each_cpu_wrap(cpu, cpus, target) {
> - if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
> + if (available_idle_cpu(cpu) || sched_idle_cpu(cpu)) {
> + /* Adjust cost of a successful scan */
> + loops <<= 2;
> +
> break;
> + }
>
> - if (loops >= nr) {
> + if (++loops >= nr) {
> cpu = -1;
> break;
> }
> - loops++;
Random (out of the blue) comment.
Now this will increment loops before the comparison/break. ie: we're
effectively doing one iteration less IIRC. Should loops be initialized to
0 instead of 1?
Thanks
--
Qais Yousef
On Fri, 8 Jan 2021 at 11:27, Mel Gorman <[email protected]> wrote:
>
> On Tue, Dec 15, 2020 at 08:59:11AM +0100, Peter Zijlstra wrote:
> > On Tue, Dec 15, 2020 at 11:36:35AM +0800, Li, Aubrey wrote:
> > > On 2020/12/15 0:48, Peter Zijlstra wrote:
> > > > We compute the average cost of the total scan, but then use it as a
> > > > per-cpu scan cost when computing the scan proportion. Fix this by
> > > > properly computing a per-cpu scan cost.
> > > >
> > > > This also fixes a bug where we would terminate early (!--nr, case) and
> > > > not account that cost at all.
> > >
> > > I'm a bit worried this may introduce a regression under heavy load.
> > > The overhead of adding another cpu_clock() and calculation becomes
> > > significant when sis_scan is throttled by nr.
> >
> > The thing is, the code as it exists today makes no sense what so ever.
> > It's plain broken batshit.
> >
> > We calculate the total scanning time (irrespective of how many CPUs we
> > touched), and then use that calculate the number of cpus to scan. That's
> > just daft.
> >
> > After this patch we calculate the avg cost of scanning 1 cpu and use
> > that to calculate how many cpus to scan. Which is coherent and sane.
> >
> > Maybe it can be improved, but that's a completely different thing.
>
> In general I agree with everything you said so lets talk about the last
> sentence.
>
> 1. avg_scan_cost is now based on the average scan cost of a rq but
> avg_idle is still scaled to the domain size. This is a bit problematic
> because it's comparing scan cost of a single rq with the estimated
> average idle time of a domain. As a result, the scan depth can be much
> larger than it was before the patch and led to some regressions.
Point 1 makes sense to me too
>
> 2. Accounting for the scan cost of success makes sense but there is a
> big difference between a scan that finds an idle CPU and one that fails.
> For failures, the scan cost is wasted CPU time where as a success
> means that an uncontested CPU is used. This can cause a search to be
> truncated earlier than it should be when the domain is lightly loaded.
But I'm not sure to catch your problem with point 2.
track the average cost to scan one rq so looping all rqs are only few
should not impact (much) the avg_scan_cost
Trying to bias the avg_scan_cost with: loops <<= 2;
will just make avg_scan_cost lost any kind of meaning because it
doesn't reflect the avg cost of scanning a rq anymore
>
> The patch below attempts to deal with both of those points. The
> remaining difficulty is the "fuzz" factor which is necessary to bring
> large avg_idle values into a reasonable range for comparing against
> avg_scan_cost. The max avg_idle value can be anything but generally the
> ceiling is 2*sysctl_sched_migration_cost. I didn't quickly spot a good way
> of mapping avg_idle to a range between 0 and sd->span_weight. The obvious
> one was (weight*avg_idle/(2*sched_migration_cost)) but it did not work very
> well as avg_scan_cost accounts for the full cost of accessing a remote rq.
> However, this could be revisited later after this series is sorted out.
>
> Anyway, for the enumerated concerns, how about this on top for your
> first patch? It seemed to work well for a few workloads on 3 machines
> at least and I'd like to nail this down before considering the remaining
> patches. The first run indicated that the first patch offset some of the
> benefits of the other patches.
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 65a2f208ada8..1e04a250e8ee 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6156,7 +6156,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
> cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
>
> if (sched_feat(SIS_PROP)) {
> - u64 avg_cost, avg_idle, span_avg;
> + u64 avg_cost, avg_idle;
>
> /*
> * Due to large variance we need a large fuzz factor;
> @@ -6164,25 +6164,25 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
> */
> avg_idle = this_rq()->avg_idle / 512;
> avg_cost = this_sd->avg_scan_cost + 1;
> -
> - span_avg = sd->span_weight * avg_idle;
> - if (span_avg > 4*avg_cost)
> - nr = div_u64(span_avg, avg_cost);
> - else
> + nr = div_u64(avg_idle, avg_cost);
> + if (nr < 4)
> nr = 4;
>
> time = cpu_clock(this);
> }
>
> for_each_cpu_wrap(cpu, cpus, target) {
> - if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
> + if (available_idle_cpu(cpu) || sched_idle_cpu(cpu)) {
> + /* Adjust cost of a successful scan */
> + loops <<= 2;
> +
> break;
> + }
>
> - if (loops >= nr) {
> + if (++loops >= nr) {
> cpu = -1;
> break;
> }
> - loops++;
> }
>
> if (sched_feat(SIS_PROP)) {
>
> --
> Mel Gorman
> SUSE Labs
On Fri, Jan 08, 2021 at 01:01:10PM +0000, Qais Yousef wrote:
> On 01/08/21 10:27, Mel Gorman wrote:
> > for_each_cpu_wrap(cpu, cpus, target) {
> > - if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
> > + if (available_idle_cpu(cpu) || sched_idle_cpu(cpu)) {
> > + /* Adjust cost of a successful scan */
> > + loops <<= 2;
> > +
> > break;
> > + }
> >
> > - if (loops >= nr) {
> > + if (++loops >= nr) {
> > cpu = -1;
> > break;
> > }
> > - loops++;
>
> Random (out of the blue) comment.
>
> Now this will increment loops before the comparison/break. ie: we're
> effectively doing one iteration less IIRC. Should loops be initialized to
> 0 instead of 1?
>
Yep, although in practice it'll make little difference except after a
rapid phase change when avg_idle still appears high on a per-rq basis
yet the domain is fully busy with no idle CPUs.
--
Mel Gorman
SUSE Labs
On Fri, Jan 08, 2021 at 02:41:19PM +0100, Vincent Guittot wrote:
> > 1. avg_scan_cost is now based on the average scan cost of a rq but
> > avg_idle is still scaled to the domain size. This is a bit problematic
> > because it's comparing scan cost of a single rq with the estimated
> > average idle time of a domain. As a result, the scan depth can be much
> > larger than it was before the patch and led to some regressions.
>
> Point 1 makes sense to me too
>
> >
> > 2. Accounting for the scan cost of success makes sense but there is a
> > big difference between a scan that finds an idle CPU and one that fails.
> > For failures, the scan cost is wasted CPU time where as a success
> > means that an uncontested CPU is used. This can cause a search to be
> > truncated earlier than it should be when the domain is lightly loaded.
>
> But I'm not sure to catch your problem with point 2.
> track the average cost to scan one rq so looping all rqs are only few
> should not impact (much) the avg_scan_cost
>
> Trying to bias the avg_scan_cost with: loops <<= 2;
> will just make avg_scan_cost lost any kind of meaning because it
> doesn't reflect the avg cost of scanning a rq anymore
>
Before the series, the avg_scan_cost also did not represent the cost of
scanning a RQ before either. Treating scan failures and successes equally
can problems with the depth of the scan conducted. Previously the "cost"
of a successful scan was 0 so successful scans allowed deeper scans in
the near future. This partially illustrates the problem.
5.11.0-rc2 5.11.0-rc2 5.11.0-rc2
baseline-v2r1 acctscan-v2r1 altscan-v2r8
Hmean 1 429.47 ( 0.00%) 420.90 * -2.00%* 414.27 * -3.54%*
Hmean 2 709.39 ( 0.00%) 796.05 * 12.22%* 791.98 * 11.64%*
Hmean 4 1449.19 ( 0.00%) 1445.14 ( -0.28%) 1319.09 * -8.98%*
Hmean 8 2765.65 ( 0.00%) 2750.07 * -0.56%* 2756.17 * -0.34%*
Hmean 16 5158.47 ( 0.00%) 5056.59 * -1.97%* 5030.67 * -2.48%*
Hmean 32 8969.96 ( 0.00%) 8796.96 * -1.93%* 8768.34 * -2.25%*
Hmean 64 11210.05 ( 0.00%) 9910.39 * -11.59%* 11073.42 * -1.22%*
Hmean 128 17978.21 ( 0.00%) 17031.41 * -5.27%* 17037.76 * -5.23%*
Hmean 256 16143.32 ( 0.00%) 15636.59 * -3.14%* 15761.12 * -2.37%*
Hmean 320 16388.59 ( 0.00%) 15591.78 * -4.86%* 15588.85 * -4.88%*
Note the impact of Peters patch (accescan-v2r1) for 64 threads. The
machine is 2-socket (40 cores, 80 threads) so 64 is the load is
balancing between two domains (load balancing vs wakeup migrations).
altscan is my suggested patch on top and with Peter's patch, there is a
11.59% regression that is negligible with my patch on top.
The impact is machine-specific or specific to the CPU generation. Here
is just comparing just the suggested alteration on a slightly older
generation.
5.11.0-rc2 5.11.0-rc2
acctscan-v2r1 altscan-v2r8
Hmean 1 155.44 ( 0.00%) 183.32 * 17.94%*
Hmean 2 445.46 ( 0.00%) 548.51 * 23.13%*
Hmean 4 1080.25 ( 0.00%) 1112.49 * 2.98%*
Hmean 8 2253.48 ( 0.00%) 2457.46 * 9.05%*
Hmean 16 3996.73 ( 0.00%) 4244.59 * 6.20%*
Hmean 32 5318.93 ( 0.00%) 5798.17 * 9.01%*
Hmean 64 9301.55 ( 0.00%) 9563.24 * 2.81%*
Hmean 128 8560.89 ( 0.00%) 8873.72 * 3.65%*
Hmean 192 8526.92 ( 0.00%) 8843.43 * 3.71%*
And another 2-socket machine on a newer generation.
Hmean 1 551.16 ( 0.00%) 503.75 * -8.60%*
Hmean 2 1074.19 ( 0.00%) 1078.08 * 0.36%*
Hmean 4 2024.72 ( 0.00%) 2049.29 * 1.21%*
Hmean 8 3762.49 ( 0.00%) 4002.24 * 6.37%*
Hmean 16 6589.98 ( 0.00%) 6688.21 * 1.49%*
Hmean 32 10080.23 ( 0.00%) 10270.34 * 1.89%*
Hmean 64 11349.16 ( 0.00%) 12452.68 * 9.72%*
Hmean 128 21670.93 ( 0.00%) 21823.70 * 0.70%*
Hmean 256 20605.62 ( 0.00%) 20615.01 * 0.05%*
Hmean 320 20974.29 ( 0.00%) 20565.11 * -1.95%*
For hackbench with processes communicating via pipes on the first
machine
5.11.0-rc2 5.11.0-rc2
acctscan-v2r1 altscan-v2r8
Amean 1 0.3927 ( 0.00%) 0.3943 ( -0.42%)
Amean 4 0.9247 ( 0.00%) 0.9267 ( -0.22%)
Amean 7 1.4587 ( 0.00%) 1.5147 * -3.84%*
Amean 12 2.3637 ( 0.00%) 2.4507 * -3.68%*
Amean 21 4.0700 ( 0.00%) 4.1757 * -2.60%*
Amean 30 5.6573 ( 0.00%) 5.7390 * -1.44%*
Amean 48 8.9037 ( 0.00%) 8.8053 * 1.10%*
Amean 79 14.9190 ( 0.00%) 14.4360 * 3.24%*
Amean 110 22.5703 ( 0.00%) 21.9210 ( 2.88%)
Amean 141 29.2400 ( 0.00%) 28.0110 * 4.20%*
Amean 172 36.3720 ( 0.00%) 34.7963 ( 4.33%)
Amean 203 43.5783 ( 0.00%) 42.5537 * 2.35%*
Amean 234 50.3653 ( 0.00%) 47.3463 * 5.99%*
Amean 265 57.6153 ( 0.00%) 55.6247 * 3.46%*
Amean 296 62.7370 ( 0.00%) 62.0720 ( 1.06%)
Adjusting the scan cost for successes is neither a universal win or
failure but it's closer to historical behaviour and the strict
accounting does hit corner cases. If a deep scan is finding an idle CPU,
it makes some sense to continue scanning deeply by adjusting the weight
instead of prematurely failing.
The testing of the full series previously showed that some loads never
recovered from side-effects of the first patch and the last patch in the
series introduced new problems of its own. Hence, I would like to limit
the negative impact of the first patch and, if necessary, cut the last
patch altogether.
--
Mel Gorman
SUSE Labs
On Fri, 8 Jan 2021 at 15:41, Mel Gorman <[email protected]> wrote:
>
> On Fri, Jan 08, 2021 at 02:41:19PM +0100, Vincent Guittot wrote:
> > > 1. avg_scan_cost is now based on the average scan cost of a rq but
> > > avg_idle is still scaled to the domain size. This is a bit problematic
> > > because it's comparing scan cost of a single rq with the estimated
> > > average idle time of a domain. As a result, the scan depth can be much
> > > larger than it was before the patch and led to some regressions.
> >
> > Point 1 makes sense to me too
> >
> > >
> > > 2. Accounting for the scan cost of success makes sense but there is a
> > > big difference between a scan that finds an idle CPU and one that fails.
> > > For failures, the scan cost is wasted CPU time where as a success
> > > means that an uncontested CPU is used. This can cause a search to be
> > > truncated earlier than it should be when the domain is lightly loaded.
> >
> > But I'm not sure to catch your problem with point 2.
> > track the average cost to scan one rq so looping all rqs are only few
> > should not impact (much) the avg_scan_cost
> >
> > Trying to bias the avg_scan_cost with: loops <<= 2;
> > will just make avg_scan_cost lost any kind of meaning because it
> > doesn't reflect the avg cost of scanning a rq anymore
> >
>
> Before the series, the avg_scan_cost also did not represent the cost of
> scanning a RQ before either. Treating scan failures and successes equally
I agree that the previous avg_scan_cost was not representing a RQ
because it was the avg cost of scanning the full domain. And we were
comparing it with the average idle time (weighted by few factors).
And this cost was impacted by the fact that the scan can return early
because it found a cpu. This has advantage and drawback but at least
stays coherent in what we are comparing
Peter's patch wants to move on per rq avg scan cost. And what you're
proposing is to add a magic heuristic to bias the per rq which at the
end makes this value just an opaque metric.
If we really want to keep the impact of early return than IMO we
should stay on a full domain scan level instead of a per rq.
Also, there is another problem (that I'm investigating) which is that
this_rq()->avg_idle is stalled when your cpu is busy. Which means that
this avg_idle can just be a very old and meaningless value. I think
that we should decay it periodically to reflect there is less and less
idle time (in fact no more) on this busy CPU that never goes to idle.
If a cpu was idle for a long period but then a long running task
starts, the avg_idle will stay stalled to the large value which is
becoming less and less relevant.
At the opposite, a cpu with a short running/idle period task will have
a lower avg_idle whereas it is more often idle.
Another thing that worries me, is that we use the avg_idle of the
local cpu, which is obviously not idle otherwise it would have been
selected, to decide how much time we should spend on looking for
another idle CPU. I'm not sure that's the right metrics to use
especially with a possibly stalled value.
> can problems with the depth of the scan conducted. Previously the "cost"
> of a successful scan was 0 so successful scans allowed deeper scans in
> the near future. This partially illustrates the problem.
>
> 5.11.0-rc2 5.11.0-rc2 5.11.0-rc2
> baseline-v2r1 acctscan-v2r1 altscan-v2r8
> Hmean 1 429.47 ( 0.00%) 420.90 * -2.00%* 414.27 * -3.54%*
> Hmean 2 709.39 ( 0.00%) 796.05 * 12.22%* 791.98 * 11.64%*
> Hmean 4 1449.19 ( 0.00%) 1445.14 ( -0.28%) 1319.09 * -8.98%*
> Hmean 8 2765.65 ( 0.00%) 2750.07 * -0.56%* 2756.17 * -0.34%*
> Hmean 16 5158.47 ( 0.00%) 5056.59 * -1.97%* 5030.67 * -2.48%*
> Hmean 32 8969.96 ( 0.00%) 8796.96 * -1.93%* 8768.34 * -2.25%*
> Hmean 64 11210.05 ( 0.00%) 9910.39 * -11.59%* 11073.42 * -1.22%*
> Hmean 128 17978.21 ( 0.00%) 17031.41 * -5.27%* 17037.76 * -5.23%*
> Hmean 256 16143.32 ( 0.00%) 15636.59 * -3.14%* 15761.12 * -2.37%*
> Hmean 320 16388.59 ( 0.00%) 15591.78 * -4.86%* 15588.85 * -4.88%*
>
> Note the impact of Peters patch (accescan-v2r1) for 64 threads. The
> machine is 2-socket (40 cores, 80 threads) so 64 is the load is
> balancing between two domains (load balancing vs wakeup migrations).
> altscan is my suggested patch on top and with Peter's patch, there is a
> 11.59% regression that is negligible with my patch on top.
>
> The impact is machine-specific or specific to the CPU generation. Here
> is just comparing just the suggested alteration on a slightly older
> generation.
>
> 5.11.0-rc2 5.11.0-rc2
> acctscan-v2r1 altscan-v2r8
> Hmean 1 155.44 ( 0.00%) 183.32 * 17.94%*
> Hmean 2 445.46 ( 0.00%) 548.51 * 23.13%*
> Hmean 4 1080.25 ( 0.00%) 1112.49 * 2.98%*
> Hmean 8 2253.48 ( 0.00%) 2457.46 * 9.05%*
> Hmean 16 3996.73 ( 0.00%) 4244.59 * 6.20%*
> Hmean 32 5318.93 ( 0.00%) 5798.17 * 9.01%*
> Hmean 64 9301.55 ( 0.00%) 9563.24 * 2.81%*
> Hmean 128 8560.89 ( 0.00%) 8873.72 * 3.65%*
> Hmean 192 8526.92 ( 0.00%) 8843.43 * 3.71%*
>
> And another 2-socket machine on a newer generation.
>
> Hmean 1 551.16 ( 0.00%) 503.75 * -8.60%*
> Hmean 2 1074.19 ( 0.00%) 1078.08 * 0.36%*
> Hmean 4 2024.72 ( 0.00%) 2049.29 * 1.21%*
> Hmean 8 3762.49 ( 0.00%) 4002.24 * 6.37%*
> Hmean 16 6589.98 ( 0.00%) 6688.21 * 1.49%*
> Hmean 32 10080.23 ( 0.00%) 10270.34 * 1.89%*
> Hmean 64 11349.16 ( 0.00%) 12452.68 * 9.72%*
> Hmean 128 21670.93 ( 0.00%) 21823.70 * 0.70%*
> Hmean 256 20605.62 ( 0.00%) 20615.01 * 0.05%*
> Hmean 320 20974.29 ( 0.00%) 20565.11 * -1.95%*
>
> For hackbench with processes communicating via pipes on the first
> machine
>
> 5.11.0-rc2 5.11.0-rc2
> acctscan-v2r1 altscan-v2r8
> Amean 1 0.3927 ( 0.00%) 0.3943 ( -0.42%)
> Amean 4 0.9247 ( 0.00%) 0.9267 ( -0.22%)
> Amean 7 1.4587 ( 0.00%) 1.5147 * -3.84%*
> Amean 12 2.3637 ( 0.00%) 2.4507 * -3.68%*
> Amean 21 4.0700 ( 0.00%) 4.1757 * -2.60%*
> Amean 30 5.6573 ( 0.00%) 5.7390 * -1.44%*
> Amean 48 8.9037 ( 0.00%) 8.8053 * 1.10%*
> Amean 79 14.9190 ( 0.00%) 14.4360 * 3.24%*
> Amean 110 22.5703 ( 0.00%) 21.9210 ( 2.88%)
> Amean 141 29.2400 ( 0.00%) 28.0110 * 4.20%*
> Amean 172 36.3720 ( 0.00%) 34.7963 ( 4.33%)
> Amean 203 43.5783 ( 0.00%) 42.5537 * 2.35%*
> Amean 234 50.3653 ( 0.00%) 47.3463 * 5.99%*
> Amean 265 57.6153 ( 0.00%) 55.6247 * 3.46%*
> Amean 296 62.7370 ( 0.00%) 62.0720 ( 1.06%)
>
> Adjusting the scan cost for successes is neither a universal win or
> failure but it's closer to historical behaviour and the strict
> accounting does hit corner cases. If a deep scan is finding an idle CPU,
> it makes some sense to continue scanning deeply by adjusting the weight
> instead of prematurely failing.
>
> The testing of the full series previously showed that some loads never
> recovered from side-effects of the first patch and the last patch in the
> series introduced new problems of its own. Hence, I would like to limit
> the negative impact of the first patch and, if necessary, cut the last
> patch altogether.
>
> --
> Mel Gorman
> SUSE Labs
On Fri, Jan 08, 2021 at 04:10:51PM +0100, Vincent Guittot wrote:
> > > Trying to bias the avg_scan_cost with: loops <<= 2;
> > > will just make avg_scan_cost lost any kind of meaning because it
> > > doesn't reflect the avg cost of scanning a rq anymore
> > >
> >
> > Before the series, the avg_scan_cost also did not represent the cost of
> > scanning a RQ before either. Treating scan failures and successes equally
>
> I agree that the previous avg_scan_cost was not representing a RQ
> because it was the avg cost of scanning the full domain.
It was not even that. As the full domain was not necessarily scanned at
all, it simply reflected how much time was spent scanning in general. It
neither represented an rq scan cost (which is variable due to cache
traffic) nor did it represent a full domain scan.
> And we were
> comparing it with the average idle time (weighted by few factors).
> And this cost was impacted by the fact that the scan can return early
> because it found a cpu. This has advantage and drawback but at least
> stays coherent in what we are comparing
>
Not really because it represented the cost of a scan of some number of
rqs from 1 to sd->span_weight.
> Peter's patch wants to move on per rq avg scan cost. And what you're
> proposing is to add a magic heuristic to bias the per rq which at the
> end makes this value just an opaque metric.
>
The metric is a heuristic no matter what. The scan cost of a RQ is not
fixed as it depends on whether cache data needs to be updated or not. Also
bear in mind that the first round of results and the results that I posted
showed that Peter's patch has significant corner cases that the patch
mitigates. You also note that avg_idle is an unusual metric to compare
against because it has numerous timing artifacts. At least one of them
is that we are extrapolating the domain idle time from a single rq which
is a poor proxy measure when a domain is only partially used. There just
is not a better one available without heavy writes to sd_llc which causes
its own set of problems.
> If we really want to keep the impact of early return than IMO we
> should stay on a full domain scan level instead of a per rq.
>
That also has the same class of side-effects. Once the scan cost of
a successful scan is strictly accounted for, there are problems. Even
tracking the success scans is costly as the CPU clock has to be read and
sd_llc has to be updated.
> Also, there is another problem (that I'm investigating) which is that
> this_rq()->avg_idle is stalled when your cpu is busy. Which means that
> this avg_idle can just be a very old and meaningless value.
Yes, avg_idle in itself is just the average inter-arrival time between
a CPU going idle and receiving a wakeup partially bound roughly
by 2*sysctl_sched_migration_cost. If avg_idle is traced for each
select_idle_cpu(), it's obvious that it takes time to adjust when a
load starts.
> I think
> that we should decay it periodically to reflect there is less and less
> idle time (in fact no more) on this busy CPU that never goes to idle.
> If a cpu was idle for a long period but then a long running task
> starts, the avg_idle will stay stalled to the large value which is
> becoming less and less relevant.
While I get what you're saying, it does not help extrapolate what the
idleness of a domain is.
> At the opposite, a cpu with a short running/idle period task will have
> a lower avg_idle whereas it is more often idle.
>
> Another thing that worries me, is that we use the avg_idle of the
> local cpu, which is obviously not idle otherwise it would have been
> selected, to decide how much time we should spend on looking for
> another idle CPU. I'm not sure that's the right metrics to use
> especially with a possibly stalled value.
>
A better estimate requires heavy writes to sd_llc. The cost of that will
likely offset any benefit gained by a superior selection of a scan
depth.
Treating a successful scan cost and a failed scan cost as being equal has
too many corner cases. If we do not want to weight the successful scan
cost, then the compromise is to keep the old behaviour that accounts for
scan failures only (avoids an sd_llc write at least) but base it on the
estimated scan cost for a single rq. The fact that we do not account for
scan failures should be explicitly commented so we do not forget it
again in the future.
--
Mel Gorman
SUSE Labs
On Fri, Jan 08, 2021 at 04:10:51PM +0100, Vincent Guittot wrote:
> Also, there is another problem (that I'm investigating) which is that
> this_rq()->avg_idle is stalled when your cpu is busy. Which means that
> this avg_idle can just be a very old and meaningless value. I think
> that we should decay it periodically to reflect there is less and less
https://lkml.kernel.org/r/[email protected]
:-)
On Fri, Jan 08, 2021 at 04:10:51PM +0100, Vincent Guittot wrote:
> Another thing that worries me, is that we use the avg_idle of the
> local cpu, which is obviously not idle otherwise it would have been
> selected, to decide how much time we should spend on looking for
> another idle CPU. I'm not sure that's the right metrics to use
> especially with a possibly stalled value.
The thinking was that if this CPU has little idle time, this CPU should
not spend a lot of time searching...
That is; if we spend more time looking for places to run, than we have
idle time, we're loosing cycles we could've ran (supposedly useful) work.
The only counter argument is tail latency.
On Fri, Jan 08, 2021 at 10:27:38AM +0000, Mel Gorman wrote:
> 1. avg_scan_cost is now based on the average scan cost of a rq but
> avg_idle is still scaled to the domain size. This is a bit problematic
> because it's comparing scan cost of a single rq with the estimated
> average idle time of a domain. As a result, the scan depth can be much
> larger than it was before the patch and led to some regressions.
> @@ -6164,25 +6164,25 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
> */
> avg_idle = this_rq()->avg_idle / 512;
> avg_cost = this_sd->avg_scan_cost + 1;
> -
> - span_avg = sd->span_weight * avg_idle;
> - if (span_avg > 4*avg_cost)
> - nr = div_u64(span_avg, avg_cost);
> - else
> + nr = div_u64(avg_idle, avg_cost);
> + if (nr < 4)
> nr = 4;
Oooh, could it be I simply didn't remember how that code was supposed to
work and should kick my (much) younger self for not writing a comment?
Consider:
span_weight * avg_idle avg_cost
nr = ---------------------- = avg_idle / ----------
avg_cost span_weigt
Where: avg_cost / span_weight ~= cost-per-rq
On Fri, Jan 08, 2021 at 09:21:48PM +0100, Peter Zijlstra wrote:
> On Fri, Jan 08, 2021 at 10:27:38AM +0000, Mel Gorman wrote:
>
> > 1. avg_scan_cost is now based on the average scan cost of a rq but
> > avg_idle is still scaled to the domain size. This is a bit problematic
> > because it's comparing scan cost of a single rq with the estimated
> > average idle time of a domain. As a result, the scan depth can be much
> > larger than it was before the patch and led to some regressions.
>
> > @@ -6164,25 +6164,25 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
> > */
> > avg_idle = this_rq()->avg_idle / 512;
> > avg_cost = this_sd->avg_scan_cost + 1;
> > -
> > - span_avg = sd->span_weight * avg_idle;
> > - if (span_avg > 4*avg_cost)
> > - nr = div_u64(span_avg, avg_cost);
> > - else
> > + nr = div_u64(avg_idle, avg_cost);
> > + if (nr < 4)
> > nr = 4;
>
> Oooh, could it be I simply didn't remember how that code was supposed to
> work and should kick my (much) younger self for not writing a comment?
>
> Consider:
>
> span_weight * avg_idle avg_cost
> nr = ---------------------- = avg_idle / ----------
> avg_cost span_weigt
>
> Where: avg_cost / span_weight ~= cost-per-rq
>
This would definitely make sense and I even evaluated it but the nature
of avg_idle and the scale it works at (up to 2*sched_migration_cost)
just ended up generating lunatic values far outside the size of the domain
size. Fitting that to the domain size just ended up looking silly too and
avg_cost does not decay. Still, in principle, it's the right direction,
it's just not what the code does right now.
--
Mel Gorman
SUSE Labs
On Fri, Jan 08, 2021 at 08:45:44PM +0100, Peter Zijlstra wrote:
> On Fri, Jan 08, 2021 at 04:10:51PM +0100, Vincent Guittot wrote:
> > Also, there is another problem (that I'm investigating) which is that
> > this_rq()->avg_idle is stalled when your cpu is busy. Which means that
> > this avg_idle can just be a very old and meaningless value. I think
> > that we should decay it periodically to reflect there is less and less
>
> https://lkml.kernel.org/r/[email protected]
>
> :-)
This needs to be revived. I'm of the opinion that your initial series
needs to be split somewhat into "single scan for core" parts followed by
the "Fix depth selection". I have tests in the queue and one of them is
just patch 2 on its own. Preliminary results for patch 2 on its own do not
look bad but that's based on one test (tbench). It'll be tomorrow before
it works through variants of patch 1 which I suspect will be inconclusive
and make me more convinced it should be split out separately.
The single scan for core would be patches 2-4 of the series this thread
is about which is an orthogonal problem to avoiding repeated scans of
the same runqueues during a single wakeup. I would prefer to drop patch
5 initially because the has_idle_cores throttling mechanism for idle core
searches is reasonably effective and the first round of tests indicated
that changing it was inconclusive and should be treated separately.
The depth scan stuff would go on top because right now the depth scan is
based on magic numbers and no amount of shuffling that around will make
it less magic without an avg_idle value that decays and potentially the
scan cost also aging. It's much less straight-forward than the single
scan aspect.
Switching idle core searches to SIS_PROP should also be treated
separately.
Thoughts? I don't want to go too far in this direction on my own because
the testing requirements are severe in terms of time. Even then no matter
how much I test, stuff will be missed as it's sensitive to domain sizes,
CPU generation, cache topology, cache characteristics, domain utilisation,
architecture, kitchen sink etc.
--
Mel Gorman
SUSE Labs
On Fri, 8 Jan 2021 at 17:14, Mel Gorman <[email protected]> wrote:
>
> On Fri, Jan 08, 2021 at 04:10:51PM +0100, Vincent Guittot wrote:
> > > > Trying to bias the avg_scan_cost with: loops <<= 2;
> > > > will just make avg_scan_cost lost any kind of meaning because it
> > > > doesn't reflect the avg cost of scanning a rq anymore
> > > >
> > >
> > > Before the series, the avg_scan_cost also did not represent the cost of
> > > scanning a RQ before either. Treating scan failures and successes equally
> >
> > I agree that the previous avg_scan_cost was not representing a RQ
> > because it was the avg cost of scanning the full domain.
>
> It was not even that. As the full domain was not necessarily scanned at
> all, it simply reflected how much time was spent scanning in general. It
> neither represented an rq scan cost (which is variable due to cache
> traffic) nor did it represent a full domain scan.
My point was mainly that the goal was to monitor the avg scan cost for
the domain (whatever the number of rq effectively checked) so the
duration was impacted by a successful scan that returns earlier
>
> > And we were
> > comparing it with the average idle time (weighted by few factors).
> > And this cost was impacted by the fact that the scan can return early
> > because it found a cpu. This has advantage and drawback but at least
> > stays coherent in what we are comparing
> >
>
> Not really because it represented the cost of a scan of some number of
> rqs from 1 to sd->span_weight.
>
> > Peter's patch wants to move on per rq avg scan cost. And what you're
> > proposing is to add a magic heuristic to bias the per rq which at the
> > end makes this value just an opaque metric.
> >
>
> The metric is a heuristic no matter what. The scan cost of a RQ is not
> fixed as it depends on whether cache data needs to be updated or not. Also
> bear in mind that the first round of results and the results that I posted
> showed that Peter's patch has significant corner cases that the patch
> mitigates. You also note that avg_idle is an unusual metric to compare
> against because it has numerous timing artifacts. At least one of them
> is that we are extrapolating the domain idle time from a single rq which
> is a poor proxy measure when a domain is only partially used. There just
> is not a better one available without heavy writes to sd_llc which causes
> its own set of problems.
>
> > If we really want to keep the impact of early return than IMO we
> > should stay on a full domain scan level instead of a per rq.
> >
>
> That also has the same class of side-effects. Once the scan cost of
> a successful scan is strictly accounted for, there are problems. Even
> tracking the success scans is costly as the CPU clock has to be read and
> sd_llc has to be updated.
>
> > Also, there is another problem (that I'm investigating) which is that
> > this_rq()->avg_idle is stalled when your cpu is busy. Which means that
> > this avg_idle can just be a very old and meaningless value.
>
> Yes, avg_idle in itself is just the average inter-arrival time between
> a CPU going idle and receiving a wakeup partially bound roughly
> by 2*sysctl_sched_migration_cost. If avg_idle is traced for each
> select_idle_cpu(), it's obvious that it takes time to adjust when a
> load starts.
>
> > I think
> > that we should decay it periodically to reflect there is less and less
> > idle time (in fact no more) on this busy CPU that never goes to idle.
> > If a cpu was idle for a long period but then a long running task
> > starts, the avg_idle will stay stalled to the large value which is
> > becoming less and less relevant.
>
> While I get what you're saying, it does not help extrapolate what the
> idleness of a domain is.
not but it gives a more up to date view of the idleness of the local
cpu which is better than a stalled value
>
> > At the opposite, a cpu with a short running/idle period task will have
> > a lower avg_idle whereas it is more often idle.
> >
> > Another thing that worries me, is that we use the avg_idle of the
> > local cpu, which is obviously not idle otherwise it would have been
> > selected, to decide how much time we should spend on looking for
> > another idle CPU. I'm not sure that's the right metrics to use
> > especially with a possibly stalled value.
> >
>
> A better estimate requires heavy writes to sd_llc. The cost of that will
> likely offset any benefit gained by a superior selection of a scan
> depth.
>
> Treating a successful scan cost and a failed scan cost as being equal has
> too many corner cases. If we do not want to weight the successful scan
> cost, then the compromise is to keep the old behaviour that accounts for
I think that keeping the current way to scane_cost id the best option for now
> scan failures only (avoids an sd_llc write at least) but base it on the
> estimated scan cost for a single rq. The fact that we do not account for
> scan failures should be explicitly commented so we do not forget it
> again in the future.
>
> --
> Mel Gorman
> SUSE Labs
On Fri, 8 Jan 2021 at 20:45, Peter Zijlstra <[email protected]> wrote:
>
> On Fri, Jan 08, 2021 at 04:10:51PM +0100, Vincent Guittot wrote:
> > Also, there is another problem (that I'm investigating) which is that
> > this_rq()->avg_idle is stalled when your cpu is busy. Which means that
> > this avg_idle can just be a very old and meaningless value. I think
> > that we should decay it periodically to reflect there is less and less
>
> https://lkml.kernel.org/r/[email protected]
>
> :-)
:-)
I was more thinking of something like decaying avg_idle during
tick_fair but at leat we all agree that we can't stay with a stalled
avg_idle value
On Fri, 8 Jan 2021 at 20:49, Peter Zijlstra <[email protected]> wrote:
>
> On Fri, Jan 08, 2021 at 04:10:51PM +0100, Vincent Guittot wrote:
> > Another thing that worries me, is that we use the avg_idle of the
> > local cpu, which is obviously not idle otherwise it would have been
> > selected, to decide how much time we should spend on looking for
> > another idle CPU. I'm not sure that's the right metrics to use
> > especially with a possibly stalled value.
>
> The thinking was that if this CPU has little idle time, this CPU should
> not spend a lot of time searching...
>
> That is; if we spend more time looking for places to run, than we have
> idle time, we're loosing cycles we could've ran (supposedly useful) work.
I understand the rationale of looking at previous avg idle time to
decide how much time we can "waste" at looking at a cpu for the waking
task. The problem is that this value is "stalled" and it gives us an
idea of the duration of the next idle time but not really when the
next idle time will happen, which can be in several seconds from now.
And we can have already use this next avg_idle time for other wakeups
search
>
> The only counter argument is tail latency.
On Mon, Jan 11, 2021 at 03:36:57PM +0100, Vincent Guittot wrote:
> > > <SNIP>
> > >
> > > I think
> > > that we should decay it periodically to reflect there is less and less
> > > idle time (in fact no more) on this busy CPU that never goes to idle.
> > > If a cpu was idle for a long period but then a long running task
> > > starts, the avg_idle will stay stalled to the large value which is
> > > becoming less and less relevant.
> >
> > While I get what you're saying, it does not help extrapolate what the
> > idleness of a domain is.
>
> not but it gives a more up to date view of the idleness of the local
> cpu which is better than a stalled value
>
Fair enough.
> >
> > > At the opposite, a cpu with a short running/idle period task will have
> > > a lower avg_idle whereas it is more often idle.
> > >
> > > Another thing that worries me, is that we use the avg_idle of the
> > > local cpu, which is obviously not idle otherwise it would have been
> > > selected, to decide how much time we should spend on looking for
> > > another idle CPU. I'm not sure that's the right metrics to use
> > > especially with a possibly stalled value.
> > >
> >
> > A better estimate requires heavy writes to sd_llc. The cost of that will
> > likely offset any benefit gained by a superior selection of a scan
> > depth.
> >
> > Treating a successful scan cost and a failed scan cost as being equal has
> > too many corner cases. If we do not want to weight the successful scan
> > cost, then the compromise is to keep the old behaviour that accounts for
>
> I think that keeping the current way to scane_cost id the best option for now
>
I sent a series that drops this patch for the moment as well as the
SIS_PROP for selecting a core.
--
Mel Gorman
SUSE Labs