From patchwork Mon Apr 11 16:59:11 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dietmar Eggemann X-Patchwork-Id: 65554 Delivered-To: patch@linaro.org Received: by 10.140.93.198 with SMTP id d64csp1466415qge; Mon, 11 Apr 2016 09:59:18 -0700 (PDT) X-Received: by 10.98.40.200 with SMTP id o191mr34259807pfo.83.1460393958733; Mon, 11 Apr 2016 09:59:18 -0700 (PDT) Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id f13si4563492pap.154.2016.04.11.09.59.18; Mon, 11 Apr 2016 09:59:18 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753309AbcDKQ7Q (ORCPT + 29 others); Mon, 11 Apr 2016 12:59:16 -0400 Received: from foss.arm.com ([217.140.101.70]:51084 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750884AbcDKQ7P (ORCPT ); Mon, 11 Apr 2016 12:59:15 -0400 Received: from usa-sjc-imap-foss1.foss.arm.com (unknown [10.72.51.249]) by usa-sjc-mx-foss1.foss.arm.com (Postfix) with ESMTP id C452B3C; Mon, 11 Apr 2016 09:58:01 -0700 (PDT) Received: from [10.1.207.26] (e107985-lin.cambridge.arm.com [10.1.207.26]) by usa-sjc-imap-foss1.foss.arm.com (Postfix) with ESMTPA id 3F4F13F25F; Mon, 11 Apr 2016 09:59:13 -0700 (PDT) Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table To: Yuyang Du , peterz@infradead.org, mingo@kernel.org, linux-kernel@vger.kernel.org References: <1460327765-18024-1-git-send-email-yuyang.du@intel.com> <1460327765-18024-2-git-send-email-yuyang.du@intel.com> Cc: bsegall@google.com, pjt@google.com, morten.rasmussen@arm.com, vincent.guittot@linaro.org, juri.lelli@arm.com From: Dietmar Eggemann Message-ID: <570BD7DF.6070400@arm.com> Date: Mon, 11 Apr 2016 17:59:11 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.6.0 MIME-Version: 1.0 In-Reply-To: <1460327765-18024-2-git-send-email-yuyang.du@intel.com> Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 [...] diff --git a/pelt.c b/pelt.c index 63e32d1d18b0..b36194e8bb9c 100644 --- a/pelt.c +++ b/pelt.c @@ -6,6 +6,8 @@ const long WMULT_CONST = ((1UL << N) - 1); double y; +int ld_avg_max_n; +double sum_fl_n; long runnable_avg_yN_inv[N]; void calc_mult_inv() { @@ -42,6 +44,7 @@ void calc_yn_sum(int n) printf("%2d: %8.0f %8.0f %8.0f\n", i, sum, sum_fl, sum_fl - sum); } + sum_fl_n = sum_fl; printf("\n"); } @@ -55,14 +58,29 @@ void calc_conv(long n) { n = mult_inv(n, 1) + 1024; i++; } while (n != old_n); + ld_avg_max_n = i - 1; printf("%d> %ld\n", i - 1, n); printf("\n"); } +void calc_acc_sum() { + int i = 1; + double sum = sum_fl_n; + int periods = ld_avg_max_n/N + 1; + + printf("sum acc\n"); + + do { + printf("%2d: %8.0f\n", i, sum); + sum = floor(sum/2 + sum_fl_n); + } while (++i <= periods); +} + void main() { y = pow(0.5, 1/(double)N); calc_mult_inv(); calc_conv(1024); calc_yn_sum(N); + calc_acc_sum(); }