Does mtree_lookup_walk need to use ma_data_end?

[Peng Zhang]

在 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
>