Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752222AbcDKGSj (ORCPT ); Mon, 11 Apr 2016 02:18:39 -0400 Received: from mga01.intel.com ([192.55.52.88]:10158 "EHLO mga01.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752043AbcDKGSi (ORCPT ); Mon, 11 Apr 2016 02:18:38 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.24,462,1455004800"; d="scan'208";a="929706661" From: Yuyang Du To: 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, Yuyang Du Subject: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Date: Mon, 11 Apr 2016 06:36:02 +0800 Message-Id: <1460327765-18024-2-git-send-email-yuyang.du@intel.com> X-Mailer: git-send-email 1.7.9.5 In-Reply-To: <1460327765-18024-1-git-send-email-yuyang.du@intel.com> References: <1460327765-18024-1-git-send-email-yuyang.du@intel.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1952 Lines: 75 __compute_runnable_contrib() uses a loop to compute sum, whereas a table loopup can do it faster in a constant time. The following python script can be used to generate the constants: print " #: yN_inv yN_sum" print "-----------------------" y = (0.5)**(1/32.0) x = 2**32 xx = 1024 for i in range(0, 32): if i == 0: x = x-1 xx = xx*y else: x = x*y xx = int(xx*y + 1024*y) print "%2d: %#x %8d" % (i, int(x), int(xx)) print " #: sum_N32" print "------------" xxx = xx for i in range(0, 11): if i == 0: xxx = xx else: xxx = xxx/2 + xx print "%2d: %8d" % (i, xxx) Signed-off-by: Yuyang Du Reviewed-by: Morten Rasmussen --- 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 */ + n %= LOAD_AVG_PERIOD; contrib = decay_load(contrib, n); return contrib + runnable_avg_yN_sum[n]; } -- 2.1.4