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

[Rafael J. Wysocki]

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

> 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;
>         }
>