Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753025AbdDJKrd (ORCPT ); Mon, 10 Apr 2017 06:47:33 -0400 Received: from bombadil.infradead.org ([65.50.211.133]:43781 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752343AbdDJKrc (ORCPT ); Mon, 10 Apr 2017 06:47:32 -0400 Date: Mon, 10 Apr 2017 12:47:25 +0200 From: Peter Zijlstra To: Paul Turner Cc: Yuyang Du , Ingo Molnar , LKML , Benjamin Segall , Morten Rasmussen , Vincent Guittot , Dietmar Eggemann , Matt Fleming , Mike Galbraith Subject: Re: [RESEND PATCH 2/2] sched/fair: Optimize __update_sched_avg() Message-ID: <20170410104725.xc2nah4ech5utqb4@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> <20170330141428.deiduft5btwid6ov@hirez.programming.kicks-ass.net> <20170331113855.xyje6u6xqjofkbcu@hirez.programming.kicks-ass.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20170331113855.xyje6u6xqjofkbcu@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: 2285 Lines: 73 On Fri, Mar 31, 2017 at 01:38:55PM +0200, Peter Zijlstra wrote: > So here, @periods == p+1, see also c1. Yes, this is confusing [*]. > [*] hysterically p used to be off by 1, which is where the p+1 came > from, but now periods includes it. I was thinking of doing a patch > correcting all the comments to fully eradicate the whole +1 business. Something like so; which also makes it obvious p == 0 is not 'right'. --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -2777,18 +2777,18 @@ static u32 __accumulate_pelt_segments(u6 u32 c1, c2, c3 = d3; /* y^0 == 1 */ /* - * c1 = d1 y^(p+1) + * c1 = d1 y^p */ c1 = decay_load((u64)d1, periods); /* - * p + * p-1 * c2 = 1024 \Sum y^n * n=1 * * inf inf * = 1024 ( \Sum y^n - \Sum y^n - y^0 ) - * n=0 n=p+1 + * n=0 n=p */ c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024; @@ -2808,15 +2808,15 @@ static u32 __accumulate_pelt_segments(u6 * |<->|<----------------->|<--->| * ... |---x---|------| ... |------|-----x (now) * - * p - * u' = (u + d1) y^(p+1) + 1024 \Sum y^n + d3 y^0 - * n=1 + * p-1 + * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0 + * n=1 * - * = u y^(p+1) + (Step 1) + * = u y^p + (Step 1) * - * p - * d1 y^(p+1) + 1024 \Sum y^n + d3 y^0 (Step 2) - * n=1 + * p-1 + * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2) + * n=1 */ static __always_inline u32 accumulate_sum(u64 delta, int cpu, struct sched_avg *sa, > > I computed all the values vs true value that the old/new computations > > result in, and it's very close. Absolutely it's approximately 2x off > > the previous computation, e.g. if the old value was -15 (relative to > > true value) than the new computation is -30. > > > > This is definitely more than good enough. If we want more precision, > > then the correction factor of: > > +clamp(periods, 0, 45) > > Can you do a patch with coherent comment explaining where that > correction term comes from? ping?