Re: [PATCH v2] maple_tree: simplify mas_wr_node_walk for improved readability

[Hao Li <haoli.tcs@gmail.com>]

On Fri, Aug 23, 2024 at 01:51:28PM -0400, Liam R. Howlett wrote:
> * Hao Li <haoli.tcs@gmail.com> [240823 05:38]:
> > On Fri, Aug 23, 2024 at 05:07:31PM +0800, Peng Zhang wrote:
> > > 
> > > 
> > > 在 2024/8/23 16:17, Hao Li 写道:
> > > > Refactor mas_wr_node_walk to make the code more clear and easier to
> > > > understand. The main changes are:
> 
> Thank you for your patch, but I don't think this is a good change.

Thank you for taking the time to review my patch and provide detailed feedback.

> 
> NACK
> 
> > > > 
> > > > 1. Replace the forward-iterating loop with a backward-iterating loop.
> > > >   This simplifies the logic for determining the correct range
> > > >   containing mas->index.
> > > I don't think iterating in reverse is a good idea, it makes the code
> > > different from everywhere else.
> > 
> 
> I also agree with Peng that having one loop go a different way seems
> like it's asking for trouble.
> 
> > I understand your concern about consistency in iteration direction.
> > 
> > While the original code correctly handled all cases, the process wasn't
> > as definitive or clear.
> > 
> > The new approach unifies the logic by eliminating the need to treat
> > `offset >= count` as a special case. This results in a more
> > straightforward and consistent flow throughout the function, which
> > provides a more deterministic and easy-to-follow path through the logic.
> > We can more clearly see and understand how we're determining the correct
> > range for `mas->index` without having to mentally parse complex
> > conditional logic.
> > 
> > > > 
> > > > 2. Eliminate the ternary operator.
> 
> This is not more clear as one may miss that the loop may not execute at
> all. So you eliminated the ternary operator, but have all but hidden the
> assignment.  I would rather an if/else for verbosity, but not enough to
> reject the patch that added it in the first place.

Got it!

> 
> You also replaced the "unsigned char count" with an "int idx", for some
> reason.  It seems like you've rewritten it so it's more clear for you.
> 
> > > > 
> > > > The new implementation maintains the same functionality as before, but
> > > > with improved readability. The performance characteristics remain
> > > > essentially the same, as we cannot predict which interval mas->index
> > > > will fall into.
> 
> We do favour the left side of the tree to increase data density, so it
> is more likely to find what we are looking for in the lower slots (but
> not by a whole lot right now). There will probably be more of this
> favouring in the future - minimum span for internal nodes.

Got it.

> 
> BENCH_NODE_STORE went from 8.79, 8.85, 8.79 seconds to 9.68, 9.74, 9.72.
> This change is slower.  It may be because you removed all the temporary
> variables that avoided dereferencing, so the compiler can't be as smart
> about optimisation.  I'm not really interested in finding out why it's
> slower as I don't think this is a good change on the grounds of other
> reasons stated as well.

Thanks for this benchmarking, I didn't even realize this performance
regression.


Regards,
Hao Li
> 
> Thanks,
> Liam
> 
> > > > 
> > > > Signed-off-by: Hao Li <haoli.tcs@gmail.com>
> > > > ---
> > > >   lib/maple_tree.c | 18 ++++++++----------
> > > >   1 file changed, 8 insertions(+), 10 deletions(-)
> > > > 
> > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > > index fe1b01b29..0b3eb55d8 100644
> > > > --- a/lib/maple_tree.c
> > > > +++ b/lib/maple_tree.c
> > > > @@ -2203,7 +2203,7 @@ static inline void mas_node_or_none(struct ma_state *mas,
> > > >   static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
> > > >   {
> > > >   	struct ma_state *mas = wr_mas->mas;
> > > > -	unsigned char count, offset;
> > > > +	int idx;
> > > >   	if (unlikely(ma_is_dense(wr_mas->type))) {
> > > >   		wr_mas->r_max = wr_mas->r_min = mas->index;
> > > > @@ -2213,16 +2213,14 @@ static inline void mas_wr_node_walk(struct ma_wr_state *wr_mas)
> > > >   	wr_mas->node = mas_mn(wr_mas->mas);
> > > >   	wr_mas->pivots = ma_pivots(wr_mas->node, wr_mas->type);
> > > > -	count = mas->end = ma_data_end(wr_mas->node, wr_mas->type,
> > > > +	mas->end = ma_data_end(wr_mas->node, wr_mas->type,
> > > >   				       wr_mas->pivots, mas->max);
> > > > -	offset = mas->offset;
> > > > -
> > > > -	while (offset < count && mas->index > wr_mas->pivots[offset])
> > > > -		offset++;
> > > > -
> > > > -	wr_mas->r_max = offset < count ? wr_mas->pivots[offset] : mas->max;
> > > > -	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, offset);
> > > > -	wr_mas->offset_end = mas->offset = offset;
> > > > +	wr_mas->r_max = mas->max;
> > > > +	idx = mas->end - 1;
> > > > +	while (idx >= mas->offset && wr_mas->pivots[idx] >= mas->index)
> > > > +		wr_mas->r_max = wr_mas->pivots[idx--];
> > > > +	wr_mas->offset_end = mas->offset = idx + 1;
> > > > +	wr_mas->r_min = mas_safe_min(mas, wr_mas->pivots, mas->offset);
> > > >   }
> > > >   /*