Messages in this thread | | | Date | Tue, 19 Dec 2023 10:34:36 +0800 | Subject | Re: [PATCH] maple_tree: Avoid checking other gaps after getting the largest gap | From | Peng Zhang <> |
| |
在 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 >>> >
| |