Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1376324
| From | Joe Perches <joe@perches.com> |
|---|---|
| Newsgroups | linux.kernel |
| Subject | Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table |
| Date | 2016-04-12 01:10 +0200 |
| Message-ID | <rmT7X-5oR-9@gated-at.bofh.it> (permalink) |
| References | <rmDmx-1gf-3@gated-at.bofh.it> <rmDmy-1gf-15@gated-at.bofh.it> |
| Organization | linux.* mail to news gateway |
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.
Back to linux.kernel | Previous | Next — Previous in thread | Find similar | Unroll thread
[PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Yuyang Du <yuyang.du@intel.com> - 2016-04-11 08:20 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Vincent Guittot <vincent.guittot@linaro.org> - 2016-04-11 11:10 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Juri Lelli <juri.lelli@arm.com> - 2016-04-11 12:50 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Yuyang Du <yuyang.du@intel.com> - 2016-04-12 05:00 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Juri Lelli <juri.lelli@arm.com> - 2016-04-12 12:20 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Yuyang Du <yuyang.du@intel.com> - 2016-04-13 04:00 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Juri Lelli <juri.lelli@arm.com> - 2016-04-13 11:10 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Dietmar Eggemann <dietmar.eggemann@arm.com> - 2016-04-11 19:00 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Joe Perches <joe@perches.com> - 2016-04-12 01:30 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Juri Lelli <juri.lelli@arm.com> - 2016-04-12 14:10 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Yuyang Du <yuyang.du@intel.com> - 2016-04-12 05:00 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Peter Zijlstra <peterz@infradead.org> - 2016-04-12 16:30 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Yuyang Du <yuyang.du@intel.com> - 2016-04-13 04:00 +0200
Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table Joe Perches <joe@perches.com> - 2016-04-12 01:10 +0200
csiph-web