Re: [PATCH 1/2] maple tree: Clean up mtree_range_walk()

[Dev Jain]

On 27/06/25 1:28 am, Liam R. Howlett wrote:
> * Dev Jain <dev.jain@xxxxxxx> [250626 13:19]:
> > The special casing for offset == 0 is being done because min will stay
> > mas->min in this case. So refactor the code to use the while loop for
> > setting the max and getting the corresponding offset, and only set the
> > min for offset > 0.
> >
> > Signed-off-by: Dev Jain <dev.jain@xxxxxxx>
> > ---
> >   lib/maple_tree.c | 11 +++--------
> >   1 file changed, 3 insertions(+), 8 deletions(-)
> >
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index 0e85e92c5375..6c89e6790fb5 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -2770,13 +2770,8 @@ static inline void *mtree_range_walk(struct ma_state *mas)
> >   		end = ma_data_end(node, type, pivots, max);
> >   		prev_min = min;
> >   		prev_max = max;
> > -		if (pivots[0] >= mas->index) {
> > -			offset = 0;
> > -			max = pivots[0];
> > -			goto next;
> > -		}
> >   
> This new line should be dropped.
>
> > -		offset = 1;
> > +		offset = 0;
> >   		while (offset < end) {
> This should now be a do {} while();
>
> >   			if (pivots[offset] >= mas->index) {
> >   				max = pivots[offset];
> > @@ -2784,9 +2779,9 @@ static inline void *mtree_range_walk(struct ma_state *mas)
> >   			}
> >   			offset++;
> >   		}
> There should be a new line here.
>
> > +		if (likely(offset))
> > +			min = pivots[offset - 1] + 1;
> >   
> > -		min = pivots[offset - 1] + 1;
> > -next:
> >   		slots = ma_slots(node, type);
> >   		next = mt_slot(mas->tree, slots, offset);
> >   		if (unlikely(ma_dead_node(node)))
> > --
> > 2.30.2
> The current way will check pivot 0, then skip the main loop.  Pivot 0
> has an equal chance of being the range you are looking for, but that
> probability increases based on a lower number of entries in the node.
> The root node, which we always pass through, can have as little as two
> entries, so then it's 50/50 you want pivot 0.

My understanding of the tree currently is that ma_root is a single slot.
Or can it be a normal node with 31 slots?

> With the way you've written it, it will check offset < end (which will
> always be the case for the first time), then do the same work as the
> out-of-loop check, then check offset an extra time after the loop.
>
> If it's written with a do {} while, the initial check of offset < end is
> avoided, but you will end up checking offset an extra time to see if min
> needs to be set.
>
> If pivot 0 is NOT the entry you want, then the current code will check
> pivot 0, then execute the loop one less time.  In the even of a root
> node with 2 entries, it will not enter the loop at all.
>
> So, the way it is written is less code execution by avoiding unnecessary
> assignment of min and checks (of offset == 0 and offset < end).

Thank you for your detailed explanation. I will have to read more to
understand what you have written : )

> Thanks,
> Liam