MIME-Version: 1.0
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>
From: Vincent Guittot <vincent.guittot@linaro.org>
Date: Mon, 11 Apr 2016 11:08:13 +0200
Message-ID: <CAKfTPtB0Ed1m6qshYv_pM0pANsmXoUzdUQ_XCjPbwG0tCvEwHw@mail.gmail.com>
Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table
To: Yuyang Du <yuyang.du@intel.com>
Cc: Peter Zijlstra <peterz@infradead.org>, Ingo Molnar <mingo@kernel.org>,
        linux-kernel <linux-kernel@vger.kernel.org>,
        Benjamin Segall <bsegall@google.com>, Paul Turner <pjt@google.com>,
        Morten Rasmussen <morten.rasmussen@arm.com>,
        Dietmar Eggemann <dietmar.eggemann@arm.com>,
        Juri Lelli <juri.lelli@arm.com>
Content-Type: text/plain; charset=UTF-8
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 2433
Lines: 80

On 11 April 2016 at 00:36, Yuyang Du <yuyang.du@intel.com> 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)
>
> Signed-off-by: Yuyang Du <yuyang.du@intel.com>
> Reviewed-by: Morten Rasmussen <morten.rasmussen@arm.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..6e0eec0 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,
> +};
> +
> +/*
>   * 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 */
> +       n %= LOAD_AVG_PERIOD;
>         contrib = decay_load(contrib, n);
>         return contrib + runnable_avg_yN_sum[n];
>  }

FWIW, you can add my acked

> --
> 2.1.4
>