v21-0011-Expand-commentary-for-kinds-vs.-size-classes.patch

From 8711b9afb019ba45a5c4c3e2ec41f72130208a68 Mon Sep 17 00:00:00 2001
From: John Naylor <john.naylor@postgresql.org>
Date: Sat, 21 Jan 2023 12:52:53 +0700
Subject: [PATCH v21 11/22] Expand commentary for kinds vs. size classes

Also move class enum closer to array and add #undef's
---
 src/include/lib/radixtree.h | 76 ++++++++++++++++++++++++++-----------
 1 file changed, 53 insertions(+), 23 deletions(-)

diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h
index 6cc8442c89..4a2dad82bf 100644
--- a/src/include/lib/radixtree.h
+++ b/src/include/lib/radixtree.h
@@ -288,22 +288,26 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree);
 #define BM_BIT(x)	((x) % BITS_PER_BITMAPWORD)
 
 /*
- * Supported radix tree node kinds and size classes.
+ * Node kinds
  *
- * There are 4 node kinds and each node kind have one or two size classes,
- * partial and full. The size classes in the same node kind have the same
- * node structure but have the different number of fanout that is stored
- * in 'fanout' of RT_NODE. For example in size class 15, when a 16th element
- * is to be inserted, we allocate a larger area and memcpy the entire old
- * node to it.
+ * The different node kinds are what make the tree "adaptive".
  *
- * This technique allows us to limit the node kinds to 4, which limits the
- * number of cases in switch statements. It also allows a possible future
- * optimization to encode the node kind in a pointer tag.
+ * Each node kind is associated with a different datatype and different
+ * search/set/delete/iterate algorithms adapted for its size. The largest
+ * kind, node256 is basically the same as a traditional radix tree,
+ * and would be most wasteful of memory when sparsely populated. The
+ * smaller nodes expend some additional CPU time to enable a smaller
+ * memory footprint.
  *
- * These size classes have been chose carefully so that it minimizes the
- * allocator padding in both the inner and leaf nodes on DSA.
- * node
+ * XXX There are 4 node kinds, and this should never be increased,
+ * for several reasons:
+ * 1. With 5 or more kinds, gcc tends to use a jump table for switch
+ *    statments.
+ * 2. The 4 kinds can be represented with 2 bits, so we have the option
+ *    in the future to tag the node pointer with the kind, even on
+ *    platforms with 32-bit pointers. This might speed up node traversal
+ *    in trees with highly random node kinds.
+ * 3. We can have multiple size classes per node kind.
  */
 #define RT_NODE_KIND_3			0x00
 #define RT_NODE_KIND_32			0x01
@@ -320,16 +324,6 @@ RT_SCOPE void RT_STATS(RT_RADIX_TREE *tree);
 
 #endif							/* RT_COMMON */
 
-
-typedef enum RT_SIZE_CLASS
-{
-	RT_CLASS_3_FULL = 0,
-	RT_CLASS_32_PARTIAL,
-	RT_CLASS_32_FULL,
-	RT_CLASS_125_FULL,
-	RT_CLASS_256
-} RT_SIZE_CLASS;
-
 /* Common type for all nodes types */
 typedef struct RT_NODE
 {
@@ -508,6 +502,37 @@ typedef struct RT_NODE_LEAF_256
 	RT_VALUE_TYPE	values[RT_NODE_MAX_SLOTS];
 } RT_NODE_LEAF_256;
 
+/*
+ * Node size classes
+ *
+ * Nodes of different kinds necessarily belong to different size classes.
+ * The main innovation in our implementation compared to the ART paper
+ * is decoupling the notion of size class from kind.
+ *
+ * The size classes within a given node kind have the same underlying
+ * type, but a variable number of children/values. This is possible
+ * because the base type contains small fixed data structures that
+ * work the same way regardless of how full the node is. We store the
+ * node's allocated capacity in the "fanout" member of RT_NODE, to allow
+ * runtime introspection.
+ *
+ * Growing from one node kind to another requires special code for each
+ * case, but growing from one size class to another within the same kind
+ * is basically just allocate + memcpy.
+ *
+ * The size classes have been chosen so that inner nodes on platforms
+ * with 64-bit pointers (and leaf nodes when using a 64-bit key) are
+ * equal to or slightly smaller than some DSA size class.
+ */
+typedef enum RT_SIZE_CLASS
+{
+	RT_CLASS_3_FULL = 0,
+	RT_CLASS_32_PARTIAL,
+	RT_CLASS_32_FULL,
+	RT_CLASS_125_FULL,
+	RT_CLASS_256
+} RT_SIZE_CLASS;
+
 /* Information for each size class */
 typedef struct RT_SIZE_CLASS_ELEM
 {
@@ -2217,6 +2242,7 @@ RT_DUMP(RT_RADIX_TREE *tree)
 #undef NODE_IS_EMPTY
 #undef VAR_NODE_HAS_FREE_SLOT
 #undef FIXED_NODE_HAS_FREE_SLOT
+#undef RT_NODE_KIND_COUNT
 #undef RT_SIZE_CLASS_COUNT
 #undef RT_RADIX_TREE_MAGIC
 
@@ -2229,6 +2255,10 @@ RT_DUMP(RT_RADIX_TREE *tree)
 #undef RT_ITER
 #undef RT_NODE
 #undef RT_NODE_ITER
+#undef RT_NODE_KIND_3
+#undef RT_NODE_KIND_32
+#undef RT_NODE_KIND_125
+#undef RT_NODE_KIND_256
 #undef RT_NODE_BASE_3
 #undef RT_NODE_BASE_32
 #undef RT_NODE_BASE_125
-- 
2.39.0