Message-ID: <1460416045.25155.0.camel@perches.com>
Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup
 table
From: Joe Perches <joe@perches.com>
To: Yuyang Du <yuyang.du@intel.com>, 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,
        juri.lelli@arm.com
Date: Mon, 11 Apr 2016 16:07:25 -0700
In-Reply-To: <1460327765-18024-2-git-send-email-yuyang.du@intel.com>
References: <1460327765-18024-1-git-send-email-yuyang.du@intel.com>
	 <1460327765-18024-2-git-send-email-yuyang.du@intel.com>
Content-Type: text/plain; charset="ISO-8859-1"
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 1475
Lines: 47

A few comments:

On Mon, 2016-04-11 at 06:36 +0800, Yuyang Du wrote:
> __compute_runnable_contrib() uses a loop to compute sum, whereas a
> table loopup can do it faster in a constant time.

lookup typo

> The following python script can be used to generate the constants:

Thanks for including the script.
> diff --git 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>>5]; /* =n/LOAD_AVG_PERIOD */

Perhaps the variable name could be improved and
the comment block around the runnable_avg_yN
declarations should include this new declaration.