Re: Strange Bitmapset manipulation in DiscreteKnapsack()

From: Andy Fan <zhihuifan1213(at)163(dot)com>
To: David Rowley <dgrowleyml(at)gmail(dot)com>
Cc: pgsql-hackers(at)lists(dot)postgresql(dot)org
Subject: Re: Strange Bitmapset manipulation in DiscreteKnapsack()
Date: 2024-01-18 05:10:57
Message-ID: 87cytzyz9w.fsf@163.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers


Hi,
David Rowley <dgrowleyml(at)gmail(dot)com> writes:

> On Thu, 18 Jan 2024 at 14:58, Andy Fan <zhihuifan1213(at)163(dot)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

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Jeff Davis 2024-01-18 05:11:00 Re: Fix search_path for all maintenance commands
Previous Message Montana Low 2024-01-18 05:10:05 Increasing IndexTupleData.t_info from uint16 to uint32