diff mbox series

[RFT,v1,2/5] cpuidle: menu: Use one loop for average and variance computations

Message ID 3339073.aeNJFYEL58@rjwysocki.net (mailing list archive)
State Queued
Delegated to: Rafael Wysocki
Headers show
Series cpuidle: menu: Avoid discarding useful information when processing recent idle intervals | expand

Commit Message

Rafael J. Wysocki Feb. 6, 2025, 2:24 p.m. UTC 
From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>

Use the observation that one loop is sufficient to compute the average
of an array of values and their variance to eliminate one of the loops
from get_typical_interval().

While at it, make get_typical_interval() consistently use u64 as the
64-bit unsigned integer data type and rearrange some white space and the
declarations of local variables in it (to make them follow the reverse
X-mas tree pattern).

No intentional functional impact.

Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
---
 drivers/cpuidle/governors/menu.c |   61 +++++++++++++++++----------------------
 1 file changed, 28 insertions(+), 33 deletions(-)

Comments

Christian Loehle Feb. 17, 2025, 1:03 p.m. UTC | #1 
On 2/6/25 14:24, Rafael J. Wysocki wrote:
> From: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> 
> Use the observation that one loop is sufficient to compute the average
> of an array of values and their variance to eliminate one of the loops
> from get_typical_interval().
> 
> While at it, make get_typical_interval() consistently use u64 as the
> 64-bit unsigned integer data type and rearrange some white space and the
> declarations of local variables in it (to make them follow the reverse
> X-mas tree pattern).
> 
> No intentional functional impact.
> 
> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
> ---
>  drivers/cpuidle/governors/menu.c |   61 +++++++++++++++++----------------------
>  1 file changed, 28 insertions(+), 33 deletions(-)
> 
> --- a/drivers/cpuidle/governors/menu.c
> +++ b/drivers/cpuidle/governors/menu.c
> @@ -116,49 +116,45 @@
>   */
>  static unsigned int get_typical_interval(struct menu_device *data)
>  {
> -	int i, divisor;
> -	unsigned int max, thresh, avg;
> -	uint64_t sum, variance;
> -
> -	thresh = INT_MAX; /* Discard outliers above this value */
> +	unsigned int max, divisor, thresh = INT_MAX;
> +	u64 avg, variance, avg_sq;
> +	int i;
>  
>  again:
> -
> -	/* First calculate the average of past intervals */
> +	/* Compute the average and variance of past intervals. */
>  	max = 0;
> -	sum = 0;
> +	avg = 0;
> +	variance = 0;
>  	divisor = 0;
>  	for (i = 0; i < INTERVALS; i++) {
>  		unsigned int value = data->intervals[i];
> -		if (value <= thresh) {
> -			sum += value;
> -			divisor++;
> -			if (value > max)
> -				max = value;
> -		}
> +
> +		/* Discard data points above the threshold. */
> +		if (value > thresh)
> +			continue;
> +
> +		divisor++;
> +
> +		avg += value;
> +		variance += (u64)value * value;
> +
> +		if (value > max)
> +			max = value;
>  	}
>  
>  	if (!max)
>  		return UINT_MAX;
>  
> -	if (divisor == INTERVALS)
> -		avg = sum >> INTERVAL_SHIFT;
> -	else
> -		avg = div_u64(sum, divisor);
> -
> -	/* Then try to determine variance */
> -	variance = 0;
> -	for (i = 0; i < INTERVALS; i++) {
> -		unsigned int value = data->intervals[i];
> -		if (value <= thresh) {
> -			int64_t diff = (int64_t)value - avg;
> -			variance += diff * diff;
> -		}
> -	}
> -	if (divisor == INTERVALS)
> +	if (divisor == INTERVALS) {
> +		avg >>= INTERVAL_SHIFT;
>  		variance >>= INTERVAL_SHIFT;
> -	else
> +	} else {
> +		do_div(avg, divisor);
>  		do_div(variance, divisor);
> +	}
> +
> +	avg_sq = avg * avg;
> +	variance -= avg_sq;
>  
>  	/*
>  	 * The typical interval is obtained when standard deviation is
> @@ -173,10 +169,9 @@
>  	 * Use this result only if there is no timer to wake us up sooner.
>  	 */
>  	if (likely(variance <= U64_MAX/36)) {
> -		if ((((u64)avg*avg > variance*36) && (divisor * 4 >= INTERVALS * 3))
> -							|| variance <= 400) {
> +		if ((avg_sq > variance * 36 && divisor * 4 >= INTERVALS * 3) ||
> +		    variance <= 400)
>  			return avg;
> -		}
>  	}
>  
>  	/*
> 

Reviewed-by: Christian Loehle <christian.loehle@arm.com>
diff mbox series

Patch

--- a/drivers/cpuidle/governors/menu.c
+++ b/drivers/cpuidle/governors/menu.c
@@ -116,49 +116,45 @@ 
  */
 static unsigned int get_typical_interval(struct menu_device *data)
 {
-	int i, divisor;
-	unsigned int max, thresh, avg;
-	uint64_t sum, variance;
-
-	thresh = INT_MAX; /* Discard outliers above this value */
+	unsigned int max, divisor, thresh = INT_MAX;
+	u64 avg, variance, avg_sq;
+	int i;
 
 again:
-
-	/* First calculate the average of past intervals */
+	/* Compute the average and variance of past intervals. */
 	max = 0;
-	sum = 0;
+	avg = 0;
+	variance = 0;
 	divisor = 0;
 	for (i = 0; i < INTERVALS; i++) {
 		unsigned int value = data->intervals[i];
-		if (value <= thresh) {
-			sum += value;
-			divisor++;
-			if (value > max)
-				max = value;
-		}
+
+		/* Discard data points above the threshold. */
+		if (value > thresh)
+			continue;
+
+		divisor++;
+
+		avg += value;
+		variance += (u64)value * value;
+
+		if (value > max)
+			max = value;
 	}
 
 	if (!max)
 		return UINT_MAX;
 
-	if (divisor == INTERVALS)
-		avg = sum >> INTERVAL_SHIFT;
-	else
-		avg = div_u64(sum, divisor);
-
-	/* Then try to determine variance */
-	variance = 0;
-	for (i = 0; i < INTERVALS; i++) {
-		unsigned int value = data->intervals[i];
-		if (value <= thresh) {
-			int64_t diff = (int64_t)value - avg;
-			variance += diff * diff;
-		}
-	}
-	if (divisor == INTERVALS)
+	if (divisor == INTERVALS) {
+		avg >>= INTERVAL_SHIFT;
 		variance >>= INTERVAL_SHIFT;
-	else
+	} else {
+		do_div(avg, divisor);
 		do_div(variance, divisor);
+	}
+
+	avg_sq = avg * avg;
+	variance -= avg_sq;
 
 	/*
 	 * The typical interval is obtained when standard deviation is
@@ -173,10 +169,9 @@ 
 	 * Use this result only if there is no timer to wake us up sooner.
 	 */
 	if (likely(variance <= U64_MAX/36)) {
-		if ((((u64)avg*avg > variance*36) && (divisor * 4 >= INTERVALS * 3))
-							|| variance <= 400) {
+		if ((avg_sq > variance * 36 && divisor * 4 >= INTERVALS * 3) ||
+		    variance <= 400)
 			return avg;
-		}
 	}
 
 	/*