linux-kernel - Re: [PATCH] sched/fair: Optimize sum computation with a lookup table

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20160408113017.GF18516@e105550-lin.cambridge.arm.com>
Date:	Fri, 8 Apr 2016 12:30:17 +0100
From:	Morten Rasmussen <morten.rasmussen@....com>
To:	Yuyang Du <yuyang.du@...el.com>
Cc:	peterz@...radead.org, mingo@...nel.org,
	linux-kernel@...r.kernel.org, bsegall@...gle.com, pjt@...gle.com,
	vincent.guittot@...aro.org, dietmar.eggemann@....com
Subject: Re: [PATCH] sched/fair: Optimize sum computation with a lookup table

On Fri, Apr 08, 2016 at 10:07:20AM +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.
> 
> Signed-off-by: Yuyang Du <yuyang.du@...el.com>
> ---
>  kernel/sched/fair.c |   20 ++++++++++++--------
>  1 file changed, 12 insertions(+), 8 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index b8cc1c3..32bc4ef 100644
> --- 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,
> +};

Could we come up with a name that better indicates that there is
relation between this new table and runnable_avg_yN_sum[]?
runnable_avg_N32_sum[]?

> +
> +/*
>   * 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/LOAD_AVG_PERIOD];
> +	n %= LOAD_AVG_PERIOD;
>  	contrib = decay_load(contrib, n);
>  	return contrib + runnable_avg_yN_sum[n];
>  }

Looks okay to me, but as PeterZ already said, it would be good to have
the code to compute that values.

With that, feel free to put my acked/reviewed-by on it if you like.