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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20160412101413.GC5609@e106622-lin>
Date:	Tue, 12 Apr 2016 11:14:13 +0100
From:	Juri Lelli <juri.lelli@....com>
To:	Yuyang Du <yuyang.du@...el.com>
Cc:	peterz@...radead.org, mingo@...nel.org,
	linux-kernel@...r.kernel.org, bsegall@...gle.com, pjt@...gle.com,
	morten.rasmussen@....com, vincent.guittot@...aro.org,
	dietmar.eggemann@....com
Subject: 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