The patch titled Subject: maple_tree: mtree_range_walk() clean up has been added to the -mm mm-unstable branch. Its filename is maple_tree-mtree_range_walk-clean-up.patch This patch will shortly appear at https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-mtree_range_walk-clean-up.patch This patch will later appear in the mm-unstable branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm Before you just go and hit "reply", please: a) Consider who else should be cc'ed b) Prefer to cc a suitable mailing list as well c) Ideally: find the original patch on the mailing list and do a reply-to-all to that, adding suitable additional cc's *** Remember to use Documentation/process/submit-checklist.rst when testing your code *** The -mm tree is included into linux-next via the mm-everything branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm and is updated there every 2-3 working days ------------------------------------------------------ From: "Liam R. Howlett" <Liam.Howlett@xxxxxxxxxx> Subject: maple_tree: mtree_range_walk() clean up Date: Wed, 1 Nov 2023 13:16:29 -0400 mtree_range_walk() needed to be updated to avoid checking if there was a pivot value. On closer examination, the code could avoid setting min or max in certain scenarios. The commit removes the extra check for pivot[offset] before setting max and only sets max when necessary. It also only sets min if it is necessary by checking offset 0 prior to the loop (as it has always done). The commit also drops a dead node check since the end of the node will return the array size when the last slot is occupied (by a potential reuse in a dead node). The data will be discarded later if the node is marked dead. Benchmarking these changes results in an increase in performance of 5.45% using the BENCH_WALK in the maple tree test code. Link: https://lkml.kernel.org/r/20231101171629.3612299-13-Liam.Howlett@xxxxxxxxxx Signed-off-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx> Cc: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx> --- lib/maple_tree.c | 27 ++++++++++++--------------- 1 file changed, 12 insertions(+), 15 deletions(-) --- a/lib/maple_tree.c~maple_tree-mtree_range_walk-clean-up +++ a/lib/maple_tree.c @@ -2806,32 +2806,29 @@ static inline void *mtree_range_walk(str min = mas->min; max = mas->max; do { - offset = 0; last = next; node = mte_to_node(next); type = mte_node_type(next); pivots = ma_pivots(node, type); end = ma_data_end(node, type, pivots, max); - if (unlikely(ma_dead_node(node))) - goto dead_node; - - if (pivots[offset] >= mas->index) { - prev_max = max; - prev_min = min; - max = pivots[offset]; + prev_min = min; + prev_max = max; + if (pivots[0] >= mas->index) { + offset = 0; + max = pivots[0]; goto next; } - do { + offset = 1; + while (offset < end) { + if (pivots[offset] >= mas->index) { + max = pivots[offset]; + break; + } offset++; - } while ((offset < end) && (pivots[offset] < mas->index)); + } - prev_min = min; min = pivots[offset - 1] + 1; - prev_max = max; - if (likely(offset < end && pivots[offset])) - max = pivots[offset]; - next: slots = ma_slots(node, type); next = mt_slot(mas->tree, slots, offset); _ Patches currently in -mm which might be from Liam.Howlett@xxxxxxxxxx are maple_tree-remove-unnecessary-default-labels-from-switch-statements.patch maple_tree-make-mas_erase-more-robust.patch maple_tree-move-debug-check-to-__mas_set_range.patch maple_tree-add-end-of-node-tracking-to-the-maple-state.patch maple_tree-use-cached-node-end-in-mas_next.patch maple_tree-use-cached-node-end-in-mas_destroy.patch maple_tree-clean-up-inlines-for-some-functions.patch maple_tree-separate-ma_state-node-from-status.patch maple_tree-separate-ma_state-node-from-status-fix-1.patch maple_tree-separate-ma_state-node-from-status-fix-2.patch maple_tree-remove-mas_searchable.patch maple_tree-use-maple-state-end-for-write-operations.patch maple_tree-dont-find-node-end-in-mtree_lookup_walk.patch maple_tree-mtree_range_walk-clean-up.patch