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

From	Peter Zijlstra <peterz@infradead.org>
Newsgroups	linux.kernel
Subject	Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup table
Date	2016-04-12 16:30 +0200
Message-ID	<rn7ui-ky-17@gated-at.bofh.it> (permalink)
References	<rmDmx-1gf-3@gated-at.bofh.it> <rmDmy-1gf-15@gated-at.bofh.it> <rmNlU-xK-15@gated-at.bofh.it> <rmWIy-8cp-19@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

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 :-)

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