Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755794AbcDLC7r (ORCPT ); Mon, 11 Apr 2016 22:59:47 -0400 Received: from mga03.intel.com ([134.134.136.65]:62057 "EHLO mga03.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755738AbcDLC7q (ORCPT ); Mon, 11 Apr 2016 22:59:46 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.24,471,1455004800"; d="scan'208";a="943174454" Date: Tue, 12 Apr 2016 03:17:12 +0800 From: Yuyang Du To: Dietmar Eggemann Cc: peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org, bsegall@google.com, pjt@google.com, morten.rasmussen@arm.com, vincent.guittot@linaro.org, juri.lelli@arm.com Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Message-ID: <20160411191712.GG8697@intel.com> References: <1460327765-18024-1-git-send-email-yuyang.du@intel.com> <1460327765-18024-2-git-send-email-yuyang.du@intel.com> <570BD7DF.6070400@arm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <570BD7DF.6070400@arm.com> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1150 Lines: 39 On Mon, Apr 11, 2016 at 05:59:11PM +0100, Dietmar Eggemann wrote: > On 10/04/16 23:36, Yuyang Du wrote: > > __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) > > > > IMHO, it would be nice to add this to the existing tool from the patch > header of commit 5b51f2f80b3b > ("sched: Make __update_entity_runnable_avg() fast") simply because people > already use this one to tweak their pelt tables. Maybe something like I'd prefer not, and recommend switching from the C program for this kind of job. :)