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

[Yuyang Du]

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.