* Wei Yang <richard.weiyang@xxxxxxxxx> [240904 10:53]:
> On Wed, Sep 04, 2024 at 07:58:19AM +0000, Wei Yang wrote:
> [...]
> >>It is only changing code for the sake of changing code. And it looks
> >>like it will be slower, or the same speed if we are lucky. I have to
> >>take time to verify things aren't slower or add subtle issues (maybe an
> >>RCU race) because the code looked similar. It's just not worth it.
> >>
> >
> >I am trying to make the code more easy to read, but seems not helping.
> >
> >BTW, I found in mas_update_gap(), if (p_gap != max_gap), we would access
> >the first parent, parent's type and its gap twice. Once in mas_update_gap()
> >and once in mas_parent_gap().
> >
> >Do you think it worth a change to reduce one?
> >
>
> Liam,
>
> I am trying to understand what kind code change you don't like.
Any change that cleans things up and verifies the performance would be
acceptable, but your previous changes didn't do that so the burden is on
me to verify that your code isn't going to cause a regression.
>
> Is the following change worth?
Not like it is right now, but this is worth fixing.
Test using the tools/test/radix-tree/maple.c Look in that file for
BENCH defines at the top, and examples of the benchmarking.
Before you submit anything, run the testing to make sure it all passes.
If you are changing anything for cleanup/optimisation, then write a
benchmark that will test the runtime, add that before your change and
run it in both before/after with the results.
Look also into the perf tool to see what is going on and where your time
is spent, then you can avoid optimising something that's not worth
optimising.
>
> diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> index 2b310dd3addf..e331d086eb7c 100644
> --- a/lib/maple_tree.c
> +++ b/lib/maple_tree.c
> @@ -1595,32 +1595,33 @@ static inline unsigned long mas_max_gap(struct ma_state *mas)
> /*
> * mas_parent_gap() - Set the parent gap and any gaps above, as needed
> * @mas: The maple state
> - * @offset: The gap offset in the parent to set
> * @new: The new gap value.
> *
> * Set the parent gap then continue to set the gap upwards, using the metadata
> * of the parent to see if it is necessary to check the node above.
> */
> -static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
> - unsigned long new)
> +static inline void mas_parent_gap(struct ma_state *mas, unsigned long new)
> {
> unsigned long meta_gap = 0;
> struct maple_node *pnode;
> - struct maple_enode *penode;
> + struct maple_enode *enode = mas->node;
Set this with the rest of the configuration, before the ascend label
would make more sense and be more clear.
> unsigned long *pgaps;
> - unsigned char meta_offset;
> + unsigned char offset, meta_offset;
Make this two lines.
> enum maple_type pmt;
>
> - pnode = mte_parent(mas->node);
> - pmt = mas_parent_type(mas, mas->node);
> - penode = mt_mk_node(pnode, pmt);
> +ascend:
> + pnode = mte_parent(enode);
> + pmt = mas_parent_type(mas, enode);
> + offset = mte_parent_slot(enode);
> pgaps = ma_gaps(pnode, pmt);
>
> -ascend:
> MAS_BUG_ON(mas, pmt != maple_arange_64);
> meta_offset = ma_meta_gap(pnode);
> meta_gap = pgaps[meta_offset];
>
> + if (pgaps[offset] == new)
> + return;
> +
So every time we go up a level in the tree, we will now check if the
offset gap is the same as the new gap? Doesn't this mean every level
now has an extra check that was previously only done for the first
level? This is an unreasonable trade off.
I don't like what is there today, but I don't see this as a meaningful
improvement and I suspect this extra check is going to cost more than
the extra hot-cache check that exists today.
> pgaps[offset] = new;
>
> if (meta_gap == new)
> @@ -1640,11 +1641,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
> return;
>
> /* Go to the parent node. */
> - pnode = mte_parent(penode);
> - pmt = mas_parent_type(mas, penode);
> - pgaps = ma_gaps(pnode, pmt);
> - offset = mte_parent_slot(penode);
> - penode = mt_mk_node(pnode, pmt);
> + enode = mt_mk_node(pnode, pmt);
Essentially, you have replaced the penode with enode and reversed the
order of setting things up. This seems reasonable, as it reduces the
lines of code.
If you undo this change, you can move the check back outside the loop
and avoid checking it every iteration and avoid the double check you are
trying to avoid.
> goto ascend;
> }
>
> @@ -1654,24 +1651,13 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset,
> */
> static inline void mas_update_gap(struct ma_state *mas)
> {
> - unsigned char pslot;
> - unsigned long p_gap;
> - unsigned long max_gap;
> -
> if (!mt_is_alloc(mas->tree))
> return;
>
> if (mte_is_root(mas->node))
> return;
>
> - max_gap = mas_max_gap(mas);
> -
> - pslot = mte_parent_slot(mas->node);
> - p_gap = ma_gaps(mte_parent(mas->node),
> - mas_parent_type(mas, mas->node))[pslot];
> -
> - if (p_gap != max_gap)
> - mas_parent_gap(mas, pslot, max_gap);
> + mas_parent_gap(mas, mas_max_gap(mas));
This was optimised to skip updating the parent if we don't need to - and
the parent update was called elsewhere in the past. Since there's not
much here, we can probably delete this function and rename the
mas_parent_gap() with the two tests here for mt_is_alloc() and
mte_is_root().
...
Thanks,
Liam
