From: Andy Shevchenko <andy.shevchenko@gmail.com>
To: Yury Norov <yury.norov@gmail.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>,
Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
Guenter Roeck <linux@roeck-us.net>,
Dennis Zhou <dennis@kernel.org>,
Russell King <linux@armlinux.org.uk>,
Catalin Marinas <catalin.marinas@arm.com>,
Andy Shevchenko <andriy.shevchenko@linux.intel.com>,
Rasmus Villemoes <linux@rasmusvillemoes.dk>,
Alexey Klimov <aklimov@redhat.com>,
Kees Cook <keescook@chromium.org>,
Andy Whitcroft <apw@canonical.com>
Subject: Re: [PATCH v2 3/3] lib/find_bit: optimize find_next_bit() functions
Date: Wed, 24 Aug 2022 12:19:05 +0300 [thread overview]
Message-ID: <CAHp75Ve4QTSs_mSB7uMqOK4q+A-z-O1tc2k5=2qaRHTdAC3yog@mail.gmail.com> (raw)
In-Reply-To: <20220824012624.2826445-4-yury.norov@gmail.com>
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
next prev parent reply other threads:[~2022-08-24 9:19 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-08-24 1:26 [PATCH v2 0/4] lib: optimize find_bit() functions Yury Norov
2022-08-24 1:26 ` [PATCH v2 1/3] lib/find_bit: introduce FIND_FIRST_BIT() macro Yury Norov
2022-08-24 9:10 ` Andy Shevchenko
2022-08-24 13:19 ` Yury Norov
2022-08-24 14:18 ` David Laight
2022-08-24 17:45 ` Andy Shevchenko
2022-08-24 17:59 ` Linus Torvalds
2022-08-24 1:26 ` [PATCH v2 2/3] lib/find_bit: create find_first_zero_bit_le() Yury Norov
2022-08-24 9:22 ` Andy Shevchenko
2022-08-24 9:24 ` Andy Shevchenko
2022-08-24 13:37 ` Yury Norov
2022-08-24 17:50 ` Andy Shevchenko
2022-08-24 17:58 ` Russell King (Oracle)
2022-08-24 20:03 ` Yury Norov
2022-08-24 18:11 ` Linus Torvalds
2022-08-24 22:09 ` Yury Norov
2022-08-24 1:26 ` [PATCH v2 3/3] lib/find_bit: optimize find_next_bit() functions Yury Norov
2022-08-24 9:19 ` Andy Shevchenko [this message]
2022-08-24 13:53 ` Yury Norov
2022-08-24 17:54 ` Andy Shevchenko
2022-08-24 17:56 ` Andy Shevchenko
2022-08-24 21:27 ` Yury Norov
2022-08-24 9:00 ` [PATCH v2 0/4] lib: optimize find_bit() functions Andy Shevchenko
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAHp75Ve4QTSs_mSB7uMqOK4q+A-z-O1tc2k5=2qaRHTdAC3yog@mail.gmail.com' \
--to=andy.shevchenko@gmail.com \
--cc=aklimov@redhat.com \
--cc=andriy.shevchenko@linux.intel.com \
--cc=apw@canonical.com \
--cc=catalin.marinas@arm.com \
--cc=dennis@kernel.org \
--cc=keescook@chromium.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@armlinux.org.uk \
--cc=linux@rasmusvillemoes.dk \
--cc=linux@roeck-us.net \
--cc=torvalds@linux-foundation.org \
--cc=yury.norov@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).