Re: [PATCH v1 2/5] lib/bitmap: Introduce bitmap_scatter() and bitmap_gather() helpers

[Andy Shevchenko <andriy.shevchenko@xxxxxxxxxxxxxxx>]

On Sun, Oct 01, 2023 at 09:06:24PM -0700, Yury Norov wrote:
> On Wed, Sep 27, 2023 at 03:02:34PM +0300, Andy Shevchenko wrote:

[...]

> > > It looks like those are designed complement to each other. Is that
> > > true? If so, can you make your example showing that
> > >         scatter -> gather -> scatter
> > > would restore the original bitmap?
> > 
> > It looks like you stopped reading documentation somewhere on the middle.
> 
> What a wonderful week of strong statements... Whatever...
> 
> > The two APIs are documented with the same example which makes it clear
> > that they are data-loss transformations.

Oh, should be read as data-lossleess.

> > Do you need something like this to be added (in both documentations):
> > 
> >   The bitmap_scatter(), when executed over the @dst bitmap, will
> >   restore the @src one if the @mask is kept the same, see the example
> >   in the function description.
> > 
> > ?
> > 
> > > If I'm wrong, can you please underline that they are not complement,
> > > and why?
> > 
> > No, you are not.
> 
> I should be confused even more. You're saying that I'm not wrong here, and few
> lines above you're saying it's a data loss...

data-lossless, sorry, I was missing that.

> I don't mind this new 3-liners, but I'd like you to have a well better
> wording and testing around them because those bitmap_scatter/gather are
> all about performance, readability and usability.
> 
> To begin with, the whole name of the series: "get rid of bitmap_remap() and
> bitmap_biremap() uses" is wrong because the functions are still here, and are
> still used.
> 
> Even worse, instead of getting rid of some useless code, you're
> bloating the kernel with something that duplicates existing
> functionality.

Wasn't Rasmus clear about the intention:
1) get rid of active users of bitmap_remap() outside of NUMA;
2) move that APIs to be private for NUMA users exclusively?

Towards that direction is my series.

> But I understand your motivation, and as I already said, I like this
> series in general. So let's please figure out a better wording before
> moving forward?
> 
> Below are some my of thought.
> 
> 1. Stop saying that you're getting rid of something when you're not.
>    I'd suggest something like: "add simple and verbose alternatives to
>    bitmap_remap(), and use them where appropriate".

I'm getting rid of the users of the bitmap_remap() outside of NUMA.
Why should I stop telling that? I think I have to elaborate what
that means.

> 2. Don't blame people considering a parameter named 'mask' as a mask.
>    I mean this sentence: 
> 
>    > You should get the mask meaning. It's not the bit provider, it's a bit
>    > positions provider.
> 
>    If it's a 'bit position provider', please give it a proper name,
>    for example 'pos'. I'd suggest something like:
>         unsigned long bitmap_scatter(unsigned long *dst, unsigned long *pos,

It's not pos in the sense of what pos means. pos means a position of a single
bit, mask is about many bits. And mask meaning is still the same despite how
we call it, it's bit positions provider, i.e. bits that are set in the mask
will be considered to be worked on. It's mask, why should I rename it?

> 3. If you're saying that new API is a simplified replacement for
>    something, I'd like to see the full contract, i.e. explicit list of all
>    simplifications and limitations implied:
>    - val == dst is not handled;
>    - when 'pos' is empty, val is not copied to dst;
>    - new API doesn't wrap around 0, like bitmap_remap() does;
>    - set bits in 'val' are not copied to 'dst' when not in 'pos' (?)'
>    - anything else else?

I see, I should have not used word "simplification" at all.
I will reword to not mention bitmap_remap() _at all_.

> 4. Similarly to previous item, I'd like to have explicit understanding
>    and examples where and how bitmap_remap may be replaced. You're
>    only saying that it is possible when either 'new' or 'old' are
>    dense. Is that the only case? Can you add a test that explicitly
>    checks that bitmap_remap and bitmap_scatter/gather produce the same
>    output. Something like this:
>         bitmap_remap(dst1, val, dense_map, pos, nbits);
>         bitmap_scatter(dst2, val, pos, nbits);
>         check_eq_bitmap(dst1, dst2, nbits);

No, I won't do that. This is out of the scope as see comment on 3. above.

> 5. Can you add a picture like this to explain the algorithm even more:
> 
>         mask:    ...v..vv..v...vv
>         bits:    0000001100000010
>         1.          ^  ^^  ^    0
>         2.          |  ||  |   10
>         3.          |  ||  +> 010
>         4.          |  |+--> 1010
>         5.          |  +--> 11010
>         6.          +----> 011010
>         gather:  ..........011010

Why? Is it so complicated?

> 5. Regarding my confusion, I had to draw the picture above to realise
>    how it's possible that scatter/gather are inverse and data-loss
>    (i.e. not inverse) at the same time. Can you explain it with a
>    wording like this: "For bits selected by 'pos' bitmap, gathering a
>    'val' bitmap with the following scattering restores the original map.
>    All other bits values are lost and replaced with zeros." Similarly
>    for gathering. And please add a test case.

Let's not make a big deal out of a small typo. I admit that it confused people,
but that was neither in the documentation, nor in the code, just in our
discussion.

> 6. Regarding performance. I think it's wrong to say that that your
>    code is better optimized then some other, and then ask your
>    reviewers to figure out how to measure the difference. If you make
>    such statement, you should already have some test or real-life
>    measurement.

Same as for 4. above. I drop the comparison and mentioning of bitmap_remap().
It was a big mistake by me to even mentioned that.

>    However, if you ask me, I can suggest you to pull this patch:
>    https://lore.kernel.org/lkml/20230828184353.5145-4-yury.norov@xxxxxxxxx/
> 
>    and modify/extend it in a way that both bitmap_remap and
>    bitmap_scatter/gather take the same 'val' and 'pos' bitmaps,
>    produce the same output, and then see which code is faster.
> 
>    Worth to mention that since all current users of your API are working
>    on 64-bit maps, performance is doubty an issue. So you can drop the
>    'optimization' part of your wording, and don't add performance test.

-- 
With Best Regards,
Andy Shevchenko