diff mbox series

maple_tree: Avoid checking other gaps after getting the largest gap

Message ID 20231215074632.82045-1-zhangpeng.00@bytedance.com
State New
Headers
Series maple_tree: Avoid checking other gaps after getting the largest gap |

Commit Message

Peng Zhang Dec. 15, 2023, 7:46 a.m. UTC 
  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.

Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
---
 lib/maple_tree.c | 3 +++
 1 file changed, 3 insertions(+)

Comments

Liam R. Howlett Dec. 18, 2023, 8:20 p.m. UTC | #1 
* Peng Zhang <zhangpeng.00@bytedance.com> [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.

> 
> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>

Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>

> ---
>  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
>
Liam R. Howlett Dec. 18, 2023, 8:28 p.m. UTC | #2 
* Liam R. Howlett <Liam.Howlett@Oracle.com> [231218 15:20]:
> * Peng Zhang <zhangpeng.00@bytedance.com> [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@bytedance.com>
> 
> Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> 
> > ---
> >  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
> >
Peng Zhang Dec. 19, 2023, 2:34 a.m. UTC | #3 
在 2023/12/19 04:28, Liam R. Howlett 写道:
> * Liam R. Howlett <Liam.Howlett@Oracle.com> [231218 15:20]:
>> * Peng Zhang <zhangpeng.00@bytedance.com> [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)?
Yes, only for right-most nodes and root.
>>
>> 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.
I think that the first slot in a node does not have any special
significance. It has a lower probability of being the largest gap,
so it may not be worth considering.
> 
>>
>>>
>>> Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
>>
>> Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
>>
>>> ---
>>>   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
>>>
>
Liam R. Howlett Dec. 19, 2023, 9:14 a.m. UTC | #4 
* Peng Zhang <zhangpeng.00@bytedance.com> [231218 21:34]:
> 
> 
> 在 2023/12/19 04:28, Liam R. Howlett 写道:
> > * Liam R. Howlett <Liam.Howlett@Oracle.com> [231218 15:20]:
> > > * Peng Zhang <zhangpeng.00@bytedance.com> [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)?
> Yes, only for right-most nodes and root.
> > > 
> > > 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.
> I think that the first slot in a node does not have any special
> significance. It has a lower probability of being the largest gap,
> so it may not be worth considering.

It has a higher probability of being a gap, but since there is a special
case for it already it won't be checked unless it is a gap.

The left-most node at each level will probably exhibit the same larger
gap in practice except for the root where it will the be end gap - at
least on x86.

Since these will be hit-cache I'm not sure either will make much of a
practical difference though.

> > 
> > > 
> > > > 
> > > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > > 
> > > Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> > > 
> > > > ---
> > > >   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
> > > > 
> >
diff mbox series

Patch

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++) {