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

From	Yuyang Du <yuyang.du@intel.com>
Newsgroups	linux.kernel
Subject	Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table
Date	2016-04-13 04:00 +0200
Message-ID	<rnig2-N7-13@gated-at.bofh.it> (permalink)
References	<rmDmx-1gf-3@gated-at.bofh.it> <rmDmy-1gf-15@gated-at.bofh.it> <rmHzQ-4kX-9@gated-at.bofh.it> <rmWIy-8cp-3@gated-at.bofh.it> <rn3Am-5K4-29@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

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.

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