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

[Peter Zijlstra]

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