Re: [PATCH v2 1/3] lib: find_*_bit reimplementation

["George Spelvin" <linux@horizon.com>]

Yury Norov <y.norov@samsung.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.)