Messages in this thread | | | From | Andy Shevchenko <> | Date | Wed, 24 Aug 2022 12:19:05 +0300 | Subject | Re: [PATCH v2 3/3] lib/find_bit: optimize find_next_bit() functions |
| |
On Wed, Aug 24, 2022 at 4:56 AM Yury Norov <yury.norov@gmail.com> wrote: > > Over the past couple years, the function _find_next_bit() was extended > with parameters that modify its behavior to implement and- zero- and le- > flavors. The parameters are passed at compile time, but current design > prevents a compiler from optimizing out the conditionals. > > As find_next_bit() API grows, I expect that more parameterss will be added.
parameters
> Current designs would require more conditional code in _find_next_bit(), > which would bloat the helper even more and make it barely readable. > > This patch replaces _find_next_bit() with a macro FIND_NEXT_BIT, and adds > a set of wrappers, so that the compile-time optimization becomes possible. > > The common logic is moved to the new macro, and all flavors may be > generated by providing an EXPRESSION macro parameter, like in this example: > > #define FIND_NEXT_BIT(EXPRESSION, size, start) ... > > find_next_xornot_and_bit(addr1, addr2, addr3, size, start) > { > return FIND_NEXT_BIT(addr1[idx] ^ ~addr2[idx] & addr3[idx], size, start); > } > > The EXPRESSION may be of any complexity, as soon as it only refers > the bitmap(s) and an iterator idx.
...
> +#define FIND_NEXT_BIT(EXPRESSION, size, start) \ > +({ \ > + unsigned long mask, idx, tmp, sz = (size), __start = (start); \ > + \ > + if (unlikely(__start >= sz)) \ > + goto out; \ > + \ > + mask = word_op(BITMAP_FIRST_WORD_MASK(__start)); \ > + idx = __start / BITS_PER_LONG; \ > + \ > + for (tmp = (EXPRESSION) & mask; !tmp; tmp = (EXPRESSION)) { \
for (unsigned long tmp ...; But hey, why not loop over idx (which probably should be named as offset) as I proposed in the first patch? You will drop a lot of divisions / multiplications, no?
> + if (idx > sz / BITS_PER_LONG) \ > + goto out; \ > + idx++; \ > + } \ > + \ > + sz = min(idx * BITS_PER_LONG + __ffs(word_op(tmp)), sz); \ > +out: \ > + sz; \ > +})
-- With Best Regards, Andy Shevchenko
| |