Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753399AbcD1R05 (ORCPT ); Thu, 28 Apr 2016 13:26:57 -0400 Received: from mail-pf0-f176.google.com ([209.85.192.176]:35402 "EHLO mail-pf0-f176.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752560AbcD1R04 (ORCPT ); Thu, 28 Apr 2016 13:26:56 -0400 From: bsegall@google.com To: Yuyang Du Cc: peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org, pjt@google.com, morten.rasmussen@arm.com, vincent.guittot@linaro.org, dietmar.eggemann@arm.com, juri.lelli@arm.com Subject: Re: [PATCH 1/6] sched/fair: Optimize sum computation with a lookup table References: <1461812173-32439-1-git-send-email-yuyang.du@intel.com> <1461812173-32439-2-git-send-email-yuyang.du@intel.com> Date: Thu, 28 Apr 2016 10:26:53 -0700 In-Reply-To: <1461812173-32439-2-git-send-email-yuyang.du@intel.com> (Yuyang Du's message of "Thu, 28 Apr 2016 10:56:08 +0800") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1791 Lines: 56 Yuyang Du writes: > __compute_runnable_contrib() uses a loop to compute sum, whereas a > table lookup can do it faster in a constant time. > > The program to generate the constants is located at: > Documentation/scheduler/sched-avg.txt > > Signed-off-by: Yuyang Du > Reviewed-by: Morten Rasmussen > Acked-by: Vincent Guittot > --- > kernel/sched/fair.c | 20 ++++++++++++-------- > 1 file changed, 12 insertions(+), 8 deletions(-) > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c > index b8cc1c3..6e0eec0 100644 > --- 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 */ Just write / LOAD_AVG_PERIOD > + n %= LOAD_AVG_PERIOD; > contrib = decay_load(contrib, n); > return contrib + runnable_avg_yN_sum[n]; > }