v16-0012-Separate-find-and-delete-actions-into-separate-f.patch

From 3637d74416d565e3ca6faff2ad6b6a25b2c50689 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Fri, 23 Dec 2022 17:41:05 +0700
Subject: [PATCH v16 12/12] Separate find and delete actions into separate
 functions

This makes hot paths smaller and less branchy.
---
 src/backend/lib/radixtree.c             | 73 ++++++++++++++++---------
 src/include/lib/radixtree_search_impl.h | 68 ++++++++++++-----------
 2 files changed, 83 insertions(+), 58 deletions(-)

diff --git a/src/backend/lib/radixtree.c b/src/backend/lib/radixtree.c
index 99450c96c8..c934bff693 100644
--- a/src/backend/lib/radixtree.c
+++ b/src/backend/lib/radixtree.c
@@ -96,13 +96,6 @@
 #define BM_IDX(x)	((x) / BITS_PER_BITMAPWORD)
 #define BM_BIT(x)	((x) % BITS_PER_BITMAPWORD)
 
-/* Enum used rt_node_search() */
-typedef enum
-{
-	RT_ACTION_FIND = 0,			/* find the key-value */
-	RT_ACTION_DELETE,			/* delete the key-value */
-} rt_action;
-
 /*
  * Supported radix tree node kinds and size classes.
  *
@@ -422,10 +415,8 @@ static inline void rt_init_node(rt_node *node, uint8 kind, rt_size_class size_cl
 								bool inner);
 static void rt_free_node(radix_tree *tree, rt_node *node);
 static void rt_extend(radix_tree *tree, uint64 key);
-static inline bool rt_node_search_inner(rt_node *node, uint64 key, rt_action action,
-										rt_node **child_p);
-static inline bool rt_node_search_leaf(rt_node *node, uint64 key, rt_action action,
-									   uint64 *value_p);
+static inline bool rt_node_search_inner(rt_node *node, uint64 key, rt_node **child_p);
+static inline bool rt_node_search_leaf(rt_node *node, uint64 key, uint64 *value_p);
 static bool rt_node_insert_inner(radix_tree *tree, rt_node *parent, rt_node *node,
 								 uint64 key, rt_node *child);
 static bool rt_node_insert_leaf(radix_tree *tree, rt_node *parent, rt_node *node,
@@ -1100,33 +1091,65 @@ rt_set_extend(radix_tree *tree, uint64 key, uint64 value, rt_node *parent,
 }
 
 /*
- * Search for the child pointer corresponding to 'key' in the given node, and
- * do the specified 'action'.
+ * Search for the child pointer corresponding to 'key' in the given node.
  *
  * Return true if the key is found, otherwise return false. On success, the child
  * pointer is set to child_p.
  */
 static inline bool
-rt_node_search_inner(rt_node *node, uint64 key, rt_action action, rt_node **child_p)
+rt_node_search_inner(rt_node *node, uint64 key, rt_node **child_p)
 {
+#define RT_ACTION_FIND
 #define RT_NODE_LEVEL_INNER
 #include "lib/radixtree_search_impl.h"
 #undef RT_NODE_LEVEL_INNER
+#undef RT_ACTION_FIND
 }
 
 /*
- * Search for the value corresponding to 'key' in the given node, and do the
- * specified 'action'.
+ * Search for the value corresponding to 'key' in the given node.
  *
  * Return true if the key is found, otherwise return false. On success, the pointer
  * to the value is set to value_p.
  */
 static inline bool
-rt_node_search_leaf(rt_node *node, uint64 key, rt_action action, uint64 *value_p)
+rt_node_search_leaf(rt_node *node, uint64 key, uint64 *value_p)
+{
+#define RT_ACTION_FIND
+#define RT_NODE_LEVEL_LEAF
+#include "lib/radixtree_search_impl.h"
+#undef RT_NODE_LEVEL_LEAF
+#undef RT_ACTION_FIND
+}
+
+/*
+ * Search for the child pointer corresponding to 'key' in the given node.
+ *
+ * Delete the node and return true if the key is found, otherwise return false.
+ */
+static inline bool
+rt_node_delete_inner(rt_node *node, uint64 key)
+{
+#define RT_ACTION_DELETE
+#define RT_NODE_LEVEL_INNER
+#include "lib/radixtree_search_impl.h"
+#undef RT_NODE_LEVEL_INNER
+#undef RT_ACTION_DELETE
+}
+
+/*
+ * Search for the value corresponding to 'key' in the given node.
+ *
+ * Delete the node and return true if the key is found, otherwise return false.
+ */
+static inline bool
+rt_node_delete_leaf(rt_node *node, uint64 key)
 {
+#define RT_ACTION_DELETE
 #define RT_NODE_LEVEL_LEAF
 #include "lib/radixtree_search_impl.h"
 #undef RT_NODE_LEVEL_LEAF
+#undef RT_ACTION_DELETE
 }
 
 /* Insert the child to the inner node */
@@ -1235,7 +1258,7 @@ rt_set(radix_tree *tree, uint64 key, uint64 value)
 		if (NODE_IS_LEAF(node))
 			break;
 
-		if (!rt_node_search_inner(node, key, RT_ACTION_FIND, &child))
+		if (!rt_node_search_inner(node, key, &child))
 		{
 			rt_set_extend(tree, key, value, parent, node);
 			return false;
@@ -1282,14 +1305,14 @@ rt_search(radix_tree *tree, uint64 key, uint64 *value_p)
 		if (NODE_IS_LEAF(node))
 			break;
 
-		if (!rt_node_search_inner(node, key, RT_ACTION_FIND, &child))
+		if (!rt_node_search_inner(node, key, &child))
 			return false;
 
 		node = child;
 		shift -= RT_NODE_SPAN;
 	}
 
-	return rt_node_search_leaf(node, key, RT_ACTION_FIND, value_p);
+	return rt_node_search_leaf(node, key, value_p);
 }
 
 /*
@@ -1322,7 +1345,7 @@ rt_delete(radix_tree *tree, uint64 key)
 		/* Push the current node to the stack */
 		stack[++level] = node;
 
-		if (!rt_node_search_inner(node, key, RT_ACTION_FIND, &child))
+		if (!rt_node_search_inner(node, key, &child))
 			return false;
 
 		node = child;
@@ -1331,7 +1354,7 @@ rt_delete(radix_tree *tree, uint64 key)
 
 	/* Delete the key from the leaf node if exists */
 	Assert(NODE_IS_LEAF(node));
-	deleted = rt_node_search_leaf(node, key, RT_ACTION_DELETE, NULL);
+	deleted = rt_node_delete_leaf(node, key);
 
 	if (!deleted)
 	{
@@ -1357,7 +1380,7 @@ rt_delete(radix_tree *tree, uint64 key)
 	{
 		node = stack[level--];
 
-		deleted = rt_node_search_inner(node, key, RT_ACTION_DELETE, NULL);
+		deleted = rt_node_delete_inner(node, key);
 		Assert(deleted);
 
 		/* If the node didn't become empty, we stop deleting the key */
@@ -1989,12 +2012,12 @@ rt_dump_search(radix_tree *tree, uint64 key)
 			uint64		dummy;
 
 			/* We reached at a leaf node, find the corresponding slot */
-			rt_node_search_leaf(node, key, RT_ACTION_FIND, &dummy);
+			rt_node_search_leaf(node, key, &dummy);
 
 			break;
 		}
 
-		if (!rt_node_search_inner(node, key, RT_ACTION_FIND, &child))
+		if (!rt_node_search_inner(node, key, &child))
 			break;
 
 		node = child;
diff --git a/src/include/lib/radixtree_search_impl.h b/src/include/lib/radixtree_search_impl.h
index 0173d9cb2f..28c02da2bf 100644
--- a/src/include/lib/radixtree_search_impl.h
+++ b/src/include/lib/radixtree_search_impl.h
@@ -10,16 +10,21 @@
 #define RT_NODE256_TYPE rt_node_leaf_256
 #else
 #error node level must be either inner or leaf
+#endif
+
+#if !defined(RT_ACTION_FIND) && !defined(RT_ACTION_DELETE)
+#error search action must be either find or delete
 #endif
 
 	uint8		chunk = RT_GET_KEY_CHUNK(key, node->shift);
-	bool		found = false;
 
+#if defined(RT_ACTION_FIND)
 #ifdef RT_NODE_LEVEL_LEAF
 	uint64		value = 0;
 #else
 	rt_node    *child = NULL;
 #endif
+#endif			/* RT_ACTION_FIND */
 
 	switch (node->kind)
 	{
@@ -29,17 +34,15 @@
 				int			idx = node_4_search_eq((rt_node_base_4 *) n4, chunk);
 
 				if (idx < 0)
-					break;
-
-				found = true;
+					return false;
 
-				if (action == RT_ACTION_FIND)
+#if defined(RT_ACTION_FIND)
 #ifdef RT_NODE_LEVEL_LEAF
 					value = n4->values[idx];
 #else
 					child = n4->children[idx];
 #endif
-				else			/* RT_ACTION_DELETE */
+#elif defined (RT_ACTION_DELETE)
 #ifdef RT_NODE_LEVEL_LEAF
 					chunk_values_array_delete(n4->base.chunks, (uint64 *) n4->values,
 											  n4->base.n.count, idx);
@@ -47,6 +50,8 @@
 					chunk_children_array_delete(n4->base.chunks, n4->children,
 											    n4->base.n.count, idx);
 #endif
+#endif			/* RT_ACTION_FIND */
+
 				break;
 			}
 		case RT_NODE_KIND_32:
@@ -55,17 +60,15 @@
 				int			idx = node_32_search_eq((rt_node_base_32 *) n32, chunk);
 
 				if (idx < 0)
-					break;
-
-				found = true;
+					return false;
 
-				if (action == RT_ACTION_FIND)
+#if defined(RT_ACTION_FIND)
 #ifdef RT_NODE_LEVEL_LEAF
 					value = n32->values[idx];
 #else
 					child = n32->children[idx];
 #endif
-				else			/* RT_ACTION_DELETE */
+#elif defined (RT_ACTION_DELETE)
 #ifdef RT_NODE_LEVEL_LEAF
 					chunk_values_array_delete(n32->base.chunks, (uint64 *) n32->values,
 											  n32->base.n.count, idx);
@@ -73,6 +76,8 @@
 					chunk_children_array_delete(n32->base.chunks, n32->children,
 											    n32->base.n.count, idx);
 #endif
+#endif			/* RT_ACTION_FIND */
+
 				break;
 			}
 		case RT_NODE_KIND_125:
@@ -80,22 +85,22 @@
 				RT_NODE125_TYPE *n125 = (RT_NODE125_TYPE *) node;
 
 				if (!node_125_is_chunk_used((rt_node_base_125 *) n125, chunk))
-					break;
+					return false;
 
-				found = true;
-
-				if (action == RT_ACTION_FIND)
+#if defined(RT_ACTION_FIND)
 #ifdef RT_NODE_LEVEL_LEAF
 					value = node_leaf_125_get_value(n125, chunk);
 #else
 					child = node_inner_125_get_child(n125, chunk);
 #endif
-				else			/* RT_ACTION_DELETE */
+#elif defined (RT_ACTION_DELETE)
 #ifdef RT_NODE_LEVEL_LEAF
 					node_leaf_125_delete(n125, chunk);
 #else
 					node_inner_125_delete(n125, chunk);
 #endif
+#endif			/* RT_ACTION_FIND */
+
 				break;
 			}
 		case RT_NODE_KIND_256:
@@ -107,43 +112,40 @@
 #else
 				if (!node_inner_256_is_chunk_used(n256, chunk))
 #endif
-					break;
-
-				found = true;
+					return false;
 
-				if (action == RT_ACTION_FIND)
+#if defined(RT_ACTION_FIND)
 #ifdef RT_NODE_LEVEL_LEAF
 					value = node_leaf_256_get_value(n256, chunk);
 #else
 					child = node_inner_256_get_child(n256, chunk);
 #endif
-				else			/* RT_ACTION_DELETE */
+#elif defined (RT_ACTION_DELETE)
 #ifdef RT_NODE_LEVEL_LEAF
 					node_leaf_256_delete(n256, chunk);
 #else
 					node_inner_256_delete(n256, chunk);
 #endif
+#endif			/* RT_ACTION_FIND */
 
 				break;
 			}
 	}
 
-	if (found)
-	{
-		/* update statistics */
-		if (action == RT_ACTION_DELETE)
-			node->count--;
-
+#if defined(RT_ACTION_FIND)
 #ifdef RT_NODE_LEVEL_LEAF
-		if (value_p)
-			*value_p = value;
+	Assert(value_p != NULL);
+	*value_p = value;
 #else
-		if (child_p)
-			*child_p = child;
+	Assert(child_p != NULL);
+	*child_p = child;
 #endif
-	}
+#elif defined (RT_ACTION_DELETE)
+	/* update statistics */
+	node->count--;
+#endif			/* RT_ACTION_FIND */
 
-	return found;
+	return true;
 
 #undef RT_NODE4_TYPE
 #undef RT_NODE32_TYPE
-- 
2.38.1