Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1375512 > unrolled thread

[PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [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

#1375512 — [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

__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];
 }
-- 
2.1.4

[toc] | [next] | [standalone]

#1375643

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
>

[toc] | [prev] | [next] | [standalone]

#1375678 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

Hi,

On 11/04/16 06: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)
> 

Thanks for the script, really useful. Do you think there is value in
making it general? Like if we want to play with/need changing LOAD_AVG_
PERIOD in the future to something different than 32.

Also, does the following assume LOAD_AVG_PERIOD == 32? And if yes, do
you think there is any value in removing that assumption?

Best,

- Juri

> 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];
>  }
> -- 
> 2.1.4
> 

[toc] | [prev] | [next] | [standalone]

#1376420 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On Mon, Apr 11, 2016 at 11:41:28AM +0100, Juri Lelli wrote:
> Hi,
> 
> On 11/04/16 06: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)
> > 
> 
> Thanks for the script, really useful. Do you think there is value in
> making it general? Like if we want to play with/need changing LOAD_AVG_
> PERIOD in the future to something different than 32.

i think a s/32/xx/ should work.
 
> Also, does the following assume LOAD_AVG_PERIOD == 32? And if yes, do
> you think there is any value in removing that assumption?
 
Like Peter said, we are heavily dependent on it already. Whether a half-life
of 32 periods (or ~32ms) is the best, maybe we can try 16, but definitely not
64. Or whether exponential decay is the best to compute the impact of old
runnable/running times as a pridiction, it is just I can't think of a better
approach yet, and credits to Paul, Ben, et al.

[toc] | [prev] | [next] | [standalone]

#1376626 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On 12/04/16 03:12, Yuyang Du wrote:
> On Mon, Apr 11, 2016 at 11:41:28AM +0100, Juri Lelli wrote:
> > Hi,
> > 
> > On 11/04/16 06: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)
> > > 
> > 
> > Thanks for the script, really useful. Do you think there is value in
> > making it general? Like if we want to play with/need changing LOAD_AVG_
> > PERIOD in the future to something different than 32.
> 
> i think a s/32/xx/ should work.
>  
> > Also, does the following assume LOAD_AVG_PERIOD == 32? And if yes, do
> > you think there is any value in removing that assumption?
>  
> Like Peter said, we are heavily dependent on it already.

But I think the current code should still work if we define LOAD_AVG_
PERIOD as, say, 16 and we use Paul's program to recompute the tables.

My point was about trying to keep everything related to LOAD_AVG_PERIOD
and not start assuming it is 32. I'm not saying your changes assume
that, I was asking if they do.

> Whether a half-life
> of 32 periods (or ~32ms) is the best, maybe we can try 16, but definitely not
> 64. Or whether exponential decay is the best to compute the impact of old
> runnable/running times as a pridiction, it is just I can't think of a better
> approach yet, and credits to Paul, Ben, et al.
> 

That is fine, I think. Another thing is crafting the code around a
particular half-life, IMHO.

Best,

- Juri

[toc] | [prev] | [next] | [standalone]

#1377465 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On Tue, Apr 12, 2016 at 11:14:13AM +0100, Juri Lelli wrote:
> On 12/04/16 03:12, Yuyang Du wrote:
> > On Mon, Apr 11, 2016 at 11:41:28AM +0100, Juri Lelli wrote:
> > > Hi,
> > > 
> > > On 11/04/16 06: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)
> > > > 
> > > 
> > > Thanks for the script, really useful. Do you think there is value in
> > > making it general? Like if we want to play with/need changing LOAD_AVG_
> > > PERIOD in the future to something different than 32.
> > 
> > i think a s/32/xx/ should work.
> >  
> > > Also, does the following assume LOAD_AVG_PERIOD == 32? And if yes, do
> > > you think there is any value in removing that assumption?
> >  
> > Like Peter said, we are heavily dependent on it already.
> 
> But I think the current code should still work if we define LOAD_AVG_
> PERIOD as, say, 16 and we use Paul's program to recompute the tables.
> 
> My point was about trying to keep everything related to LOAD_AVG_PERIOD
> and not start assuming it is 32. I'm not saying your changes assume
> that, I was asking if they do.

Oh, then my changes do not make more or less dependency. The entire avg thing
should only have two seeds (and all others depend on them):

(1) a period is 1024*1024ns
(2) a half-life is 32 periods

I'll check if there is anything hard-coded other than the two.

[toc] | [prev] | [next] | [standalone]

#1377675 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On 13/04/16 02:07, Yuyang Du wrote:
> On Tue, Apr 12, 2016 at 11:14:13AM +0100, Juri Lelli wrote:
> > On 12/04/16 03:12, Yuyang Du wrote:
> > > On Mon, Apr 11, 2016 at 11:41:28AM +0100, Juri Lelli wrote:
> > > > Hi,
> > > > 
> > > > On 11/04/16 06: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)
> > > > > 
> > > > 
> > > > Thanks for the script, really useful. Do you think there is value in
> > > > making it general? Like if we want to play with/need changing LOAD_AVG_
> > > > PERIOD in the future to something different than 32.
> > > 
> > > i think a s/32/xx/ should work.
> > >  
> > > > Also, does the following assume LOAD_AVG_PERIOD == 32? And if yes, do
> > > > you think there is any value in removing that assumption?
> > >  
> > > Like Peter said, we are heavily dependent on it already.
> > 
> > But I think the current code should still work if we define LOAD_AVG_
> > PERIOD as, say, 16 and we use Paul's program to recompute the tables.
> > 
> > My point was about trying to keep everything related to LOAD_AVG_PERIOD
> > and not start assuming it is 32. I'm not saying your changes assume
> > that, I was asking if they do.
> 
> Oh, then my changes do not make more or less dependency. The entire avg thing
> should only have two seeds (and all others depend on them):
> 
> (1) a period is 1024*1024ns

Which I think is fine.

> (2) a half-life is 32 periods
> 

And this is fine as well, but only if we can actually write

 (2) a half-life is LOAD_AVG_PERIOD periods

Best,

- Juri

> I'll check if there is anything hard-coded other than the two.
> 

[toc] | [prev] | [next] | [standalone]

#1376163 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

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();
 }

[...]

[toc] | [prev] | [next] | [standalone]

#1376329 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On Mon, 2016-04-11 at 17:59 +0100, Dietmar Eggemann wrote:
[]
> 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 create a file and put it in tools somewhere.
Maybe tools/sched ?

[toc] | [prev] | [next] | [standalone]

#1376735 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On 11/04/16 16:21, Joe Perches wrote:
> On Mon, 2016-04-11 at 17:59 +0100, Dietmar Eggemann wrote:
> []
> > 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 create a file and put it in tools somewhere.
> Maybe tools/sched ?
> 

+1. And I'd stick with the C program.

Best,

- Juri

[toc] | [prev] | [next] | [standalone]

#1376423 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On Mon, Apr 11, 2016 at 05:59:11PM +0100, Dietmar Eggemann wrote:
> 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
 
I'd prefer not, and recommend switching from the C program for this
kind of job. :)

[toc] | [prev] | [next] | [standalone]

#1376853 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On Tue, Apr 12, 2016 at 03:17:12AM +0800, Yuyang Du wrote:
> On Mon, Apr 11, 2016 at 05:59:11PM +0100, Dietmar Eggemann wrote:
> > 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
>  
> I'd prefer not, and recommend switching from the C program for this
> kind of job. :)

I much prefer C because I don't speak snake or any of the other popular
languages -- mostly because I simply don't use them enough to remember
how they work.

Also, if we're going to edit that program, maybe change it such that at
the end it prints the numbers in a copy/paste-able C form, just for the
lazy amongst us :-)

[toc] | [prev] | [next] | [standalone]

#1377463 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

On Tue, Apr 12, 2016 at 04:19:52PM +0200, Peter Zijlstra wrote:
> On Tue, Apr 12, 2016 at 03:17:12AM +0800, Yuyang Du wrote:
> > On Mon, Apr 11, 2016 at 05:59:11PM +0100, Dietmar Eggemann wrote:
> > > 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
> >  
> > I'd prefer not, and recommend switching from the C program for this
> > kind of job. :)
> 
> I much prefer C because I don't speak snake or any of the other popular
> languages -- mostly because I simply don't use them enough to remember
> how they work.
> 
> Also, if we're going to edit that program, maybe change it such that at
> the end it prints the numbers in a copy/paste-able C form, just for the
> lazy amongst us :-)

Sure thing, :)

[toc] | [prev] | [next] | [standalone]

#1376324 — Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table

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.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web