Does mtree_lookup_walk need to use ma_data_end?

[Liam R. Howlett]

* Liam R. Howlett <Liam.Howlett at Oracle.com> [231027 10:25]:
> * Omar Sandoval <osandov at osandov.com> [231026 20:16]:
> > Hi,
> > 
> > I'm reading some of the maple tree code in order to write drgn helpers
> > for maple trees, and I was hoping for some clarification on one bit of
> > code. Specifically, in mtree_lookup_walk:
> > 
> > 	end = ma_data_end(node, type, pivots, max);
> > 	...
> > 	do {
> > 		if (pivots[offset] >= mas->index) {
> > 			max = pivots[offset];
> > 			break;
> > 		}
> > 	} while (++offset < end);
> > 
> > So this is looping until the first pivot greater than or equal to the
> > desired index, stopping after it has checked the last pivot.
> > 
> > But we're guaranteed that either the last pivot or the implied maximum
> > is greater than or equal to the index, so is it necessary to get the
> > actual end with ma_data_end? I.e., would the following be equivalent?
> > 
> > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > index bb24d84a4922..18297c6ed06f 100644
> > --- a/lib/maple_tree.c
> > +++ b/lib/maple_tree.c
> > @@ -3739,7 +3739,7 @@ static inline void *mtree_lookup_walk(struct ma_state *mas)
> >  		node = mte_to_node(next);
> >  		type = mte_node_type(next);
> >  		pivots = ma_pivots(node, type);
> > -		end = ma_data_end(node, type, pivots, max);
> > +		end = mt_pivots[type];
> >  		if (unlikely(ma_dead_node(node)))
> >  			goto dead_node;
> >  		do {
> > 
> > I have no idea whether this is any better or faster. I guess it does
> > avoid a few branches and loads in ma_data_end. I'm mainly wondering
> > whether there's something I'm missing in my understanding.
> 
> Your analysis looks correct.  This is probably the case elsewhere in
> recent code as well (mas_range_walk(), probably).
> 

I have been looking at caching the end of the node in the maple state
for the benefit of the mas_for_each() loops, and so I have begin to use
the end variable after the loop you are updating.

On benchmarking, it seems it's actually better to use the ma_data_end()
call than to look at the mt_pivots[type], in my testing.  I suspect this
is locality of reference and instruction speed over array lookup in the
.text.


Thanks,
Liam