Introduce for_each_set_bitrange() and improve bitmap_list_string().
On top of:
https://lore.kernel.org/lkml/YNp3extAkTY8Aocd@yury-ThinkPad/T/ and
https://lore.kernel.org/lkml/YNirnaYw1GSxg1jK@yury-ThinkPad/T/
The full series is here:
https://github.com/norov/linux/commits/bm-f3
Yury Norov (2):
lib: bitmap: add performance test for bitmap_print_to_pagebuf
bitmap: introduce for_each_set_bitrange{_from}
include/linux/find.h | 7 +++++++
lib/test_bitmap.c | 37 +++++++++++++++++++++++++++++++++++++
lib/vsprintf.c | 40 ++++++++++++++++------------------------
3 files changed, 60 insertions(+), 24 deletions(-)
--
2.30.2
bitmap_list_string() is very ineffective when printing bitmaps with long
ranges of set bits because it calls find_next_bit for each bit. We can do
better by detecting ranges of set bits.
This patch introduces a macro for_each_set_bitrange and uses it in
bitmap_list_string(). In my environment, before/after is 943008/31008 ns.
Signed-off-by: Yury Norov <[email protected]>
---
include/linux/find.h | 7 +++++++
lib/vsprintf.c | 40 ++++++++++++++++------------------------
2 files changed, 23 insertions(+), 24 deletions(-)
diff --git a/include/linux/find.h b/include/linux/find.h
index ae9ed52b52b8..1a5ed45dc81b 100644
--- a/include/linux/find.h
+++ b/include/linux/find.h
@@ -301,6 +301,13 @@ unsigned long find_next_bit_le(const void *addr, unsigned
(bit) < (size); \
(bit) = find_next_zero_bit((addr), (size), (bit) + 1))
+#define for_each_set_bitrange(b, e, addr, size) \
+ for ((b) = find_next_bit((addr), (size), 0), \
+ (e) = find_next_zero_bit((addr), (size), (b) + 1); \
+ (b) < (size); \
+ (b) = find_next_bit((addr), (size), (e) + 1), \
+ (e) = find_next_zero_bit((addr), (size), (b) + 1))
+
/**
* for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
* @start: bit offset to start search and to store the current iteration offset
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index 87acf66f0e4c..1ee54dace71e 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -1240,38 +1240,30 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap,
struct printf_spec spec, const char *fmt)
{
int nr_bits = max_t(int, spec.field_width, 0);
- /* current bit is 'cur', most recently seen range is [rbot, rtop] */
- int cur, rbot, rtop;
- bool first = true;
+ char *start = buf;
+ int b, e;
if (check_pointer(&buf, end, bitmap, spec))
return buf;
- rbot = cur = find_first_bit(bitmap, nr_bits);
- while (cur < nr_bits) {
- rtop = cur;
- cur = find_next_bit(bitmap, nr_bits, cur + 1);
- if (cur < nr_bits && cur <= rtop + 1)
- continue;
+ for_each_set_bitrange(b, e, bitmap, nr_bits) {
+ buf = number(buf, end, b, default_dec_spec);
+ if (e == b + 1)
+ goto put_comma;
- if (!first) {
- if (buf < end)
- *buf = ',';
- buf++;
- }
- first = false;
+ if (buf < end)
+ *buf = '-';
- buf = number(buf, end, rbot, default_dec_spec);
- if (rbot < rtop) {
- if (buf < end)
- *buf = '-';
- buf++;
+ buf = number(++buf, end, e - 1, default_dec_spec);
+put_comma:
+ if (buf < end)
+ *buf = ',';
+ buf++;
+ }
- buf = number(buf, end, rtop, default_dec_spec);
- }
+ if (buf > start)
+ buf--;
- rbot = cur;
- }
return buf;
}
--
2.30.2
On Thu, Jul 08, 2021 at 08:45:19PM -0700, Yury Norov wrote:
> bitmap_list_string() is very ineffective when printing bitmaps with long
> ranges of set bits because it calls find_next_bit for each bit. We can do
> better by detecting ranges of set bits.
>
> This patch introduces a macro for_each_set_bitrange and uses it in
> bitmap_list_string(). In my environment, before/after is 943008/31008 ns.
Ah, it seems we already have bitmap_for_each_{set,clear}_region() with
the same functionality. I'll check everything again and submit v2 soon.
On Thu, 8 Jul 2021 20:45:19 -0700
Yury Norov <[email protected]> wrote:
> bitmap_list_string() is very ineffective when printing bitmaps with long
> ranges of set bits because it calls find_next_bit for each bit. We can do
> better by detecting ranges of set bits.
>
> This patch introduces a macro for_each_set_bitrange and uses it in
> bitmap_list_string(). In my environment, before/after is 943008/31008 ns.
>
> Signed-off-by: Yury Norov <[email protected]>
> ---
> include/linux/find.h | 7 +++++++
> lib/vsprintf.c | 40 ++++++++++++++++------------------------
> 2 files changed, 23 insertions(+), 24 deletions(-)
>
> diff --git a/include/linux/find.h b/include/linux/find.h
> index ae9ed52b52b8..1a5ed45dc81b 100644
> --- a/include/linux/find.h
> +++ b/include/linux/find.h
> @@ -301,6 +301,13 @@ unsigned long find_next_bit_le(const void *addr, unsigned
> (bit) < (size); \
> (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
>
> +#define for_each_set_bitrange(b, e, addr, size) \
The above needs a kerneldoc header.
> + for ((b) = find_next_bit((addr), (size), 0), \
> + (e) = find_next_zero_bit((addr), (size), (b) + 1); \
> + (b) < (size); \
> + (b) = find_next_bit((addr), (size), (e) + 1), \
> + (e) = find_next_zero_bit((addr), (size), (b) + 1))
> +
> /**
> * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
> * @start: bit offset to start search and to store the current iteration offset
> diff --git a/lib/vsprintf.c b/lib/vsprintf.c
> index 87acf66f0e4c..1ee54dace71e 100644
> --- a/lib/vsprintf.c
> +++ b/lib/vsprintf.c
> @@ -1240,38 +1240,30 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap,
> struct printf_spec spec, const char *fmt)
> {
> int nr_bits = max_t(int, spec.field_width, 0);
> - /* current bit is 'cur', most recently seen range is [rbot, rtop] */
> - int cur, rbot, rtop;
> - bool first = true;
> + char *start = buf;
> + int b, e;
>
> if (check_pointer(&buf, end, bitmap, spec))
> return buf;
>
> - rbot = cur = find_first_bit(bitmap, nr_bits);
> - while (cur < nr_bits) {
> - rtop = cur;
> - cur = find_next_bit(bitmap, nr_bits, cur + 1);
> - if (cur < nr_bits && cur <= rtop + 1)
> - continue;
> + for_each_set_bitrange(b, e, bitmap, nr_bits) {
> + buf = number(buf, end, b, default_dec_spec);
> + if (e == b + 1)
> + goto put_comma;
Using a goto to skip a few lines instead of just having the reverse
conditional is rather sloppy IMO.
if (e != b + 1) {
if (buf < end)
*buf = '-';
buf++;
buf = number(buf, end, e - 1, default_dec_spec);
}
Is much clearer.
>
> - if (!first) {
> - if (buf < end)
> - *buf = ',';
> - buf++;
> - }
> - first = false;
> + if (buf < end)
> + *buf = '-';
>
> - buf = number(buf, end, rbot, default_dec_spec);
> - if (rbot < rtop) {
> - if (buf < end)
> - *buf = '-';
> - buf++;
> + buf = number(++buf, end, e - 1, default_dec_spec);
> +put_comma:
> + if (buf < end)
> + *buf = ',';
> + buf++;
> + }
>
> - buf = number(buf, end, rtop, default_dec_spec);
> - }
> + if (buf > start)
> + buf--;
If the above is to undo the last comma, please put back the first logic.
-- Steve
>
> - rbot = cur;
> - }
> return buf;
> }
>
On Fri, Jul 09, 2021 at 09:59:50AM -0400, Steven Rostedt wrote:
> On Thu, 8 Jul 2021 20:45:19 -0700
> Yury Norov <[email protected]> wrote:
>
> > bitmap_list_string() is very ineffective when printing bitmaps with long
> > ranges of set bits because it calls find_next_bit for each bit. We can do
> > better by detecting ranges of set bits.
> >
> > This patch introduces a macro for_each_set_bitrange and uses it in
> > bitmap_list_string(). In my environment, before/after is 943008/31008 ns.
> >
> > Signed-off-by: Yury Norov <[email protected]>
> > ---
> > include/linux/find.h | 7 +++++++
> > lib/vsprintf.c | 40 ++++++++++++++++------------------------
> > 2 files changed, 23 insertions(+), 24 deletions(-)
> >
> > diff --git a/include/linux/find.h b/include/linux/find.h
> > index ae9ed52b52b8..1a5ed45dc81b 100644
> > --- a/include/linux/find.h
> > +++ b/include/linux/find.h
> > @@ -301,6 +301,13 @@ unsigned long find_next_bit_le(const void *addr, unsigned
> > (bit) < (size); \
> > (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
> >
> > +#define for_each_set_bitrange(b, e, addr, size) \
>
> The above needs a kerneldoc header.
OK.
>
> > + for ((b) = find_next_bit((addr), (size), 0), \
> > + (e) = find_next_zero_bit((addr), (size), (b) + 1); \
> > + (b) < (size); \
> > + (b) = find_next_bit((addr), (size), (e) + 1), \
> > + (e) = find_next_zero_bit((addr), (size), (b) + 1))
> > +
> > /**
> > * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
> > * @start: bit offset to start search and to store the current iteration offset
> > diff --git a/lib/vsprintf.c b/lib/vsprintf.c
> > index 87acf66f0e4c..1ee54dace71e 100644
> > --- a/lib/vsprintf.c
> > +++ b/lib/vsprintf.c
> > @@ -1240,38 +1240,30 @@ char *bitmap_list_string(char *buf, char *end, unsigned long *bitmap,
> > struct printf_spec spec, const char *fmt)
> > {
> > int nr_bits = max_t(int, spec.field_width, 0);
> > - /* current bit is 'cur', most recently seen range is [rbot, rtop] */
> > - int cur, rbot, rtop;
> > - bool first = true;
> > + char *start = buf;
> > + int b, e;
> >
> > if (check_pointer(&buf, end, bitmap, spec))
> > return buf;
> >
> > - rbot = cur = find_first_bit(bitmap, nr_bits);
> > - while (cur < nr_bits) {
> > - rtop = cur;
> > - cur = find_next_bit(bitmap, nr_bits, cur + 1);
> > - if (cur < nr_bits && cur <= rtop + 1)
> > - continue;
> > + for_each_set_bitrange(b, e, bitmap, nr_bits) {
> > + buf = number(buf, end, b, default_dec_spec);
> > + if (e == b + 1)
> > + goto put_comma;
>
> Using a goto to skip a few lines instead of just having the reverse
> conditional is rather sloppy IMO.
>
> if (e != b + 1) {
> if (buf < end)
> *buf = '-';
> buf++;
> buf = number(buf, end, e - 1, default_dec_spec);
> }
>
> Is much clearer.
I don't think it's clearer, but as you wish.
> >
> > - if (!first) {
> > - if (buf < end)
> > - *buf = ',';
> > - buf++;
> > - }
> > - first = false;
> > + if (buf < end)
> > + *buf = '-';
> >
> > - buf = number(buf, end, rbot, default_dec_spec);
> > - if (rbot < rtop) {
> > - if (buf < end)
> > - *buf = '-';
> > - buf++;
> > + buf = number(++buf, end, e - 1, default_dec_spec);
> > +put_comma:
> > + if (buf < end)
> > + *buf = ',';
> > + buf++;
> > + }
> >
> > - buf = number(buf, end, rtop, default_dec_spec);
> > - }
> > + if (buf > start)
> > + buf--;
>
> If the above is to undo the last comma, please put back the first logic.
>
> -- Steve
You're asking me to move part of the logic inside the loop which generally
should be avoided. Is there any particular reason to do this?
>
> >
> > - rbot = cur;
> > - }
> > return buf;
> > }
> >
On Thu 2021-07-15 08:50:21, Yury Norov wrote:
> On Fri, Jul 09, 2021 at 09:59:50AM -0400, Steven Rostedt wrote:
> > On Thu, 8 Jul 2021 20:45:19 -0700
> > Yury Norov <[email protected]> wrote:
> >
> > > bitmap_list_string() is very ineffective when printing bitmaps with long
> > > ranges of set bits because it calls find_next_bit for each bit. We can do
> > > better by detecting ranges of set bits.
> > > diff --git a/lib/vsprintf.c b/lib/vsprintf.c
> > > index 87acf66f0e4c..1ee54dace71e 100644
> > > --- a/lib/vsprintf.c
> > > +++ b/lib/vsprintf.c
> > >
> > > - buf = number(buf, end, rtop, default_dec_spec);
> > > - }
> > > + if (buf > start)
> > > + buf--;
> >
> > If the above is to undo the last comma, please put back the first logic.
>
> You're asking me to move part of the logic inside the loop which generally
> should be avoided. Is there any particular reason to do this?
vsprintf() should write what is needed and keep the rest of the given
buffer intact. There is even a test for this in the test_printf module.
I think that test_printf does not complain here because only a single
character is used and it is later replaced by the trailing '\0'.
By other words, undoing the last comma does not cause visible problems
in the end. But from vsprintf() point of view, it is a hack that does
not trigger the warning only by chance. And it is better to avoid it.
Best Regards,
Petr
On Fri, Jul 16, 2021 at 03:46:43PM +0200, Petr Mladek wrote:
> On Thu 2021-07-15 08:50:21, Yury Norov wrote:
> > On Fri, Jul 09, 2021 at 09:59:50AM -0400, Steven Rostedt wrote:
> > > On Thu, 8 Jul 2021 20:45:19 -0700
> > > Yury Norov <[email protected]> wrote:
> > >
> > > > bitmap_list_string() is very ineffective when printing bitmaps with long
> > > > ranges of set bits because it calls find_next_bit for each bit. We can do
> > > > better by detecting ranges of set bits.
> > > > diff --git a/lib/vsprintf.c b/lib/vsprintf.c
> > > > index 87acf66f0e4c..1ee54dace71e 100644
> > > > --- a/lib/vsprintf.c
> > > > +++ b/lib/vsprintf.c
> > > >
> > > > - buf = number(buf, end, rtop, default_dec_spec);
> > > > - }
> > > > + if (buf > start)
> > > > + buf--;
> > >
> > > If the above is to undo the last comma, please put back the first logic.
> >
> > You're asking me to move part of the logic inside the loop which generally
> > should be avoided. Is there any particular reason to do this?
>
> vsprintf() should write what is needed and keep the rest of the given
> buffer intact. There is even a test for this in the test_printf module.
>
> I think that test_printf does not complain here because only a single
> character is used and it is later replaced by the trailing '\0'.
>
> By other words, undoing the last comma does not cause visible problems
> in the end. But from vsprintf() point of view, it is a hack that does
> not trigger the warning only by chance. And it is better to avoid it.
>
> Best Regards,
> Petr
Ah, OK. Thanks Petr.