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: <20160412141952.GF1087@worktop>
Date:	Tue, 12 Apr 2016 16:19:52 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Yuyang Du <yuyang.du@...el.com>
Cc:	Dietmar Eggemann <dietmar.eggemann@....com>, mingo@...nel.org,
	linux-kernel@...r.kernel.org, bsegall@...gle.com, pjt@...gle.com,
	morten.rasmussen@....com, vincent.guittot@...aro.org,
	juri.lelli@....com
Subject: Re: [PATCH 1/4] sched/fair: Optimize sum computation with a lookup
 table

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