Messages in this thread | | | Date | 1 Feb 2015 22:17:14 -0500 | From | "George Spelvin" <> | Subject | Re: [PATCH v2 1/3] lib: find_*_bit reimplementation |
| |
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.)
| |