| Message ID | 20241114170524.64391-5-sidhartha.kumar@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Track node vacancy to reduce worst case allocation counts | expand |
On Thu, Nov 14, 2024 at 12:05:23PM -0500, Sidhartha Kumar wrote: >This allows support for using the vacant height to calculate the worst >case number of nodes needed for wr_rebalance operation. >mas_spanning_rebalance() was seen to perform unnecessary node allocations. >We can reduce allocations by breaking early during the rebalancing loop >once we realize that we have ascended to a common ancestor. > >Suggested-by: Liam Howlett <liam.howlett@oracle.com> >Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com> I am just about to send a similar patch :-) Reviewed-by: Wei Yang <richard.weiyang@gmail.com>
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f14d70c171c2..59c5c3f8db30 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2904,11 +2904,21 @@ static void mas_spanning_rebalance(struct ma_state *mas, mast_combine_cp_right(mast); mast->orig_l->last = mast->orig_l->max; - if (mast_sufficient(mast)) - continue; + if (mast_sufficient(mast)) { + if (mast_overflow(mast)) + continue; + + if (mast->orig_l->node == mast->orig_r->node) { + /* + * The data in b_node should be stored in one + * node and in the tree + */ + slot = mast->l->offset; + break; + } - if (mast_overflow(mast)) continue; + } /* May be a new root stored in mast->bn */ if (mas_is_root_limits(mast->orig_l))
This allows support for using the vacant height to calculate the worst case number of nodes needed for wr_rebalance operation. mas_spanning_rebalance() was seen to perform unnecessary node allocations. We can reduce allocations by breaking early during the rebalancing loop once we realize that we have ascended to a common ancestor. Suggested-by: Liam Howlett <liam.howlett@oracle.com> Signed-off-by: Sidhartha Kumar <sidhartha.kumar@oracle.com> --- lib/maple_tree.c | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-)