Messages in this thread | | | From | Rasmus Villemoes <> | Subject | Re: [PATCH v2 1/3] lib: find_*_bit reimplementation | Date | Thu, 05 Feb 2015 16:01:26 +0100 |
| |
On Wed, Feb 04 2015, Yury <yury.norov@gmail.com> wrote:
> On 02.02.2015 13:43, Rasmus Villemoes wrote: >>> @@ -23,86 +50,22 @@ >>> unsigned long find_next_bit(const unsigned long *addr, unsigned long size, >>> unsigned long offset) >>> { >>> - const unsigned long *p = addr + BITOP_WORD(offset); >>> - unsigned long result = offset & ~(BITS_PER_LONG-1); >>> - unsigned long tmp; >>> - >>> if (offset >= size) >>> return size; >> Why can't this ... >> >> >>> - size -= result; >>> - offset %= BITS_PER_LONG; >>> - if (offset) { >>> - tmp = *(p++); >>> - tmp &= (~0UL << offset); >>> - if (size < BITS_PER_LONG) >>> - goto found_first; >>> - if (tmp) >>> - goto found_middle; >>> - size -= BITS_PER_LONG; >>> - result += BITS_PER_LONG; >>> - } >>> - while (size & ~(BITS_PER_LONG-1)) { >>> - if ((tmp = *(p++))) >>> - goto found_middle; >>> - result += BITS_PER_LONG; >>> - size -= BITS_PER_LONG; >>> - } >>> - if (!size) >>> - return result; >>> - tmp = *p; >>> >>> -found_first: >>> - tmp &= (~0UL >> (BITS_PER_LONG - size)); >>> - if (tmp == 0UL) /* Are any bits set? */ >>> - return result + size; /* Nope. */ >>> -found_middle: >>> - return result + __ffs(tmp); >>> + return min(_find_next_bit(addr, size, offset, 1), size); >> ... and this be part of _find_next_bit? Can find_next_bit not be simply >> 'return _find_next_bit(addr, size, offset, 1);', and similarly for >> find_next_zero_bit? Btw., passing true and false for the boolean >> parameter may be a little clearer. > I moved size checkers out of '_find_next_bit' to let user call it from his code > if he knows for sure that size/offset pair is valid. This may help save a couple > of clocks. I think, I'll walk over the code to find how many such places we have. > If not too much / not in critical paths, checks may be moved into the function.
But _find_next_bit is static, so outsiders can't call it... The branches are easily predicted and hence almost free, so I think it's better to do the code deduplication and move the bounds checking inside _find_next_bit, so that find_next_bit is literally just 'return _find_next_bit(addr, size, offset, 0ul);' and find_next_zero_bit is 'return _find_next_bit(addr, size, offset, ~0ul);'.
Rasmus
| |