Обсуждение: Strange Bitmapset manipulation in DiscreteKnapsack()

While working on [1], I noticed some strange code in
DiscreteKnapsack() which seems to be aiming to copy the Bitmapset.

It's not that obvious at a casual glance, but:

sets[j] = bms_del_members(sets[j], sets[j]);

this is aiming to zero all the words in the set by passing the same
set in both parameters.

Now that 00b41463c changed Bitmapset to have NULL be the only valid
representation of an empty set, this code no longer makes sense.  We
may as well just bms_free() the original set and bms_copy() in the new
set as the bms_del_members() call will always pfree the set anyway.

I've done that in the attached.

I did consider if we might want bms_merge_members() or
bms_exchange_members() or some other function suitably named function
to perform a del/add operation, but given the lack of complaints about
any performance regressions here, I think it's not worthwhile.

The code could also be adjusted to:

sets[j] = bms_add_members(sets[j], sets[ow]);
sets[j] = bms_del_members(sets[j], sets[j]);
sets[j] = bms_add_members(sets[j], sets[ow]); // re-add any deletions

so that the set never becomes fully empty... but ... that's pretty horrid.

00b41463c is in PG16, but I'm not proposing to backpatch this.  The
misleading comment does not seem critical enough and the resulting
behaviour isn't changing, just the performance characteristics.

Unless there's some objection, I plan to push this in the next day or two.

David

[1] https://postgr.es/m/CAApHDvoXPoaDYEjMj9e1ihZZZynCtGqdAppWgPZMaMQ222NAkw@mail.gmail.com

On Tue, 16 Jan 2024 at 16:32, David Rowley <dgrowleyml@gmail.com> wrote:
>
> While working on [1], I noticed some strange code in
> DiscreteKnapsack() which seems to be aiming to copy the Bitmapset.
>
> It's not that obvious at a casual glance, but:
>
> sets[j] = bms_del_members(sets[j], sets[j]);
>
> this is aiming to zero all the words in the set by passing the same
> set in both parameters.
>
> Now that 00b41463c changed Bitmapset to have NULL be the only valid
> representation of an empty set, this code no longer makes sense.  We
> may as well just bms_free() the original set and bms_copy() in the new
> set as the bms_del_members() call will always pfree the set anyway.
>
> I've done that in the attached.
>
> I did consider if we might want bms_merge_members() or
> bms_exchange_members() or some other function suitably named function
> to perform a del/add operation, but given the lack of complaints about
> any performance regressions here, I think it's not worthwhile.

After looking at this again and reading more code, I see that
DiscreteKnapsack() goes to some efforts to minimise memory
allocations.

The functions's header comment mentions "The bitmapsets are all
pre-initialized with an unused high bit so that memory allocation is
done only once.".

I tried adding some debugging output to track how many additional
allocations we're now causing as a result of 00b41463c.  Previously
there'd have just been max_weight allocations, but now there's those
plus the number that's mentioned for "frees" below.

NOTICE:  DiscreteKnapsack: frees = 373, max_weight = 140, extra = 266.43%
NOTICE:  DiscreteKnapsack: frees = 373, max_weight = 140, extra = 266.43%
NOTICE:  DiscreteKnapsack: frees = 267, max_weight = 100, extra = 267.00%
NOTICE:  DiscreteKnapsack: frees = 267, max_weight = 100, extra = 267.00%
NOTICE:  DiscreteKnapsack: frees = 200, max_weight = 140, extra = 142.86%
NOTICE:  DiscreteKnapsack: frees = 200, max_weight = 140, extra = 142.86%
NOTICE:  DiscreteKnapsack: frees = 30, max_weight = 40, extra = 75.00%
NOTICE:  DiscreteKnapsack: frees = 110, max_weight = 60, extra = 183.33%
NOTICE:  DiscreteKnapsack: frees = 110, max_weight = 60, extra = 183.33%
NOTICE:  DiscreteKnapsack: frees = 110, max_weight = 60, extra = 183.33%
NOTICE:  DiscreteKnapsack: frees = 110, max_weight = 60, extra = 183.33%

and by the looks of the code, the worst case is much worse.

Given that the code original code was written in a very deliberate way
to avoid reallocations, I now think that we should maintain that.

I've attached a patch which adds bms_replace_members(). It's basically
like bms_copy() but attempts to reuse the member from another set. I
considered if the new function should be called bms_copy_inplace(),
but left it as bms_replace_members() for now.

Now I wonder if this should be backpatched to PG16.

David

Hi,

David Rowley <dgrowleyml@gmail.com> writes:

> On Tue, 16 Jan 2024 at 16:32, David Rowley <dgrowleyml@gmail.com> wrote:
>>
>>
>> Now that 00b41463c changed Bitmapset to have NULL be the only valid
>> representation of an empty set, this code no longer makes sense.  We
>> may as well just bms_free() the original set and bms_copy() in the new
>> set as the bms_del_members() call will always pfree the set anyway.

I want to know if "user just want to zero out the flags in bitmapset
but keeping the memory allocation" is a valid requirement. Commit
00b41463c makes it is hard IIUC.  The user case I have is I want to
keep the detoast datum in slot->tts_values[1]  so that any further
access doesn't need to detoast it again, I used a 'Bitmapset' in
TupleTableSlot which shows which attributes is detoast. all of the
detoast values should be pfree-d in ExecClearTuple. However if a
bms_free the bitmapset everytime in ExecClearTuple and allocate the
memory again later makes some noticable performance regression (5%
difference in my workload). That is still a open items for that patch. 

> ...

> The functions's header comment mentions "The bitmapsets are all
> pre-initialized with an unused high bit so that memory allocation is
> done only once.".
> NOTICE:  DiscreteKnapsack: frees = 110, max_weight = 60, extra = 183.33%
> NOTICE:  DiscreteKnapsack: frees = 110, max_weight = 60, extra = 183.33%
>
> and by the looks of the code, the worst case is much worse.
>

Looks like this is another user case of "user just wants to zero out the
flags in bitmapset but keeping the memory allocation".

[1] https://www.postgresql.org/message-id/flat/87il4jrk1l.fsf@163.com

-- 
Best Regards
Andy Fan

Thanks for having a look at this again.

On Thu, 18 Jan 2024 at 15:22, Richard Guo <guofenglinux@gmail.com> wrote:
> Do you think we can use 'memcpy(a, b, BITMAPSET_SIZE(b->nwords))'
> directly in the new bms_replace_members() instead of copying the
> bitmapwords one by one, like:
>
> -   i = 0;
> -   do
> -   {
> -       a->words[i] = b->words[i];
> -   } while (++i < b->nwords);
> -
> -   a->nwords = b->nwords;
> +   memcpy(a, b, BITMAPSET_SIZE(b->nwords));
>
> But I'm not sure if this is an improvement or not.

I considered this earlier but felt it was going against the method
used in other places in the file. However, on relooking I do see
bms_copy() does a memcpy().

I'm still in favour of keeping it the way the v2 patch does it for 2 reasons:

1) Ignoring bms_copy(), we use do/while in all other functions where
we operate on all words in the set.
2) memcpy isn't that fast for small numbers of bytes when that number
of bytes isn't known at compile-time.

The do/while method can take advantage of knowing that the Bitmapset
will have at least 1 word allowing a single loop check when the set
only has a single word, which I expect most Bitmapsets do.

Of course, memcpy() is fewer lines of code and this likely isn't that
performance critical, so there's certainly arguments for memcpy().
However, it isn't quite as few lines as the patch you pasted.  We
still need to overwrite a->nwords to ensure we grow the set or shrink
it to trim off any trailing zero words (which I didn't feel any need
to actually set to 0).

David

On Thu, 18 Jan 2024 at 14:58, Andy Fan <zhihuifan1213@163.com> wrote:
> I want to know if "user just want to zero out the flags in bitmapset
> but keeping the memory allocation" is a valid requirement. Commit
> 00b41463c makes it is hard IIUC.

Looking at your patch, I see:

+/*
+ * does this break commit 00b41463c21615f9bf3927f207e37f9e215d32e6?
+ * but I just found alloc memory and free the memory is too bad
+ * for this current feature. So let see ...;
+ */
+void
+bms_zero(Bitmapset *a)

I understand the requirement here, but, to answer the question in the
comment -- Yes, that does violate the requirements for how an empty
set is represented and as of c7e5e994b and possibly earlier, any
subsequent Bitmapset operations will cause an Assert failure due to
the trailing zero word(s) left by bms_zero().

> Looks like this is another user case of "user just wants to zero out the
> flags in bitmapset but keeping the memory allocation".

I don't really see a way to have it work the way you want without
violating the new representation of an empty Bitmapset.  Per [1],
there's quite a performance advantage to 00b41463c plus the additional
don't allow trailing empty words rule done in a8c09daa8. So I don't
wish the rules were more lax.

Maybe Bitmapsets aren't the best fit for your need.  Maybe it would be
better to have a more simple fixed size bitset that you could allocate
in the same allocation as the TupleTableSlot's tts_null and tts_values
arrays. The slot's TupleDesc should know how many bits are needed.

David

[1] https://postgr.es/m/CAJ2pMkYcKHFBD_OMUSVyhYSQU0-j9T6NZ0pL6pwbZsUCohWc7Q%40mail.gmail.com

Hi, 
David Rowley <dgrowleyml@gmail.com> writes:

> On Thu, 18 Jan 2024 at 14:58, Andy Fan <zhihuifan1213@163.com> wrote:
>> I want to know if "user just want to zero out the flags in bitmapset
>> but keeping the memory allocation" is a valid requirement. Commit
>> 00b41463c makes it is hard IIUC.
>
> Looking at your patch, I see:
>
> +/*
> + * does this break commit 00b41463c21615f9bf3927f207e37f9e215d32e6?
> + * but I just found alloc memory and free the memory is too bad
> + * for this current feature. So let see ...;
> + */
> +void
> +bms_zero(Bitmapset *a)
>
> I understand the requirement here, but, to answer the question in the
> comment -- Yes, that does violate the requirements for how an empty
> set is represented and as of c7e5e994b and possibly earlier, any
> subsequent Bitmapset operations will cause an Assert failure due to
> the trailing zero word(s) left by bms_zero().

Thanks for the understanding and confirmation.

>> Looks like this is another user case of "user just wants to zero out the
>> flags in bitmapset but keeping the memory allocation".
>
> I don't really see a way to have it work the way you want without
> violating the new representation of an empty Bitmapset.  Per [1],
> there's quite a performance advantage to 00b41463c plus the additional
> don't allow trailing empty words rule done in a8c09daa8. So I don't
> wish the rules were more lax.

I agree with this.

>
> Maybe Bitmapsets aren't the best fit for your need.  Maybe it would be
> better to have a more simple fixed size bitset that you could allocate
> in the same allocation as the TupleTableSlot's tts_null and tts_values
> arrays. The slot's TupleDesc should know how many bits are needed.

I think this is the direction we have to go. There is no bitset struct
yet, so I prefer to design it as below, The APIs are pretty similar with
Bitmapset. 

typdef char Bitset;

Bitset *bitset_init(int size);
void bitset_add_member(Bitset *bitset, int x);
void bitset_del_member(Bitset *bitset, int x);
Bitset *bitset_add_members(Bitset *bitset1, Bitset *bitset2);
bool bitset_is_member(int x);
int bitset_next_member(Bitset *bitset, int i);
Bitset *bitset_clear();

After this, we may use it for DiscreteKnapsack as well since the
num_items is fixed as well and this user case wants the memory allocation 
is done only once.

-- 
Best Regards
Andy Fan

Hi,

David Rowley <dgrowleyml@gmail.com> writes:

> Given that the code original code was written in a very deliberate way
> to avoid reallocations, I now think that we should maintain that.
>
> I've attached a patch which adds bms_replace_members(). It's basically
> like bms_copy() but attempts to reuse the member from another set. I
> considered if the new function should be called bms_copy_inplace(),
> but left it as bms_replace_members() for now.

I find the following code in DiscreteKnapsack is weird.


    for (i = 0; i <= max_weight; ++i)
    {
        values[i] = 0;

** memory allocation here, and the num_items bit is removed later **
    
        sets[i] = bms_make_singleton(num_items);
    }


        ** num_items bit is removed here **
    result = bms_del_member(bms_copy(sets[max_weight]), num_items);

I can't access the github.com now so I can't test my idea, but basiclly
I think we may need some improvement here. like 'sets[i] = NULL;' at the
first and remove the bms_del_member later.

-- 
Best Regards
Andy Fan

On Fri, 19 Jan 2024 at 01:07, Andy Fan <zhihuifan1213@163.com> wrote:
> I find the following code in DiscreteKnapsack is weird.
>
>
>         for (i = 0; i <= max_weight; ++i)
>         {
>                 values[i] = 0;
>
> ** memory allocation here, and the num_items bit is removed later **
>
>                 sets[i] = bms_make_singleton(num_items);
>         }
>
>
>         ** num_items bit is removed here **
>         result = bms_del_member(bms_copy(sets[max_weight]), num_items);

It does not seem weird to me.  If the set is going to have multiple
words then adding a member 1 higher than the highest we'll ever add
ensures the set has enough words and we don't need to repalloc to grow
the set when we bms_add_member().

David

On Thu, 18 Jan 2024 at 16:24, David Rowley <dgrowleyml@gmail.com> wrote:
> On Thu, 18 Jan 2024 at 15:22, Richard Guo <guofenglinux@gmail.com> wrote:
> > Do you think we can use 'memcpy(a, b, BITMAPSET_SIZE(b->nwords))'
> > directly in the new bms_replace_members() instead of copying the
> > bitmapwords one by one, like:
> >
> > -   i = 0;
> > -   do
> > -   {
> > -       a->words[i] = b->words[i];
> > -   } while (++i < b->nwords);
> > -
> > -   a->nwords = b->nwords;
> > +   memcpy(a, b, BITMAPSET_SIZE(b->nwords));
> >
> > But I'm not sure if this is an improvement or not.
>
> I considered this earlier but felt it was going against the method
> used in other places in the file. However, on relooking I do see
> bms_copy() does a memcpy().

I feel it's not worth debating the memcpy thing any further, so I've
pushed the v2 patch.

Thanks for reviewing.

David

David Rowley <dgrowleyml@gmail.com> writes:

> On Fri, 19 Jan 2024 at 01:07, Andy Fan <zhihuifan1213@163.com> wrote:
>> I find the following code in DiscreteKnapsack is weird.
>>
>>
>>         for (i = 0; i <= max_weight; ++i)
>>         {
>>                 values[i] = 0;
>>
>> ** memory allocation here, and the num_items bit is removed later **
>>
>>                 sets[i] = bms_make_singleton(num_items);
>>         }
>>
>>
>>         ** num_items bit is removed here **
>>         result = bms_del_member(bms_copy(sets[max_weight]), num_items);
>
> It does not seem weird to me.  If the set is going to have multiple
> words then adding a member 1 higher than the highest we'll ever add
> ensures the set has enough words and we don't need to repalloc to grow
> the set when we bms_add_member().

Hmm, I missed this part, thanks for the explaination. If bitset feature
can get in someday, the future user case like this can use bitset
directly to avoid this trick method. 

-- 
Best Regards
Andy Fan