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
src/backend/nodes/bitmapset.c | 24 ------------------------ src/backend/nodes/tidbitmap.c | 5 ----- src/include/nodes/bitmapset.h | 24 ++++++++++++++++++++++++ 3 files changed, 24 insertions(+), 29 deletions(-) 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) - #define BITMAPSET_SIZE(nwords) \ (offsetof(Bitmapset, words) + (nwords) * sizeof(bitmapword)) -/*---------- - * This is a well-known cute trick for isolating the rightmost one-bit - * in a word. It assumes two's complement arithmetic. Consider any - * nonzero value, and focus attention on the rightmost one. The value is - * then something like - * xxxxxx10000 - * where x's are unspecified bits. The two's complement negative is formed - * by inverting all the bits and adding one. Inversion gives - * yyyyyy01111 - * where each y is the inverse of the corresponding x. Incrementing gives - * yyyyyy10000 - * and then ANDing with the original value gives - * 00000010000 - * This works for all cases except original value = zero, where of course - * we get zero. - *---------- - */ -#define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x))) - -#define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x)) - /* Select appropriate bit-twiddling functions for bitmap word size */ #if BITS_PER_BITMAPWORD == 32 #define bmw_leftmost_one_pos(w) pg_leftmost_one_pos32(w) diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c index a7a6b26668..8a1fd1d205 100644 --- a/src/backend/nodes/tidbitmap.c +++ b/src/backend/nodes/tidbitmap.c @@ -72,11 +72,6 @@ */ #define PAGES_PER_CHUNK (BLCKSZ / 32) -/* We use BITS_PER_BITMAPWORD and typedef bitmapword from nodes/bitmapset.h */ - -#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) -#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) - /* number of active words for an exact page: */ #define WORDS_PER_PAGE ((MAX_TUPLES_PER_PAGE - 1) / BITS_PER_BITMAPWORD + 1) /* number of active words for a lossy chunk: */ diff --git a/src/include/nodes/bitmapset.h b/src/include/nodes/bitmapset.h index 2792281658..8462282b9e 100644 --- a/src/include/nodes/bitmapset.h +++ b/src/include/nodes/bitmapset.h @@ -48,6 +48,30 @@ typedef int32 signedbitmapword; /* must be the matching signed type */ #endif +#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) +#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) + +/*---------- + * This is a well-known cute trick for isolating the rightmost one-bit + * in a word. It assumes two's complement arithmetic. Consider any + * nonzero value, and focus attention on the rightmost one. The value is + * then something like + * xxxxxx10000 + * where x's are unspecified bits. The two's complement negative is formed + * by inverting all the bits and adding one. Inversion gives + * yyyyyy01111 + * where each y is the inverse of the corresponding x. Incrementing gives + * yyyyyy10000 + * and then ANDing with the original value gives + * 00000010000 + * This works for all cases except original value = zero, where of course + * we get zero. + *---------- + */ +#define RIGHTMOST_ONE(x) ((signedbitmapword) (x) & -((signedbitmapword) (x))) + +#define HAS_MULTIPLE_ONES(x) ((bitmapword) RIGHTMOST_ONE(x) != (x)) + typedef struct Bitmapset { pg_node_attr(custom_copy_equal, special_read_write)