linux-kernel - Re: [PATCH] Optimize int_sqrt for small values for faster idle

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: <56ADB774.8080708@gmail.com>
Date:	Sun, 31 Jan 2016 15:27:48 +0800
From:	Thomas Rohwer <tr@...er.de>
To:	Andi Kleen <andi@...stfloor.org>, akpm@...ux-foundation.org
Cc:	linux-kernel@...r.kernel.org, davidlohr.bueso@...com,
	rafael.j.wysocki@...el.com, lenb@...nel.org,
	Andi Kleen <ak@...ux.intel.com>
Subject: Re: [PATCH] Optimize int_sqrt for small values for faster idle

Hello,

 > -	m = 1UL << (BITS_PER_LONG - 2);
 > +	if (x <= 0xffff) {
 > +		if (m <= 0xff)
 > +			m = 1UL << (8 - 2);
 > +		else
 > +			m = 1UL << (16 - 2);
 > +	} else if (x <= 0xffffffff)
 > +		m = 1UL << (32 - 2);
 > +	else
 > +		m = 1UL << (BITS_PER_LONG - 2);
 >   	while (m != 0) {
 >   		b = y + m;
 >   		y >>= 1;
 >

I think, m can be initialized with

1 << (greatest multiple of 2 less than or equal to (position of most significant bit of x))

i.e. 1 << ((position of most significant bit of x) & 62)

without changing the outcome of the original algorithm (as long as x<m the loop does just m >>= 2).

I believe, that for (position of most significant bit of x) there is an efficient macro, and
some processors directly have an instruction for it. So this would probably be faster than your suggestion
for an initial starting value and give an even better starting value (cutting in some cases further on the number of
while loop interations).

If one just wants to achieve a result with a certain relative error in terms of the fraction of the input, one can
probably only look at the most significant bit and a few following bits of x.

Sincerely,

Thomas