Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1611047 > unrolled thread
| Started by | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| First post | 2017-03-28 16:50 +0200 |
| Last post | 2017-03-31 04:50 +0200 |
| Articles | 3 on this page of 23 — 4 participants |
Back to article view | Back to linux.kernel
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-28 16:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Yuyang Du <yuyang.du@intel.com> - 2017-03-29 10:20 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-29 12:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Yuyang Du <yuyang.du@intel.com> - 2017-03-30 04:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Paul Turner <pjt@google.com> - 2017-03-30 13:30 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-30 14:20 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-30 15:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Yuyang Du <yuyang.du@intel.com> - 2017-03-31 05:00 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-30 16:20 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Paul Turner <pjt@google.com> - 2017-03-31 00:10 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-31 09:10 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Paul Turner <pjt@google.com> - 2017-03-31 12:00 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-31 13:30 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Dietmar Eggemann <dietmar.eggemann@arm.com> - 2017-04-10 09:40 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-04-10 10:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-31 13:40 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Yuyang Du <yuyang.du@intel.com> - 2017-03-31 05:20 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Yuyang Du <yuyang.du@intel.com> - 2017-03-31 05:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-31 09:20 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Paul Turner <pjt@google.com> - 2017-03-31 13:00 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-03-31 13:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Peter Zijlstra <peterz@infradead.org> - 2017-04-10 12:50 +0200
Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Yuyang Du <yuyang.du@intel.com> - 2017-03-31 04:50 +0200
Page 2 of 2 — ← Prev page 1 [2]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-03-31 13:50 +0200 |
| Message-ID | <tr3e2-45U-17@gated-at.bofh.it> |
| In reply to | #1613863 |
On Fri, Mar 31, 2017 at 03:55:40AM -0700, Paul Turner wrote:
> > I'm thinking that we can compute the middle segment, by taking the max
> > value and chopping off the ends, like:
> >
>
> >
> > p
> > c2 = 1024 \Sum y^n
> > n=1
> >
> > inf inf
> > = 1024 ( \Sum y^n - \Sum y^n - y^0 )
> > n=0 n=p
> >
>
> Very nice!
> Minor nit: Second sum needs to be from n=p+1
Correct.
> > +static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
> > {
> > + u32 c1, c2, c3 = d3; /* y^0 == 1 */
> >
> > /*
> > * c1 = d1 y^(p+1)
> > */
> > + c1 = decay_load((u64)d1, periods);
> >
> > /*
> > + * p
> > + * c2 = 1024 \Sum y^n
> > + * n=1
> > *
> > + * inf inf
> > + * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
> > + * n=0 n=p+1
> > */
> > + c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
>
> decay_load(LOAD_AVG_MAX, periods + 1)
So here, @periods == p+1, see also c1. Yes, this is confusing [*].
In particular, I think the decay terms for c1 and this should be the
same. We cut off this tail end of the series to replace it with c1 after
all.
[*] hysterically p used to be off by 1, which is where the p+1 came
from, but now periods includes it. I was thinking of doing a patch
correcting all the comments to fully eradicate the whole +1 business.
> I computed all the values vs true value that the old/new computations
> result in, and it's very close. Absolutely it's approximately 2x off
> the previous computation, e.g. if the old value was -15 (relative to
> true value) than the new computation is -30.
>
> This is definitely more than good enough. If we want more precision,
> then the correction factor of:
> +clamp(periods, 0, 45)
Can you do a patch with coherent comment explaining where that
correction term comes from?
[toc] | [prev] | [next] | [standalone]
| From | Peter Zijlstra <peterz@infradead.org> |
|---|---|
| Date | 2017-04-10 12:50 +0200 |
| Message-ID | <tuF3s-7X5-11@gated-at.bofh.it> |
| In reply to | #1613929 |
On Fri, Mar 31, 2017 at 01:38:55PM +0200, Peter Zijlstra wrote: > So here, @periods == p+1, see also c1. Yes, this is confusing [*]. > [*] hysterically p used to be off by 1, which is where the p+1 came > from, but now periods includes it. I was thinking of doing a patch > correcting all the comments to fully eradicate the whole +1 business. Something like so; which also makes it obvious p == 0 is not 'right'. --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2777,18 +2777,18 @@ static u32 __accumulate_pelt_segments(u6 u32 c1, c2, c3 = d3; /* y^0 == 1 */ /* - * c1 = d1 y^(p+1) + * c1 = d1 y^p */ c1 = decay_load((u64)d1, periods); /* - * p + * p-1 * c2 = 1024 \Sum y^n * n=1 * * inf inf * = 1024 ( \Sum y^n - \Sum y^n - y^0 ) - * n=0 n=p+1 + * n=0 n=p */ c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024; @@ -2808,15 +2808,15 @@ static u32 __accumulate_pelt_segments(u6 * |<->|<----------------->|<--->| * ... |---x---|------| ... |------|-----x (now) * - * p - * u' = (u + d1) y^(p+1) + 1024 \Sum y^n + d3 y^0 - * n=1 + * p-1 + * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0 + * n=1 * - * = u y^(p+1) + (Step 1) + * = u y^p + (Step 1) * - * p - * d1 y^(p+1) + 1024 \Sum y^n + d3 y^0 (Step 2) - * n=1 + * p-1 + * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2) + * n=1 */ static __always_inline u32 accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, > > I computed all the values vs true value that the old/new computations > > result in, and it's very close. Absolutely it's approximately 2x off > > the previous computation, e.g. if the old value was -15 (relative to > > true value) than the new computation is -30. > > > > This is definitely more than good enough. If we want more precision, > > then the correction factor of: > > +clamp(periods, 0, 45) > > Can you do a patch with coherent comment explaining where that > correction term comes from? ping?
[toc] | [prev] | [next] | [standalone]
| From | Yuyang Du <yuyang.du@intel.com> |
|---|---|
| Date | 2017-03-31 04:50 +0200 |
| Message-ID | <tqUNs-70F-5@gated-at.bofh.it> |
| In reply to | #1612973 |
Hi Paul,
On Thu, Mar 30, 2017 at 04:21:08AM -0700, Paul Turner wrote:
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -2767,7 +2767,7 @@ static const u32 __accumulated_sum_N32[]
> > * Approximate:
> > * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
> > */
> > -static __always_inline u64 decay_load(u64 val, u64 n)
> > +static u64 decay_load(u64 val, u64 n)
> > {
> > unsigned int local_n;
> >
> > @@ -2795,32 +2795,113 @@ static __always_inline u64 decay_load(u6
> > return val;
> > }
> >
> > -/*
> > - * For updates fully spanning n periods, the contribution to runnable
> > - * average will be: \Sum 1024*y^n
> > - *
> > - * We can compute this reasonably efficiently by combining:
> > - * y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for n <PERIOD}
> > - */
> > -static u32 __compute_runnable_contrib(u64 n)
> > +static u32 __accumulate_sum(u64 periods, u32 period_contrib, u32 remainder)
>
> - The naming here is really ambiguous:
> "__accumulate_sum" -> "__accumulate_pelt_segments"?
Yes, sounds better :)
> - Passing in "remainder" seems irrelevant to the sum accumulation. It would be
> more clear to handle it from the caller.
It's relevant, because it "may" be c3. But maybe "remainder" isn't a good name,
as it's actually:
delta %= 1024, in which delta is (now - last_period_boundary).
> >
> > {
> > - u32 contrib = 0;
> > + u32 c1, c2, c3 = remainder; /* y^0 == 1 */
> >
> > - if (likely(n <= LOAD_AVG_PERIOD))
> > - return runnable_avg_yN_sum[n];
> > - else if (unlikely(n >= LOAD_AVG_MAX_N))
> > + if (!periods)
> > + return remainder - period_contrib;
>
> This is super confusing. It only works because remainder already had
> period_contrib aggregated _into_ it. We're literally computing:
> remainder + period_contrib - period_contrib
Sort of, but we're just reusing (delta += period_contrib), which is the simple
way to compute periods. And we carry the hope that we passed (delta %= 1024) as
the c3 if (periods). Or we could keep the real "delta" only for the !0 periods
case, which is good too. Yes, making the code as compact as possible produces
confusion, in which direction I have gone too much.
> We should just not call this in the !periods case and handle the remainder
> below.
It'd be clear to stick to __accumulate_pelt_segments() being c1 + c2 + c3,
described as step 2.
> > +
> > + if (unlikely(periods >= LOAD_AVG_MAX_N))
> > return LOAD_AVG_MAX;
> >
> > - /* Since n < LOAD_AVG_MAX_N, n/LOAD_AVG_PERIOD < 11 */
> > - contrib = __accumulated_sum_N32[n/LOAD_AVG_PERIOD];
> > - n %= LOAD_AVG_PERIOD;
> > - contrib = decay_load(contrib, n);
> > - return contrib + runnable_avg_yN_sum[n];
> > + /*
> > + * c1 = d1 y^(p+1)
> > + */
> > + c1 = decay_load((u64)(1024 - period_contrib), periods);
> > +
> > + periods -= 1;
> > + /*
> > + * For updates fully spanning n periods, the contribution to runnable
> > + * average will be:
> > + *
> > + * c2 = 1024 \Sum y^n
> > + *
> > + * We can compute this reasonably efficiently by combining:
> > + *
> > + * y^PERIOD = 1/2 with precomputed 1024 \Sum y^n {for: n < PERIOD}
> > + */
> > + if (likely(periods <= LOAD_AVG_PERIOD)) {
> > + c2 = runnable_avg_yN_sum[periods];
> > + } else {
> > + c2 = __accumulated_sum_N32[periods/LOAD_AVG_PERIOD];
>
> This still wants the comment justifying why we can't overflow.
Yes, and it'd be:
/*
* We can't overflow because we would have returned if
* periods >= LOAD_AVG_MAX_N.
*/
> > + periods %= LOAD_AVG_PERIOD;
> > + c2 = decay_load(c2, periods);
> > + c2 += runnable_avg_yN_sum[periods];
> > + }
> > +
> > + return c1 + c2 + c3;
> > }
> >
> > #define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
> >
> > /*
> > + * Accumulate the three separate parts of the sum; d1 the remainder
> > + * of the last (incomplete) period, d2 the span of full periods and d3
> > + * the remainder of the (incomplete) current period.
> > + *
> > + * d1 d2 d3
> > + * ^ ^ ^
> > + * | | |
> > + * |<->|<----------------->|<--->|
> > + * ... |---x---|------| ... |------|-----x (now)
> > + *
> > + * p
> > + * u' = (u + d1) y^(p+1) + 1024 \Sum y^n + d3 y^0
> > + * n=1
> > + *
> > + * = u y^(p+1) + (Step 1)
> > + *
> > + * p
> > + * d1 y^(p+1) + 1024 \Sum y^n + d3 y^0 (Step 2)
> > + * n=1
> > + */
> > +static __always_inline u32
> > +accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
> > + unsigned long weight, int running, struct cfs_rq *cfs_rq)
> > +{
> > + unsigned long scale_freq, scale_cpu;
> > + u64 periods;
> > + u32 contrib;
> > +
> > + scale_freq = arch_scale_freq_capacity(NULL, cpu);
> > + scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
> > +
> > + delta += sa->period_contrib;
> > + periods = delta / 1024; /* A period is 1024us (~1ms) */
> > +
> > + if (periods) {
> > + sa->load_sum = decay_load(sa->load_sum, periods);
> > + if (cfs_rq) {
> > + cfs_rq->runnable_load_sum =
> > + decay_load(cfs_rq->runnable_load_sum, periods);
> > + }
> > + sa->util_sum = decay_load((u64)(sa->util_sum), periods);
>
> Move step 2 here, handle remainder below.
See above.
Thanks,
Yuyang
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | linux.kernel
csiph-web