Horton

Thread

Commits

  1. Move some bitmap logic out of bitmapset.c

  1. move some bitmapset.c macros to bitmapset.h

    John Naylor <john.naylor@enterprisedb.com> — 2022-12-05T11:51:50Z

    Over in [1], Masahiko and I found that using some bitmapset logic yields a
useful speedup in one part of the proposed radix tree patch. In addition to
what's in bitmapset.h now, we'd need WORDNUM, BITNUM, RIGHTMOST_ONE and
bmw_rightmost_one_pos() from bitmapset.c. The file tidbitmap.c has its own
copies of the first two, and we could adapt that strategy again. But
instead of three files defining these, it seems like it's time to consider
moving them somewhere more central.

Attached is a simple form of this concept, including moving
HAS_MULTIPLE_ONES just for consistency. One possible objection is the
possibility of namespace clash. Thoughts?

I also considered putting the macros and typedefs in pg_bitutils.h. One
organizational advantage is that pg_bitutils.h already offers convenience
function symbols where the parameter depends on SIZEOF_SIZE_T, so putting
the BITS_PER_BITMAPWORD versions there makes sense. But that way is not a
clear win, so I didn't go that far.

[1]
https://www.postgresql.org/message-id/CAFBsxsHgP5LP9q%3DRq_3Q2S6Oyut67z%2BVpemux%2BKseSPXhJF7sg%40mail.gmail.com

-- 
John Naylor
EDB: http://www.enterprisedb.com

  2. Re: move some bitmapset.c macros to bitmapset.h

    Alvaro Herrera <alvherre@alvh.no-ip.org> — 2022-12-05T12:05:49Z

    On 2022-Dec-05, John Naylor wrote:

> diff --git a/src/backend/nodes/bitmapset.c b/src/backend/nodes/bitmapset.c
> index b7b274aeff..3204b49738 100644
> --- a/src/backend/nodes/bitmapset.c
> +++ b/src/backend/nodes/bitmapset.c
> @@ -26,33 +26,9 @@
>  #include "port/pg_bitutils.h"
>  
>  
> -#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
> -#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)

In this location, nobody can complain about the naming of these macros,
since they're just used to implement other bitmapset.c code.  However,
if you move them to the .h file, ISTM you should give them more
meaningful names.

-- 
Álvaro Herrera               48°01'N 7°57'E  —  https://www.EnterpriseDB.com/
"Oh, great altar of passive entertainment, bestow upon me thy discordant images
at such speed as to render linear thought impossible" (Calvin a la TV)

  3. Re: move some bitmapset.c macros to bitmapset.h

    Tom Lane <tgl@sss.pgh.pa.us> — 2022-12-05T14:32:59Z

    Alvaro Herrera <alvherre@alvh.no-ip.org> writes:
> On 2022-Dec-05, John Naylor wrote:
>> -#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
>> -#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)

> In this location, nobody can complain about the naming of these macros,
> since they're just used to implement other bitmapset.c code.  However,
> if you move them to the .h file, ISTM you should give them more
> meaningful names.

IMV these are absolutely private to bitmapset.c.  I reject the idea
that they should be exposed publicly, under these names or any others.

Maybe we need some more bitmapset primitive functions?  What is it
you actually want to accomplish in the end?

			regards, tom lane

  4. Re: move some bitmapset.c macros to bitmapset.h

    John Naylor <john.naylor@enterprisedb.com> — 2022-12-06T04:17:04Z

    On Mon, Dec 5, 2022 at 9:33 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> Alvaro Herrera <alvherre@alvh.no-ip.org> writes:
> > On 2022-Dec-05, John Naylor wrote:
> >> -#define WORDNUM(x)  ((x) / BITS_PER_BITMAPWORD)
> >> -#define BITNUM(x)   ((x) % BITS_PER_BITMAPWORD)
>
> > In this location, nobody can complain about the naming of these macros,
> > since they're just used to implement other bitmapset.c code.  However,
> > if you move them to the .h file, ISTM you should give them more
> > meaningful names.
>
> IMV these are absolutely private to bitmapset.c.  I reject the idea
> that they should be exposed publicly, under these names or any others.

Well, they've already escaped to tidbitmap.c as a copy. How do you feel
about going that route?

> Maybe we need some more bitmapset primitive functions?  What is it
> you actually want to accomplish in the end?

 An inserter into one type of node in a tree structure must quickly find a
free position in an array. We have a bitmap of 128 bits to indicate whether
the corresponding array position is free. The proposed coding is:

 /* get the first word with at least one bit not set */
for (idx = 0; idx < WORDNUM(128); idx++)
{
  if (isset[idx] < ~((bitmapword) 0))
    break;
}

/* To get the first unset bit in X, get the first set bit in ~X */
inverse = ~(isset[idx]);
slotpos = idx * BITS_PER_BITMAPWORD;
slotpos += bmw_rightmost_one_pos(inverse);

/* mark the slot used */
isset[idx] |= RIGHTMOST_ONE(inverse);

return slotpos;

...which, if it were reversed so that a set bit meant "available", would
essentially be bms_first_member(), so a more primitive version of that
might work.

--
John Naylor
EDB: http://www.enterprisedb.com

  5. Re: move some bitmapset.c macros to bitmapset.h

    Tom Lane <tgl@sss.pgh.pa.us> — 2022-12-06T04:57:20Z

    John Naylor <john.naylor@enterprisedb.com> writes:
> On Mon, Dec 5, 2022 at 9:33 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> IMV these are absolutely private to bitmapset.c.  I reject the idea
>> that they should be exposed publicly, under these names or any others.

> Well, they've already escaped to tidbitmap.c as a copy. How do you feel
> about going that route?

Not terribly pleased with that either, I must admit.

>> Maybe we need some more bitmapset primitive functions?  What is it
>> you actually want to accomplish in the end?

> 	for (idx = 0; idx < WORDNUM(128); idx++)

BITS_PER_BITMAPWORD is already public, so can't you spell that

	for (idx = 0; idx < 128/BITS_PER_BITMAPWORD; idx++)

> slotpos += bmw_rightmost_one_pos(inverse);

I'm not terribly against exposing bmw_rightmost_one_pos, given
that it's just exposing the pg_rightmost_one_posXX variant that
matches BITS_PER_BITMAPWORD.

> isset[idx] |= RIGHTMOST_ONE(inverse);

And RIGHTMOST_ONE is something that could be made public, but
I think it belongs in pg_bitutils.h, perhaps with a different
name.

> ...which, if it were reversed so that a set bit meant "available", would
> essentially be bms_first_member(), so a more primitive version of that
> might work.

That could be a reasonable direction to pursue as well.

			regards, tom lane

  6. Re: move some bitmapset.c macros to bitmapset.h

    David Rowley <dgrowleyml@gmail.com> — 2022-12-06T05:46:38Z

    On Tue, 6 Dec 2022 at 17:57, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> And RIGHTMOST_ONE is something that could be made public, but
> I think it belongs in pg_bitutils.h, perhaps with a different
> name.

Maybe there's a path of lesser resistance... There's been a bit of
work in pg_bitutils.h to define some of the bit manipulation functions
for size_t types which wrap the 32 or 64-bit version of the function
accordingly. Couldn't we just define one of those for
pg_rightmost_one_pos and then use a size_t as the bitmap word type?

Then you'd end up with something like:

for (idx = 0; idx < 128 / (sizeof(size_t) * 8); idx++)
 if (isset[idx] != ~((size_t) 0))
    break;
slotpos = idx * (sizeof(size_t) * 8) + pg_rightmost_one_pos_size_t(~isset[idx]);

no need to export anything from bitmapset.c to do it like that.

I've not looked at the code in question to know how often that form
would be needed. Maybe it would need a set of inlined functions
similar to above in the same file this is being used in to save on
repeating too often.

David

  7. Re: move some bitmapset.c macros to bitmapset.h

    Tom Lane <tgl@sss.pgh.pa.us> — 2022-12-06T05:57:31Z

    David Rowley <dgrowleyml@gmail.com> writes:
> Maybe there's a path of lesser resistance... There's been a bit of
> work in pg_bitutils.h to define some of the bit manipulation functions
> for size_t types which wrap the 32 or 64-bit version of the function
> accordingly. Couldn't we just define one of those for
> pg_rightmost_one_pos and then use a size_t as the bitmap word type?

It doesn't seem particularly wise to me to hard-wire the bitmap
word size as sizeof(size_t).  There is not a necessary connection
between those things: there could be a performance reason to
choose a word width that's different from size_t.

If we do put RIGHTMOST_ONE functionality into pg_bitutils.h,
I'd envision it as pg_bitutils.h exporting both 32-bit and
64-bit versions of that, and then bitmapset.c choosing the
appropriate one just like it chooses bmw_rightmost_one_pos.

			regards, tom lane

  8. Re: move some bitmapset.c macros to bitmapset.h

    John Naylor <john.naylor@enterprisedb.com> — 2022-12-06T06:21:04Z

    On Tue, Dec 6, 2022 at 12:57 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:

> > Well, they've already escaped to tidbitmap.c as a copy. How do you feel
> > about going that route?
>
> Not terribly pleased with that either, I must admit.

Okay, I won't pursue that further.

> If we do put RIGHTMOST_ONE functionality into pg_bitutils.h,
> I'd envision it as pg_bitutils.h exporting both 32-bit and
> 64-bit versions of that, and then bitmapset.c choosing the
> appropriate one just like it chooses bmw_rightmost_one_pos.

Here's a quick go at that. I've not attempted to use it for what I need,
but it looks like it fits the bill.

--
John Naylor
EDB: http://www.enterprisedb.com

  9. Re: move some bitmapset.c macros to bitmapset.h

    Tom Lane <tgl@sss.pgh.pa.us> — 2022-12-06T06:29:39Z

    John Naylor <john.naylor@enterprisedb.com> writes:
> Here's a quick go at that. I've not attempted to use it for what I need,
> but it looks like it fits the bill.

Passes a quick eyeball check, but of course we should have a
concrete external use for the new pg_bitutils functions.

			regards, tom lane