move some bitmapset.c macros to bitmapset.h

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)

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

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

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

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

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

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

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