* Liam R. Howlett <Liam.Howlett@xxxxxxxxxx> [231218 15:20]: > * Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> [231215 02:46]: > > The last range stored in maple tree is typically quite large. By > > checking if it exceeds the sum of the remaining ranges in that node, it > > is possible to avoid checking all other gaps. > > > > Running the maple tree test suite in user mode almost always results in > > a near 100% hit rate for this optimization. > > This should only be triggered for right-most nodes and root though, > correct (mas->max == ULONG_MAX from just before this)? > > I wonder if it's worth special case checking the first gap if the node > min is 0 as well. Might be worth looking at, but this patch is > certainly worth doing. Actually, not just when the min is 0, we have a special case close to here for slot 0 so we could just check the same sort of thing there. > > > > > Signed-off-by: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx> > > Reviewed-by: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx> > > > --- > > lib/maple_tree.c | 3 +++ > > 1 file changed, 3 insertions(+) > > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > > index c9a970ea20dd..6f241bb38799 100644 > > --- a/lib/maple_tree.c > > +++ b/lib/maple_tree.c > > @@ -1518,6 +1518,9 @@ static unsigned long mas_leaf_max_gap(struct ma_state *mas) > > gap = ULONG_MAX - pivots[max_piv]; > > if (gap > max_gap) > > max_gap = gap; > > + > > + if (max_gap > pivots[max_piv] - mas->min) > > + return max_gap; > > } > > > > for (; i <= max_piv; i++) { > > -- > > 2.20.1 > >