Re: [PATCH] cpuidle: menu: correct variance calculation

[Julia Lawall]

On Wed, 29 Apr 2026, Rafael J. Wysocki wrote:

> On Wed, Apr 29, 2026 at 5:35 PM Julia Lawall <Julia.Lawall@xxxxxxxx> wrote:
> >
> > Commit 13982929fb08 ("cpuidle: menu: Use one loop for average and
> > variance computations") simplified the numerator of the variance
> > calculation to:
> >
> > sum of squares of idle times - (average idle time)^2
> >
> > This computes a value that is typically too big.  The formula should be
> >
> > sum of squares of idle times - (sum of idle times * average idle time)
>
> I'm not sure why.
>
> According to Wikipedia Var(X) = E[X^2] - E[X]^2:
>
> https://en.wikipedia.org/wiki/Variance

OK, looking again at the formulas, I may be wrong about the calculation.
I was assuming that the division by N was at the end of the calculation of
the variance, but now that I am paying more attention, I see that it is
before the subtraction.  So maybe the formula is OK as is.

Thanks for the feedback.

julia

>
> > On a small number of tests I didn't find any significant performance
> > change.  Likewise, the original patch was tested by various people and
> > was presumably not observed to cause any problem.  My impression is
> > that this is because the actual variance is almost always quite high
> > (greater than the threshold of 400 used by get_typical_interval), so
> > having a value that is even higher than it should be doesn't matter.
> >
> > Signed-off-by: Julia Lawall <Julia.Lawall@xxxxxxxx>
> > Fixes: 13982929fb08 ("cpuidle: menu: Use one loop for average and variance computations")
> >
> > ---
> >
> >  drivers/cpuidle/governors/menu.c |   14 +++++++-------
> >  1 file changed, 7 insertions(+), 7 deletions(-)
> >
> > diff --git a/drivers/cpuidle/governors/menu.c b/drivers/cpuidle/governors/menu.c
> > index 64d6f7a1c776..8cbd70cafe89 100644
> > --- a/drivers/cpuidle/governors/menu.c
> > +++ b/drivers/cpuidle/governors/menu.c
> > @@ -117,14 +117,14 @@ static unsigned int get_typical_interval(struct menu_device *data)
> >  {
> >         s64 value, min_thresh = -1, max_thresh = UINT_MAX;
> >         unsigned int max, min, divisor;
> > -       u64 avg, variance, avg_sq;
> > +       u64 avg, variance, sum;
> >         int i;
> >
> >  again:
> >         /* Compute the average and variance of past intervals. */
> >         max = 0;
> >         min = UINT_MAX;
> > -       avg = 0;
> > +       sum = 0;
> >         variance = 0;
> >         divisor = 0;
> >         for (i = 0; i < INTERVALS; i++) {
> > @@ -138,7 +138,7 @@ static unsigned int get_typical_interval(struct menu_device *data)
> >
> >                 divisor++;
> >
> > -               avg += value;
> > +               sum += value;
> >                 variance += value * value;
> >
> >                 if (value > max)
> > @@ -151,17 +151,17 @@ static unsigned int get_typical_interval(struct menu_device *data)
> >         if (!max)
> >                 return UINT_MAX;
> >
> > +       avg = sum;
> >         if (divisor == INTERVALS) {
> >                 avg >>= INTERVAL_SHIFT;
> > +               variance = variance - (sum * avg);
> >                 variance >>= INTERVAL_SHIFT;
> >         } else {
> >                 do_div(avg, divisor);
> > +               variance = variance - (sum * avg);
> >                 do_div(variance, divisor);
> >         }
> >
> > -       avg_sq = avg * avg;
> > -       variance -= avg_sq;
> > -
> >         /*
> >          * The typical interval is obtained when standard deviation is
> >          * small (stddev <= 20 us, variance <= 400 us^2) or standard
> > @@ -175,7 +175,7 @@ static unsigned int get_typical_interval(struct menu_device *data)
> >          * Use this result only if there is no timer to wake us up sooner.
> >          */
> >         if (likely(variance <= U64_MAX/36)) {
> > -               if ((avg_sq > variance * 36 && divisor * 4 >= INTERVALS * 3) ||
> > +               if ((avg * avg > variance * 36 && divisor * 4 >= INTERVALS * 3) ||
> >                     variance <= 400)
> >                         return avg;
> >         }
> >
>