Does mtree_lookup_walk need to use ma_data_end?

[Liam R. Howlett]

* Liam R. Howlett <Liam.Howlett at Oracle.com> [231027 15:30]:
> * 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.
> 

Sorry, the code I'm editing is mas_range_walk(), this one may be faster
the way you are writing it as the max variable is unnecessary then.