v16-0009-Use-bitmap-operations-for-isset-arrays-rather-th.patch

From e1085a0420f719f7e4ce8a904794ab8e484b75a9 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Mon, 19 Dec 2022 16:16:12 +0700
Subject: [PATCH v16 09/12] Use bitmap operations for isset arrays rather than
 byte operations

It's simpler to do the same thing everywhere, even for node256
where iteration performance doesn't matter as much because we
always can insert directly.

Also rename WORDNUM and BITNUM to avoid clashing with bitmapset.c.
---
 src/backend/lib/radixtree.c | 64 +++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 28 deletions(-)

diff --git a/src/backend/lib/radixtree.c b/src/backend/lib/radixtree.c
index ddf7b002fc..7899e844fb 100644
--- a/src/backend/lib/radixtree.c
+++ b/src/backend/lib/radixtree.c
@@ -77,12 +77,6 @@
 /* The number of maximum slots in the node */
 #define RT_NODE_MAX_SLOTS (1 << RT_NODE_SPAN)
 
-/*
- * Return the number of bits required to represent nslots slots, used
- * nodes indexed by array lookup.
- */
-#define RT_NODE_NSLOTS_BITS(nslots) ((nslots) / (sizeof(uint8) * BITS_PER_BYTE))
-
 /* Mask for extracting a chunk from the key */
 #define RT_CHUNK_MASK ((1 << RT_NODE_SPAN) - 1)
 
@@ -98,15 +92,9 @@
 /* Get a chunk from the key */
 #define RT_GET_KEY_CHUNK(key, shift) ((uint8) (((key) >> (shift)) & RT_CHUNK_MASK))
 
-/*
- * Mapping from the value to the bit in is-set bitmap in the node-256.
- */
-#define RT_NODE_BITMAP_BYTE(v) ((v) / BITS_PER_BYTE)
-#define RT_NODE_BITMAP_BIT(v) (UINT64CONST(1) << ((v) % RT_NODE_SPAN))
-
-/* FIXME rename */
-#define WORDNUM(x)	((x) / BITS_PER_BITMAPWORD)
-#define BITNUM(x)	((x) % BITS_PER_BITMAPWORD)
+/* For accessing bitmaps */
+#define BM_IDX(x)	((x) / BITS_PER_BITMAPWORD)
+#define BM_BIT(x)	((x) % BITS_PER_BITMAPWORD)
 
 /* Enum used rt_node_search() */
 typedef enum
@@ -214,7 +202,7 @@ typedef struct rt_node_base125
 	uint8		slot_idxs[RT_NODE_MAX_SLOTS];
 
 	/* isset is a bitmap to track which slot is in use */
-	bitmapword		isset[WORDNUM(128)];
+	bitmapword		isset[BM_IDX(128)];
 } rt_node_base_125;
 
 typedef struct rt_node_base256
@@ -300,7 +288,7 @@ typedef struct rt_node_leaf_256
 	rt_node_base_256 base;
 
 	/* isset is a bitmap to track which slot is in use */
-	uint8		isset[RT_NODE_NSLOTS_BITS(RT_NODE_MAX_SLOTS)];
+	bitmapword	isset[BM_IDX(RT_NODE_MAX_SLOTS)];
 
 	/* Slots for 256 values */
 	uint64		values[RT_NODE_MAX_SLOTS];
@@ -665,17 +653,23 @@ node_125_is_chunk_used(rt_node_base_125 *node, uint8 chunk)
 static inline bool
 node_inner_125_is_slot_used(rt_node_inner_125 *node, uint8 slot)
 {
+	int			idx = BM_IDX(slot);
+	int			bitnum = BM_BIT(slot);
+
 	Assert(!NODE_IS_LEAF(node));
 	Assert(slot < node->base.n.fanout);
-	return (node->base.isset[WORDNUM(slot)] & ((bitmapword) 1 << BITNUM(slot))) != 0;
+	return (node->base.isset[idx] & ((bitmapword) 1 << bitnum)) != 0;
 }
 
 static inline bool
 node_leaf_125_is_slot_used(rt_node_leaf_125 *node, uint8 slot)
 {
+	int			idx = BM_IDX(slot);
+	int			bitnum = BM_BIT(slot);
+
 	Assert(NODE_IS_LEAF(node));
 	Assert(slot < node->base.n.fanout);
-	return (node->base.isset[WORDNUM(slot)] & ((bitmapword) 1 << BITNUM(slot))) != 0;
+	return (node->base.isset[idx] & ((bitmapword) 1 << bitnum)) != 0;
 }
 #endif
 
@@ -698,9 +692,12 @@ static void
 node_inner_125_delete(rt_node_inner_125 *node, uint8 chunk)
 {
 	int			slotpos = node->base.slot_idxs[chunk];
+	int			idx = BM_IDX(slotpos);
+	int			bitnum = BM_BIT(slotpos);
 
 	Assert(!NODE_IS_LEAF(node));
-	node->base.isset[WORDNUM(slotpos)] &= ~((bitmapword) 1 << BITNUM(slotpos));
+
+	node->base.isset[idx] &= ~((bitmapword) 1 << bitnum);
 	node->children[node->base.slot_idxs[chunk]] = NULL;
 	node->base.slot_idxs[chunk] = RT_NODE_125_INVALID_IDX;
 }
@@ -709,9 +706,11 @@ static void
 node_leaf_125_delete(rt_node_leaf_125 *node, uint8 chunk)
 {
 	int			slotpos = node->base.slot_idxs[chunk];
+	int			idx = BM_IDX(slotpos);
+	int			bitnum = BM_BIT(slotpos);
 
 	Assert(NODE_IS_LEAF(node));
-	node->base.isset[WORDNUM(slotpos)] &= ~((bitmapword) 1 << BITNUM(slotpos));
+	node->base.isset[idx] &= ~((bitmapword) 1 << bitnum);
 	node->base.slot_idxs[chunk] = RT_NODE_125_INVALID_IDX;
 }
 
@@ -724,7 +723,7 @@ node_125_find_unused_slot(bitmapword *isset)
 	bitmapword	inverse;
 
 	/* get the first word with at least one bit not set */
-	for (idx = 0; idx < WORDNUM(128); idx++)
+	for (idx = 0; idx < BM_IDX(128); idx++)
 	{
 		if (isset[idx] < ~((bitmapword) 0))
 			break;
@@ -798,8 +797,11 @@ node_inner_256_is_chunk_used(rt_node_inner_256 *node, uint8 chunk)
 static inline bool
 node_leaf_256_is_chunk_used(rt_node_leaf_256 *node, uint8 chunk)
 {
+	int			idx = BM_IDX(chunk);
+	int			bitnum = BM_BIT(chunk);
+
 	Assert(NODE_IS_LEAF(node));
-	return (node->isset[RT_NODE_BITMAP_BYTE(chunk)] & RT_NODE_BITMAP_BIT(chunk)) != 0;
+	return (node->isset[idx] & ((bitmapword) 1 << bitnum)) != 0;
 }
 
 static inline rt_node *
@@ -830,8 +832,11 @@ node_inner_256_set(rt_node_inner_256 *node, uint8 chunk, rt_node *child)
 static inline void
 node_leaf_256_set(rt_node_leaf_256 *node, uint8 chunk, uint64 value)
 {
+	int			idx = BM_IDX(chunk);
+	int			bitnum = BM_BIT(chunk);
+
 	Assert(NODE_IS_LEAF(node));
-	node->isset[RT_NODE_BITMAP_BYTE(chunk)] |= RT_NODE_BITMAP_BIT(chunk);
+	node->isset[idx] |= ((bitmapword) 1 << bitnum);
 	node->values[chunk] = value;
 }
 
@@ -846,8 +851,11 @@ node_inner_256_delete(rt_node_inner_256 *node, uint8 chunk)
 static inline void
 node_leaf_256_delete(rt_node_leaf_256 *node, uint8 chunk)
 {
+	int			idx = BM_IDX(chunk);
+	int			bitnum = BM_BIT(chunk);
+
 	Assert(NODE_IS_LEAF(node));
-	node->isset[RT_NODE_BITMAP_BYTE(chunk)] &= ~(RT_NODE_BITMAP_BIT(chunk));
+	node->isset[idx] &= ~((bitmapword) 1 << bitnum);
 }
 
 /*
@@ -2269,8 +2277,8 @@ rt_verify_node(rt_node *node)
 					rt_node_leaf_256 *n256 = (rt_node_leaf_256 *) node;
 					int			cnt = 0;
 
-					for (int i = 0; i < RT_NODE_NSLOTS_BITS(RT_NODE_MAX_SLOTS); i++)
-						cnt += pg_popcount32(n256->isset[i]);
+					for (int i = 0; i < BM_IDX(RT_NODE_MAX_SLOTS); i++)
+						cnt += bmw_popcount(n256->isset[i]);
 
 					/* Check if the number of used chunk matches */
 					Assert(n256->base.n.count == cnt);
@@ -2386,7 +2394,7 @@ rt_dump_node(rt_node *node, int level, bool recurse)
 					rt_node_leaf_125 *n = (rt_node_leaf_125 *) node;
 
 					fprintf(stderr, ", isset-bitmap:");
-					for (int i = 0; i < WORDNUM(128); i++)
+					for (int i = 0; i < BM_IDX(128); i++)
 					{
 						fprintf(stderr, UINT64_FORMAT_HEX " ", n->base.isset[i]);
 					}
-- 
2.38.1