From 6831fe27a2c9c5765113b7903403c426f09f55f6 Mon Sep 17 00:00:00 2001 From: John Naylor Date: Mon, 6 Feb 2023 22:04:50 +0700 Subject: [PATCH v26 7/9] Skip unnecessary searches in RT_NODE_INSERT_INNER For inner nodes, we know the key chunk doesn't exist already, otherwise we would have found it while descending the tree. To reinforce this fact, declare this function to return void. --- src/include/lib/radixtree.h | 4 +-- src/include/lib/radixtree_insert_impl.h | 48 ++++++++++++------------- 2 files changed, 24 insertions(+), 28 deletions(-) diff --git a/src/include/lib/radixtree.h b/src/include/lib/radixtree.h index 4bd0aaa810..1cdb995e54 100644 --- a/src/include/lib/radixtree.h +++ b/src/include/lib/radixtree.h @@ -685,7 +685,7 @@ typedef struct RT_ITER } RT_ITER; -static bool RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node, +static void RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node, uint64 key, RT_PTR_ALLOC child); static bool RT_NODE_INSERT_LEAF(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node, uint64 key, RT_VALUE_TYPE *value_p); @@ -1375,7 +1375,7 @@ RT_NODE_DELETE_LEAF(RT_PTR_LOCAL node, uint64 key) * If the node we're inserting into needs to grow, we update the parent's * child pointer with the pointer to the new larger node. */ -static bool +static void RT_NODE_INSERT_INNER(RT_RADIX_TREE *tree, RT_PTR_LOCAL parent, RT_PTR_ALLOC stored_node, RT_PTR_LOCAL node, uint64 key, RT_PTR_ALLOC child) { diff --git a/src/include/lib/radixtree_insert_impl.h b/src/include/lib/radixtree_insert_impl.h index c18e26b537..d56e58dcac 100644 --- a/src/include/lib/radixtree_insert_impl.h +++ b/src/include/lib/radixtree_insert_impl.h @@ -28,10 +28,10 @@ #endif uint8 chunk = RT_GET_KEY_CHUNK(key, node->shift); - bool chunk_exists = false; #ifdef RT_NODE_LEVEL_LEAF const bool is_leaf = true; + bool chunk_exists = false; Assert(RT_NODE_IS_LEAF(node)); #else const bool is_leaf = false; @@ -43,21 +43,18 @@ case RT_NODE_KIND_3: { RT_NODE3_TYPE *n3 = (RT_NODE3_TYPE *) node; - int idx; - idx = RT_NODE_3_SEARCH_EQ(&n3->base, chunk); +#ifdef RT_NODE_LEVEL_LEAF + int idx = RT_NODE_3_SEARCH_EQ(&n3->base, chunk); + if (idx != -1) { /* found the existing chunk */ chunk_exists = true; -#ifdef RT_NODE_LEVEL_LEAF n3->values[idx] = *value_p; -#else - n3->children[idx] = child; -#endif break; } - +#endif if (unlikely(RT_NODE_MUST_GROW(n3))) { RT_PTR_ALLOC allocnode; @@ -113,21 +110,18 @@ { const RT_SIZE_CLASS_ELEM class32_max = RT_SIZE_CLASS_INFO[RT_CLASS_32_MAX]; RT_NODE32_TYPE *n32 = (RT_NODE32_TYPE *) node; - int idx; - idx = RT_NODE_32_SEARCH_EQ(&n32->base, chunk); +#ifdef RT_NODE_LEVEL_LEAF + int idx = RT_NODE_32_SEARCH_EQ(&n32->base, chunk); + if (idx != -1) { /* found the existing chunk */ chunk_exists = true; -#ifdef RT_NODE_LEVEL_LEAF n32->values[idx] = *value_p; -#else - n32->children[idx] = child; -#endif break; } - +#endif if (unlikely(RT_NODE_MUST_GROW(n32)) && n32->base.n.fanout < class32_max.fanout) { @@ -220,21 +214,19 @@ case RT_NODE_KIND_125: { RT_NODE125_TYPE *n125 = (RT_NODE125_TYPE *) node; - int slotpos = n125->base.slot_idxs[chunk]; + int slotpos; int cnt = 0; +#ifdef RT_NODE_LEVEL_LEAF + slotpos = n125->base.slot_idxs[chunk]; if (slotpos != RT_INVALID_SLOT_IDX) { /* found the existing chunk */ chunk_exists = true; -#ifdef RT_NODE_LEVEL_LEAF n125->values[slotpos] = *value_p; -#else - n125->children[slotpos] = child; -#endif break; } - +#endif if (unlikely(RT_NODE_MUST_GROW(n125))) { RT_PTR_ALLOC allocnode; @@ -300,14 +292,10 @@ #ifdef RT_NODE_LEVEL_LEAF chunk_exists = RT_NODE_LEAF_256_IS_CHUNK_USED(n256, chunk); -#else - chunk_exists = RT_NODE_INNER_256_IS_CHUNK_USED(n256, chunk); -#endif Assert(chunk_exists || node->count < RT_NODE_MAX_SLOTS); - -#ifdef RT_NODE_LEVEL_LEAF RT_NODE_LEAF_256_SET(n256, chunk, *value_p); #else + Assert(node->count < RT_NODE_MAX_SLOTS); RT_NODE_INNER_256_SET(n256, chunk, child); #endif break; @@ -315,8 +303,12 @@ } /* Update statistics */ +#ifdef RT_NODE_LEVEL_LEAF if (!chunk_exists) node->count++; +#else + node->count++; +#endif /* * Done. Finally, verify the chunk and value is inserted or replaced @@ -324,7 +316,11 @@ */ RT_VERIFY_NODE(node); +#ifdef RT_NODE_LEVEL_LEAF return chunk_exists; +#else + return; +#endif #undef RT_NODE3_TYPE #undef RT_NODE32_TYPE -- 2.39.1