This series adds a test, const-time optimizaton and fixes O(N^2)
complexity problem for the functions. It's based on discussion in
bitmap: optimize bitmap_remap() series [1], but there's much more work
here, so I decided to give it a separete run, and don't name it as v2.

bitmap_remap() API has just one user in generic code, and few more in
drivers, so this may look like an overkill. But the work gives ~10x
better performance for a 1000-bit bitmaps, which is typical for nodemasks
in major distros like Ubuntu.

Anyways, the work is done, so guys please review.

[1] https://lore.kernel.org/lkml/20230815235934.47782-1-yury.norov@gmail.com/T/
Yury Norov (12):
  bitmap: add find_nth_bit_from()
  bitmap: add bitmap_weight_from()
  bitmap: add test for bitmap_remap()
  bitmap: add test for bitmap_bitremap()
  bitmap: update comment for bitmap_{bit,}remap()
  bitmap: add small_cont_nbits() optimization for bitmap_remap()
  bitmap: add small_const_nbits() optimization for bitmap_bitremap()
  bitmap: optiimze bitmap_bitremap()
  bitmap: optimize bitmap_remap() when 'new' is empty map
  bitmap: separate handling of identity and remapping parts in
    bitmap_remap()
  bitmap: defer calculating weight of 'new' in bitmap_remap()
  bitmap: don't count bits from the beginning in bitmap_remap()

 include/linux/bitmap.h | 116 +++++++++++++++++++++++++++++++--
 include/linux/find.h   |  37 +++++++++++
 lib/bitmap.c           | 145 ++++++++++++++++++++---------------------
 lib/find_bit.c         |  29 +++++++++
 lib/test_bitmap.c      | 142 +++++++++++++++++++++++++++++++++++++++-
 5 files changed, 388 insertions(+), 81 deletions(-)

-- 
2.39.2

On 28/08/2023 20.43, Yury Norov wrote:
> This series adds a test, const-time optimizaton and fixes O(N^2)
> complexity problem for the functions. It's based on discussion in
> bitmap: optimize bitmap_remap() series [1], but there's much more work
> here, so I decided to give it a separete run, and don't name it as v2.
> 
> bitmap_remap() API has just one user in generic code, and few more in
> drivers, so this may look like an overkill. But the work gives ~10x
> better performance for a 1000-bit bitmaps, which is typical for nodemasks
> in major distros like Ubuntu.

Can you find just _one_ project on Debian Code Search or elsewhere that
actually uses mbind(2), that could possibly ever trigger the use of that
bitmap_remap stuff? Also, the bitmap may be order 10, but that's just
because the kitchen sink distros are silly, real machines have nowhere
near that number of nodes, so even if mbind is used, the bitmaps
involved will never actually have anything beyond index ~64.

I think this is all total overkill for non-existing problems, and when
it takes me 20 seconds to find the first bug, I really don't think it's
worth the churn. I'm not giving a thorough review on the rest of the
series, nor commenting on followups.

Rasmus

On Tue, Aug 29, 2023 at 09:33:29AM +0200, Rasmus Villemoes wrote:
> On 28/08/2023 20.43, Yury Norov wrote:
> > This series adds a test, const-time optimizaton and fixes O(N^2)
> > complexity problem for the functions. It's based on discussion in
> > bitmap: optimize bitmap_remap() series [1], but there's much more work
> > here, so I decided to give it a separete run, and don't name it as v2.
> > 
> > bitmap_remap() API has just one user in generic code, and few more in
> > drivers, so this may look like an overkill. But the work gives ~10x
> > better performance for a 1000-bit bitmaps, which is typical for nodemasks
> > in major distros like Ubuntu.
> 
> Can you find just _one_ project on Debian Code Search or elsewhere that
> actually uses mbind(2), that could possibly ever trigger the use of that
> bitmap_remap stuff? Also, the bitmap may be order 10, but that's just
> because the kitchen sink distros are silly, real machines have nowhere
> near that number of nodes, so even if mbind is used, the bitmaps
> involved will never actually have anything beyond index ~64.
> 
> I think this is all total overkill for non-existing problems, and when
> it takes me 20 seconds to find the first bug, I really don't think it's
> worth the churn. I'm not giving a thorough review on the rest of the
> series, nor commenting on followups.

I posted one patch to replace these APIs with something else, more particular
for GPIO case(s). Have you chance to look at that? With that taking in, I'm
fully agree on the above statement (as we lose the user of this complicated
thingy which is a niche of the NUMA as you mentioned already).

-- 
With Best Regards,
Andy Shevchenko

On Tue, Aug 29, 2023 at 6:39 AM Andy Shevchenko
<andriy.shevchenko@linux.intel.com> wrote:
>
> On Tue, Aug 29, 2023 at 09:33:29AM +0200, Rasmus Villemoes wrote:
> > On 28/08/2023 20.43, Yury Norov wrote:
> > > This series adds a test, const-time optimizaton and fixes O(N^2)
> > > complexity problem for the functions. It's based on discussion in
> > > bitmap: optimize bitmap_remap() series [1], but there's much more work
> > > here, so I decided to give it a separete run, and don't name it as v2.
> > >
> > > bitmap_remap() API has just one user in generic code, and few more in
> > > drivers, so this may look like an overkill. But the work gives ~10x
> > > better performance for a 1000-bit bitmaps, which is typical for nodemasks
> > > in major distros like Ubuntu.
> >
> > Can you find just _one_ project on Debian Code Search or elsewhere that
> > actually uses mbind(2), that could possibly ever trigger the use of that
> > bitmap_remap stuff? Also, the bitmap may be order 10, but that's just
> > because the kitchen sink distros are silly, real machines have nowhere
> > near that number of nodes, so even if mbind is used, the bitmaps
> > involved will never actually have anything beyond index ~64.
> >
> > I think this is all total overkill for non-existing problems, and when
> > it takes me 20 seconds to find the first bug, I really don't think it's
> > worth the churn. I'm not giving a thorough review on the rest of the
> > series, nor commenting on followups.
>
> I posted one patch to replace these APIs with something else, more particular
> for GPIO case(s). Have you chance to look at that? With that taking in, I'm
> fully agree on the above statement (as we lose the user of this complicated
> thingy which is a niche of the NUMA as you mentioned already).

I saw the code in a comment in some thread but not as a separate patch, and
AFAIK you said it's a work-in-progress.

Sorry if I missed your submission. Can you please send the patch or point me to
the previous submission?

Also, if after your change bitmap_remap would become a NUMA-specific, should
protect it with NUMA guards?

Thanks,
Yury

On Tue, Aug 29, 2023 at 06:50:08AM -0700, Yury Norov wrote:
> On Tue, Aug 29, 2023 at 6:39 AM Andy Shevchenko
> <andriy.shevchenko@linux.intel.com> wrote:
> > On Tue, Aug 29, 2023 at 09:33:29AM +0200, Rasmus Villemoes wrote:

...

> > I posted one patch to replace these APIs with something else, more particular
> > for GPIO case(s). Have you chance to look at that? With that taking in, I'm
> > fully agree on the above statement (as we lose the user of this complicated
> > thingy which is a niche of the NUMA as you mentioned already).
> 
> I saw the code in a comment in some thread but not as a separate patch, and
> AFAIK you said it's a work-in-progress.

The patch itself is self-contained, the only problem it has no users as is.
The work-in-progress for the test cases, but before I continue with that I want
to hear if it's accepted approach.

> Sorry if I missed your submission. Can you please send the patch or point me to
> the previous submission?
> 
> Also, if after your change bitmap_remap would become a NUMA-specific, should
> protect it with NUMA guards?

Rasmus' idea was to move that completely out of the bitmap namespace and scope.

-- 
With Best Regards,
Andy Shevchenko