Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933744AbdC3OOn (ORCPT ); Thu, 30 Mar 2017 10:14:43 -0400 Received: from merlin.infradead.org ([205.233.59.134]:59568 "EHLO merlin.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933107AbdC3OOm (ORCPT ); Thu, 30 Mar 2017 10:14:42 -0400 Date: Thu, 30 Mar 2017 16:14:28 +0200 From: Peter Zijlstra To: Paul Turner Cc: Yuyang Du , Ingo Molnar , LKML , Benjamin Segall , Morten Rasmussen , Vincent Guittot , Dietmar Eggemann , Matt Fleming , umgwanakikbuti@gmail.com Subject: Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Message-ID: <20170330141428.deiduft5btwid6ov@hirez.programming.kicks-ass.net> References: <1486935863-25251-1-git-send-email-yuyang.du@intel.com> <1486935863-25251-3-git-send-email-yuyang.du@intel.com> <20170328144625.GX3093@worktop> <20170329000442.GC2459@ydu19desktop> <20170329104126.lg6ismevfbqywpcj@hirez.programming.kicks-ass.net> <20170330121658.6mo7datma4ssw7st@hirez.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170330121658.6mo7datma4ssw7st@hirez.programming.kicks-ass.net> User-Agent: NeoMutt/20170113 (1.7.2) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 4682 Lines: 160 On Thu, Mar 30, 2017 at 02:16:58PM +0200, Peter Zijlstra wrote: > On Thu, Mar 30, 2017 at 04:21:08AM -0700, Paul Turner wrote: > > > + > > > + if (unlikely(periods >= LOAD_AVG_MAX_N)) > > > return LOAD_AVG_MAX; > > > > Is this correct in the iterated periods > LOAD_AVG_MAX_N case? > > I don't think the decay above is guaranteed to return these to zero. > > Ah! > > Indeed, so decay_load() needs LOAD_AVG_PERIOD * 63 before it truncates > to 0, because every LOAD_AVG_PERIOD we half the value; loose 1 bit; so > 63 of those and we're 0. > > But __accumulate_sum() OTOH returns LOAD_AVG_MAX after only > LOAD_AVG_MAX_N, which < LOAD_AVG_PERIOD * 63. > > So yes, combined we exceed LOAD_AVG_MAX, which is bad. Let me think what > to do about that. So at the very least it should be decay_load(LOAD_AVG_MAX, 1) (aka LOAD_AVG_MAX - 1024), but that still doesn't account for the !0 decay_load() of the first segment. I'm thinking that we can compute the middle segment, by taking the max value and chopping off the ends, like: p c2 = 1024 \Sum y^n n=1 inf inf = 1024 ( \Sum y^n - \Sum y^n - y^0 ) n=0 n=p Which gives something like the below.. Or am I completely off my rocker? --- kernel/sched/fair.c | 70 ++++++++++++++--------------------------------------- 1 file changed, 18 insertions(+), 52 deletions(-) diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 76f67b3e34d6..4f17ec0a378a 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2744,26 +2744,6 @@ static const u32 runnable_avg_yN_inv[] = { }; /* - * Precomputed \Sum y^k { 1<=k<=n }. These are floor(true_value) to prevent - * over-estimates when re-combining. - */ -static const u32 runnable_avg_yN_sum[] = { - 0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103, - 9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082, - 17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371, -}; - -/* - * Precomputed \Sum y^k { 1<=k<=n, where n%32=0). Values are rolled down to - * lower integers. See Documentation/scheduler/sched-avg.txt how these - * were generated: - */ -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) */ @@ -2795,40 +2775,25 @@ static u64 decay_load(u64 val, u64 n) return val; } -static u32 __accumulate_sum(u64 periods, u32 period_contrib, u32 remainder) +static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) { - u32 c1, c2, c3 = remainder; /* y^0 == 1 */ - - if (!periods) - return remainder - period_contrib; - - if (unlikely(periods >= LOAD_AVG_MAX_N)) - return LOAD_AVG_MAX; + u32 c1, c2, c3 = d3; /* y^0 == 1 */ /* * c1 = d1 y^(p+1) */ - c1 = decay_load((u64)(1024 - period_contrib), periods); + c1 = decay_load((u64)d1, periods); - periods -= 1; /* - * For updates fully spanning n periods, the contribution to runnable - * average will be: + * p + * c2 = 1024 \Sum y^n + * n=1 * - * c2 = 1024 \Sum y^n - * - * We can compute this reasonably efficiently by combining: - * - * y^PERIOD = 1/2 with precomputed 1024 \Sum y^n {for: n < PERIOD} + * inf inf + * = 1024 ( \Sum y^n - \Sum y^n - y^0 ) + * n=0 n=p+1 */ - if (likely(periods <= LOAD_AVG_PERIOD)) { - c2 = runnable_avg_yN_sum[periods]; - } else { - c2 = __accumulated_sum_N32[periods/LOAD_AVG_PERIOD]; - periods %= LOAD_AVG_PERIOD; - c2 = decay_load(c2, periods); - c2 += runnable_avg_yN_sum[periods]; - } + c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024; return c1 + c2 + c3; } @@ -2861,8 +2826,8 @@ accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, unsigned long weight, int running, struct cfs_rq *cfs_rq) { unsigned long scale_freq, scale_cpu; + u32 contrib = delta; u64 periods; - u32 contrib; scale_freq = arch_scale_freq_capacity(NULL, cpu); scale_cpu = arch_scale_cpu_capacity(NULL, cpu); @@ -2880,13 +2845,14 @@ accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, decay_load(cfs_rq->runnable_load_sum, periods); } sa->util_sum = decay_load((u64)(sa->util_sum), periods); - } - /* - * Step 2 - */ - delta %= 1024; - contrib = __accumulate_sum(periods, sa->period_contrib, delta); + /* + * Step 2 + */ + delta %= 1024; + contrib = __accumulate_pelt_segments(periods, + 1024 - sa->period_contrib, delta); + } sa->period_contrib = delta; contrib = cap_scale(contrib, scale_freq);