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