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

["Liam R. Howlett" <Liam.Howlett@oracle.com>]

* Dev Jain <dev.jain@arm.com> [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@arm.com>
> ---
>  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.

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).

Thanks,
Liam