Does mtree_lookup_walk need to use ma_data_end?

[Liam R. Howlett]

* Peng Zhang <zhangpeng.00 at bytedance.com> [231029 23:25]:
> 
> 
> 在 2023/10/28 03:43, 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.
> The reason we can do it now is because the commit
> 3c769fd88 (maple_tree: set the node limit when creating a new root node)
> added the node limit to the root node. Before this, we couldn't do it this
> way and had to obtain the node limit through 'max'. I was planning to remove
> this 'max' variable earlier, but I haven't sent the code to the email list yet.

Thanks Peng.  I have this as part of a patch set I'm preparing now so
don't worry about it.

Cheers,
Liam