linux-kernel - Re: [PATCH] lib/int_sqrt.c: Optimize square root function

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]

Date:	Tue, 3 Feb 2015 21:24:56 +0530
From:	Anshul Garg <aksgarg1989@...il.com>
To:	Davidlohr Bueso <dave@...olabs.net>
Cc:	Linus Torvalds <torvalds@...ux-foundation.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	"anshul.g@...sung.com" <anshul.g@...sung.com>
Subject: Re: [PATCH] lib/int_sqrt.c: Optimize square root function

On Tue, Feb 3, 2015 at 10:11 AM, Davidlohr Bueso <dave@...olabs.net> wrote:
> On Mon, 2015-02-02 at 11:13 -0800, Linus Torvalds wrote:
>> IOW, instead of
>>
>>   m = 1UL << (BITS_PER_LONG - 2);
>>
>> perhaps something like
>>
>>    m = 1UL << (BITS_PER_LONG/2- 2);
>>    if (m < x)
>>        m <<= BITS_PER_LONG/2;

On doing this change also extra instruction(shown below) will execute
if x is small(say 10000).

b = y + m;
y >>= 1;
if (x >= b) {

Although i understand your point that we can set value of m according
to range of x.
But in future also range of x can change if apart from memory some
other module starts
using this function more extensively.
So in worst case it will be almost same as current implementation.

So i think its better to scale m according to x by doing
while(m > x)
m>>=2;
rather than according to range of x.

Thanks
Anshul Garg


>>
>> (assuming gcc can change that code into a "cmov") might cut down the
>> "lots of empty loops" case in half for small values of 'x'.
>
> Makes a lot of sense.
>

>> There's probably some other better cheap initial guess value estimator.
>
> Just to get a feeling for the normal arg range in the non-driver parts
> that use this thing:
>
> fs/ceph/super.h:        congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10);
> fs/nfs/write.c: nfs_congestion_kb = (16*int_sqrt(totalram_pages)) << (PAGE_SHIFT-10);
> fs/nfsd/nfscache.c:     limit = (16 * int_sqrt(low_pages)) << (PAGE_SHIFT-10);
> kernel/rcu/tree_plugin.h:               ls = int_sqrt(nr_cpu_ids);
> mm/memcontrol.c:                inactive_ratio = int_sqrt(10 * gb);
> mm/page_alloc.c:                ratio = int_sqrt(10 * gb);
> mm/page_alloc.c:        new_min_free_kbytes = int_sqrt(lowmem_kbytes * 16);
>
> So mostly values that scale according to mem or cpu.
>
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/