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

<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>LKML: Christian Loehle: Re: [RFT][PATCH v1 2/5] cpuidle: menu: Use one loop for average and variance computations</title><link href="/css/message.css" rel="stylesheet" type="text/css" /><link href="/css/wrap.css" rel="alternate stylesheet" type="text/css" title="wrap" /><link href="/css/nowrap.css" rel="stylesheet" type="text/css" title="nowrap" /><link href="/favicon.ico" rel="shortcut icon" /><script src="/js/simple-calendar.js" type="text/javascript"></script><script src="/js/styleswitcher.js" type="text/javascript"></script><link rel="alternate" type="application/rss+xml" title="lkml.org : last 100 messages" href="/rss.php" /><link rel="alternate" type="application/rss+xml" title="lkml.org : last messages by Christian Loehle" href="/groupie.php?aid=" /><script> var _paq = window._paq = window._paq || []; /* tracker methods like "setCustomDimension" should be called before "trackPageView" */ _paq.push(["setDoNotTrack", true]); _paq.push(["disableCookies"]); _paq.push(['trackPageView']); _paq.push(['enableLinkTracking']); (function() { var u="//m.lkml.org/"; _paq.push(['setTrackerUrl', u+'matomo.php']); _paq.push(['setSiteId', '1']); var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s); })(); </script></head><body onload="es.jasper.simpleCalendar.init();" itemscope="itemscope" itemtype="http://schema.org/BlogPosting"><table border="0" cellpadding="0" cellspacing="0"><tr><td width="180" align="center"><a href="/"><img style="border:0;width:135px;height:32px" src="/images/toprowlk.gif" alt="lkml.org" /></a></td><td width="32">聽</td><td class="nb"><div><a class="nb" href="/lkml"> [lkml]</a> 聽 <a class="nb" href="/lkml/2025"> [2025]</a> 聽 <a class="nb" href="/lkml/2025/2"> [Feb]</a> 聽 <a class="nb" href="/lkml/2025/2/17"> [17]</a> 聽 <a class="nb" href="/lkml/last100"> [last100]</a> 聽 <a href="/rss.php"><img src="/images/rss-or.gif" border="0" alt="RSS Feed" /></a></div><div>Views: <a href="#" class="nowrap" onclick="setActiveStyleSheet('wrap');return false;">[wrap]</a><a href="#" class="wrap" onclick="setActiveStyleSheet('nowrap');return false;">[no wrap]</a> 聽 <a class="nb" href="/lkml/mheaders/2025/2/17/790" onclick="this.href='/lkml/headers'+'/2025/2/17/790';">[headers]</a>聽 <a href="/lkml/bounce/2025/2/17/790">[forward]</a>聽 </div></td><td width="32">聽</td></tr><tr><td valign="top"><div class="es-jasper-simpleCalendar" baseurl="/lkml/"></div><div class="threadlist">Messages in this thread</div><ul class="threadlist"><li class="root"><a href="/lkml/2025/2/6/927">First message in thread</a></li><li><a href="/lkml/2025/2/6/927">"Rafael J. Wysocki"</a><ul><li><a href="/lkml/2025/2/6/923">"Rafael J. Wysocki"</a><ul><li class="origin"><a href="">Christian Loehle</a></li></ul></li><li><a href="/lkml/2025/2/6/924">"Rafael J. Wysocki"</a><ul><li><a href="/lkml/2025/2/17/866">Christian Loehle</a><ul><li><a href="/lkml/2025/2/17/880">"Rafael J. Wysocki"</a></li></ul></li></ul></li><li><a href="/lkml/2025/2/6/925">"Rafael J. Wysocki"</a><ul><li><a href="/lkml/2025/2/17/853">Christian Loehle</a></li></ul></li><li><a href="/lkml/2025/2/6/926">"Rafael J. Wysocki"</a><ul><li><a href="/lkml/2025/2/17/804">Christian Loehle</a></li></ul></li><li><a href="/lkml/2025/2/6/928">"Rafael J. Wysocki"</a><ul><li><a href="/lkml/2025/2/6/961">Christian Loehle</a></li></ul></li><li><a href="/lkml/2025/2/7/1027">Artem Bityutskiy</a><ul><li><a href="/lkml/2025/2/7/1103">Christian Loehle</a><ul><li><a href="/lkml/2025/2/7/1115">"Rafael J. Wysocki"</a></li></ul></li><li><a href="/lkml/2025/2/7/1157">"Rafael J. Wysocki"</a></li></ul></li><li><a href="/lkml/2025/2/10/922">Christian Loehle</a><ul><li><a href="/lkml/2025/2/10/965">"Rafael J. Wysocki"</a><ul><li><a href="/lkml/2025/2/10/972">Christian Loehle</a></li></ul></li><li><a href="/lkml/2025/2/18/1941">Christian Loehle</a><ul><li><a href="/lkml/2025/2/19/773">"Rafael J. Wysocki"</a></li></ul></li></ul></li><li><a href="/lkml/2025/2/13/1996">"Doug Smythies"</a><ul><li><a href="/lkml/2025/2/14/1548">"Rafael J. Wysocki"</a><ul><li><a href="/lkml/2025/2/16/278">"Doug Smythies"</a></li></ul></li></ul></li><li><a href="/lkml/2025/2/24/221">Aboorva Devarajan</a><ul><li><a href="/lkml/2025/2/24/240">Aboorva Devarajan</a></li><li><a href="/lkml/2025/2/24/1038">"Rafael J. Wysocki"</a></li><li><a href="/lkml/2025/2/26/233">Aboorva Devarajan</a><ul><li><a href="/lkml/2025/2/26/773">Christian Loehle</a></li></ul></li></ul></li></ul></li></ul></td><td width="32" rowspan="2" class="c" valign="top"><img src="/images/icornerl.gif" width="32" height="32" alt="/" /></td><td class="c" rowspan="2" valign="top" style="padding-top: 1em"><table><tr><td><table><tr><td class="lp">Date</td><td class="rp" itemprop="datePublished">Mon, 17 Feb 2025 13:03:01 +0000</td></tr><tr><td class="lp">Subject</td><td class="rp" itemprop="name">Re: [RFT][PATCH v1 2/5] cpuidle: menu: Use one loop for average and variance computations</td></tr><tr><td class="lp">From</td><td class="rp" itemprop="author">Christian Loehle <></td></tr></table></td><td></td></tr></table><pre itemprop="articleBody">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> </pre></td><td width="32" rowspan="2" class="c" valign="top"><img src="/images/icornerr.gif" width="32" height="32" alt="\" /></td></tr><tr><td align="right" valign="bottom"> 聽 </td></tr><tr><td align="right" valign="bottom">聽</td><td class="c" valign="bottom" style="padding-bottom: 0px"><img src="/images/bcornerl.gif" width="32" height="32" alt="\" /></td><td class="c">聽</td><td class="c" valign="bottom" style="padding-bottom: 0px"><img src="/images/bcornerr.gif" width="32" height="32" alt="/" /></td></tr><tr><td align="right" valign="top" colspan="2"> 聽 </td><td class="lm">Last update: 2025-02-17 14:08 聽聽 [W:0.847 / U:4.813 seconds] 漏2003-2020 <a href="http://blog.jasper.es/">Jasper Spaans</a>|hosted at <a href="https://www.digitalocean.com/?refcode=9a8e99d24cf9">Digital Ocean</a> and my Meterkast|<a href="http://blog.jasper.es/categories.html#lkml-ref">Read the blog</a></td><td>聽</td></tr></table><script language="javascript" src="/js/styleswitcher.js" type="text/javascript"></script></body></html>

CINXE.COM

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