[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <58be76a0-8fc3-4d5d-959e-eabe7664e277@arm.com>
Date: Sat, 28 Jun 2025 17:27:56 +0530
From: Dev Jain <dev.jain@....com>
To: "Liam R. Howlett" <Liam.Howlett@...cle.com>, akpm@...ux-foundation.org,
richard.weiyang@...il.com, maple-tree@...ts.infradead.org,
linux-mm@...ck.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 1/2] maple tree: Clean up mtree_range_walk()
On 27/06/25 1:28 am, Liam R. Howlett wrote:
> * Dev Jain <dev.jain@....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@....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.
My understanding of the tree currently is that ma_root is a single slot.
Or can it be a normal node with 31 slots?
>
> 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).
Thank you for your detailed explanation. I will have to read more to
understand what you have written : )
>
> Thanks,
> Liam
Powered by blists - more mailing lists