linux-kernel - Re: [PATCH v2 1/3] lib: find_*

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:	1 Feb 2015 22:17:14 -0500
From:	"George Spelvin" <linux@...izon.com>
To:	akpm@...ux-foundation.org, chris@...is-wilson.co.uk,
	davem@...emloft.net, dborkman@...hat.com,
	hannes@...essinduktion.org, klimov.linux@...il.com,
	laijs@...fujitsu.com, linux@...izon.com, msalter@...hat.com,
	takahiro.akashi@...aro.org, tgraf@...g.ch,
	valentinrothberg@...il.com, yury.norov@...il.com
Cc:	linux-kernel@...r.kernel.org, y.norov@...sung.com
Subject: Re: [PATCH v2 1/3] lib: find_*_bit reimplementation

Yury Norov <y.norov@...sung.com> wrote:
> New implementations takes less space in source file (see diffstat)
> and in object. For me it's 710 vs 453 bytes of text.
> 
> Patch was boot-tested on x86_64 and MIPS (big-endian) machines.
> Performance tests were ran on userspace with code like this:
> 
>	/* addr[] is filled from /dev/urandom */
>	start = clock();
>	while (ret < nbits)
>		ret = find_next_bit(addr, nbits, ret + 1);
>
>	end = clock();
>	printf("%ld\t", (unsigned long) end - start);

> On Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz rezults are next:
> (for find_next_bit, nbits is 8M, for find_first_bit - 80K)
>
>	find_next_bit:		find_first_bit:
>	new	current		new	current
>	26932	43151		14777	14925
>	26947	43182		14521	15423

I'll look at this more carefully, but one immediate thought is that this
is an unrealistic benchmark.  It will amost never need to look at more
than one word of the array, but real arrays have long runs of zero
bits to skip over.

So the code size is appreciated, but the time benefits may be the result
of you optimizing for the wrong thing.

I'd try filling the array with mostly-identical bits, flipping with odds
of 1/256 or so.

For full generality, I'd test different 1->0 and 0->1 transition
probabilities.  (But powers of two are probably enough for benchmarking.)

--
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/