Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1758031AbcDHJt7 (ORCPT ); Fri, 8 Apr 2016 05:49:59 -0400 Received: from mga14.intel.com ([192.55.52.115]:25134 "EHLO mga14.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753088AbcDHJt6 (ORCPT ); Fri, 8 Apr 2016 05:49:58 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.24,449,1455004800"; d="scan'208";a="682915268" 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, Yuyang Du Subject: [PATCH] sched/fair: Optimize sum computation with a lookup table Date: Fri, 8 Apr 2016 10:07:20 +0800 Message-Id: <1460081240-8074-1-git-send-email-yuyang.du@intel.com> X-Mailer: git-send-email 1.7.9.5 Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1416 Lines: 48 __compute_runnable_contrib() uses a loop to compute sum, whereas a table loopup can do it faster in a constant time. Signed-off-by: Yuyang Du --- 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..32bc4ef 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/LOAD_AVG_PERIOD]; + n %= LOAD_AVG_PERIOD; contrib = decay_load(contrib, n); return contrib + runnable_avg_yN_sum[n]; } -- 1.7.9.5