| Message ID | 2301940.iZASKD2KPV@rjwysocki.net |
|---|---|
| State | New |
| Headers | show |
| Series | cpuidle: menu: Avoid discarding useful information when processing recent idle intervals | expand |
On 2/6/25 14:26, Rafael J. Wysocki wrote: > From: Rafael J. Wysocki <rafael.j.wysocki@intel.com> > > Currently, get_typical_interval() attempts to eliminate outliers at the > high end of the sample set only (probably in order to bias the prediction > toward lower values), but this it problematic because if the outliers are > present at the low end of the sample set, discarding the highest values > will not help to reduce the variance. > > Since the presence of outliers at the low end of the sample set is > generally as likely as their presence at the high end of the sample > set, modify get_typical_interval() to treat samples at the largest > distances from the average (on both ends of the sample set) as outliers. > > This should increase the likelihood of making a meaningful prediction > in some cases. > > Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com> > --- > drivers/cpuidle/governors/menu.c | 32 ++++++++++++++++++++++---------- > 1 file changed, 22 insertions(+), 10 deletions(-) > > --- a/drivers/cpuidle/governors/menu.c > +++ b/drivers/cpuidle/governors/menu.c > @@ -116,30 +116,37 @@ > */ > static unsigned int get_typical_interval(struct menu_device *data) > { > - unsigned int max, divisor, thresh = UINT_MAX; > + s64 value, min_thresh = -1, max_thresh = UINT_MAX; > + unsigned int max, min, divisor; > u64 avg, variance, avg_sq; > int i; > > again: > /* Compute the average and variance of past intervals. */ > max = 0; > + min = UINT_MAX; > avg = 0; > variance = 0; > divisor = 0; > for (i = 0; i < INTERVALS; i++) { > - unsigned int value = data->intervals[i]; > - > - /* Discard data points above or at the threshold. */ > - if (value >= thresh) > + value = data->intervals[i]; > + /* > + * Discard the samples outside the interval between the min and > + * max thresholds. > + */ > + if (value <= min_thresh || value >= max_thresh) > continue; > > divisor++; > > avg += value; > - variance += (u64)value * value; > + variance += value * value; > > if (value > max) > max = value; > + > + if (value < min) > + min = value; > } > > if (!max) > @@ -175,10 +182,10 @@ > } > > /* > - * If we have outliers to the upside in our distribution, discard > - * those by setting the threshold to exclude these outliers, then > + * If there are outliers, discard them by setting thresholds to exclude > + * data points at a large enough distance from the average, then > * calculate the average and standard deviation again. Once we get > - * down to the bottom 3/4 of our samples, stop excluding samples. > + * down to the last 3/4 of our samples, stop excluding samples. > * > * This can deal with workloads that have long pauses interspersed > * with sporadic activity with a bunch of short pauses. > @@ -186,7 +193,12 @@ > if ((divisor * 4) <= INTERVALS * 3) > return UINT_MAX; > > - thresh = max; > + /* Update the thresholds for the next round. */ > + if (avg - min > max - avg) > + min_thresh = min; > + else > + max_thresh = max; > + > goto again; > } Reviewed-by: Christian Loehle <christian.loehle@arm.com>
--- a/drivers/cpuidle/governors/menu.c +++ b/drivers/cpuidle/governors/menu.c @@ -116,30 +116,37 @@ */ static unsigned int get_typical_interval(struct menu_device *data) { - unsigned int max, divisor, thresh = UINT_MAX; + s64 value, min_thresh = -1, max_thresh = UINT_MAX; + unsigned int max, min, divisor; u64 avg, variance, avg_sq; int i; again: /* Compute the average and variance of past intervals. */ max = 0; + min = UINT_MAX; avg = 0; variance = 0; divisor = 0; for (i = 0; i < INTERVALS; i++) { - unsigned int value = data->intervals[i]; - - /* Discard data points above or at the threshold. */ - if (value >= thresh) + value = data->intervals[i]; + /* + * Discard the samples outside the interval between the min and + * max thresholds. + */ + if (value <= min_thresh || value >= max_thresh) continue; divisor++; avg += value; - variance += (u64)value * value; + variance += value * value; if (value > max) max = value; + + if (value < min) + min = value; } if (!max) @@ -175,10 +182,10 @@ } /* - * If we have outliers to the upside in our distribution, discard - * those by setting the threshold to exclude these outliers, then + * If there are outliers, discard them by setting thresholds to exclude + * data points at a large enough distance from the average, then * calculate the average and standard deviation again. Once we get - * down to the bottom 3/4 of our samples, stop excluding samples. + * down to the last 3/4 of our samples, stop excluding samples. * * This can deal with workloads that have long pauses interspersed * with sporadic activity with a bunch of short pauses. @@ -186,7 +193,12 @@ if ((divisor * 4) <= INTERVALS * 3) return UINT_MAX; - thresh = max; + /* Update the thresholds for the next round. */ + if (avg - min > max - avg) + min_thresh = min; + else + max_thresh = max; + goto again; }