Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg()

From: Peter Zijlstra
Date: Mon Apr 10 2017 - 06:47:47 EST


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?