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

[Christian Loehle <christian.loehle@arm.com>]

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>