From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754196AbcDKXHb (ORCPT ); Mon, 11 Apr 2016 19:07:31 -0400 Received: from smtprelay0082.hostedemail.com ([216.40.44.82]:59587 "EHLO smtprelay.hostedemail.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1751427AbcDKXHa (ORCPT ); Mon, 11 Apr 2016 19:07:30 -0400 X-Session-Marker: 6A6F6540706572636865732E636F6D X-Spam-Summary: 2,0,0,,d41d8cd98f00b204,joe@perches.com,:::::::::::::::::::,RULES_HIT:41:355:379:541:599:960:973:982:988:989:1260:1277:1311:1313:1314:1345:1359:1373:1437:1461:1515:1516:1518:1534:1541:1593:1594:1711:1730:1747:1777:1792:2393:2559:2562:2828:3138:3139:3140:3141:3142:3353:3865:3867:3868:3870:3872:4321:4362:5007:7904:10004:10400:10848:11026:11232:11473:11658:11783:11914:12043:12048:12438:12517:12519:12555:12679:12740:13069:13161:13229:13311:13357:13439:13894:14659:21080:21324:30029:30054:30064:30091,0,RBL:none,CacheIP:none,Bayesian:0.5,0.5,0.5,Netcheck:none,DomainCache:0,MSF:not bulk,SPF:fn,MSBL:0,DNSBL:none,Custom_rules:0:0:0,LFtime:1,LUA_SUMMARY:none X-HE-Tag: skirt94_6e8f0d096e51 X-Filterd-Recvd-Size: 2519 Message-ID: <1460416045.25155.0.camel@perches.com> Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table From: Joe Perches To: Yuyang Du , peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org Cc: bsegall@google.com, pjt@google.com, morten.rasmussen@arm.com, vincent.guittot@linaro.org, dietmar.eggemann@arm.com, juri.lelli@arm.com Date: Mon, 11 Apr 2016 16:07:25 -0700 In-Reply-To: <1460327765-18024-2-git-send-email-yuyang.du@intel.com> References: <1460327765-18024-1-git-send-email-yuyang.du@intel.com> <1460327765-18024-2-git-send-email-yuyang.du@intel.com> Content-Type: text/plain; charset="ISO-8859-1" X-Mailer: Evolution 3.18.5.2-0ubuntu1 Mime-Version: 1.0 Content-Transfer-Encoding: 8bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org A few comments: On Mon, 2016-04-11 at 06:36 +0800, Yuyang Du wrote: > __compute_runnable_contrib() uses a loop to compute sum, whereas a > table loopup can do it faster in a constant time. lookup typo > The following python script can be used to generate the constants: Thanks for including the script. > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c [] > @@ -2603,6 +2603,15 @@ static const u32 runnable_avg_yN_sum[] = { >  }; >   >  /* > + * Precomputed \Sum y^k { 1<=k<=n, where n%32=0). Values are rolled down to > + * lower integers. > + */ > +static const u32 __accumulated_sum_N32[] = { > +     0, 23371, 35056, 40899, 43820, 45281, > + 46011, 46376, 46559, 46650, 46696, 46719, > +}; > + > +/* >   * Approximate: >   *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period) >   */ > @@ -2650,14 +2659,9 @@ static u32 __compute_runnable_contrib(u64 n) >   else if (unlikely(n >= LOAD_AVG_MAX_N)) >   return LOAD_AVG_MAX; >   > - /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */ > - do { > - contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */ > - contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD]; > - > - n -= LOAD_AVG_PERIOD; > - } while (n > LOAD_AVG_PERIOD); > - > + /* Since n < LOAD_AVG_MAX_N, n/LOAD_AVG_PERIOD < 11 */ > + contrib = __accumulated_sum_N32[n>>5]; /* =n/LOAD_AVG_PERIOD */ Perhaps the variable name could be improved and the comment block around the runnable_avg_yN declarations should include this new declaration.