Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753135AbcD1KiU (ORCPT ); Thu, 28 Apr 2016 06:38:20 -0400 Received: from mga02.intel.com ([134.134.136.20]:49305 "EHLO mga02.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753087AbcD1KiR (ORCPT ); Thu, 28 Apr 2016 06:38:17 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.24,546,1455004800"; d="scan'208";a="964534334" 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/6] sched/fair: Optimize sum computation with a lookup table Date: Thu, 28 Apr 2016 10:56:08 +0800 Message-Id: <1461812173-32439-2-git-send-email-yuyang.du@intel.com> X-Mailer: git-send-email 1.7.9.5 In-Reply-To: <1461812173-32439-1-git-send-email-yuyang.du@intel.com> References: <1461812173-32439-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: 1632 Lines: 53 __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 */ + n %= LOAD_AVG_PERIOD; contrib = decay_load(contrib, n); return contrib + runnable_avg_yN_sum[n]; } -- 1.7.9.5