[PATCH] cpuidle: menu: correct variance calculation

[PATCH] cpuidle: menu: correct variance calculation

[Julia Lawall]

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)

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@inria.fr>
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;
 	}

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

[Rafael J. Wysocki]

On Wed, Apr 29, 2026 at 5:35 PM Julia Lawall <Julia.Lawall@inria.fr> 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@inria.fr>
> 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;
>         }
>

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

[Julia Lawall]

[-- Attachment #1: Type: text/plain, Size: 4168 bytes --]



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

> On Wed, Apr 29, 2026 at 5:35 PM Julia Lawall <Julia.Lawall@inria.fr> 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

Suppose you have 10 10 10 10 10 10 10 10 10
The sum of the squares is 800.
The average is 10.
The square of the average is 100.
So the current formula gives 800 - 100 = 700 as the numerator.  It is
supposed to be 0.

800 - (80 * 10) = 0

I took the formula from the same page but in the discrete random variable
section, in the sentence:

The variance of a collection of n {\displaystyle n} equally likely values
can be written as ...

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@inria.fr>
> > 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;
> >         }
> >
>

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

[Julia Lawall]

[-- Attachment #1: Type: text/plain, Size: 4038 bytes --]



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

> On Wed, Apr 29, 2026 at 5:35 PM Julia Lawall <Julia.Lawall@inria.fr> 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@inria.fr>
> > 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;
> >         }
> >
>