The patch titled
Subject: maple_tree: avoid checking other gaps after getting the largest gap
has been added to the -mm mm-unstable branch. Its filename is
maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap.patch
This patch will later appear in the mm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via the mm-everything
branch at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there every 2-3 working days
------------------------------------------------------
From: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx>
Subject: maple_tree: avoid checking other gaps after getting the largest gap
Date: Fri, 15 Dec 2023 15:46:32 +0800
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.
Link: https://lkml.kernel.org/r/20231215074632.82045-1-zhangpeng.00@xxxxxxxxxxxxx
Signed-off-by: Peng Zhang <zhangpeng.00@xxxxxxxxxxxxx>
Cc: Liam R. Howlett <Liam.Howlett@xxxxxxxxxx>
Signed-off-by: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
---
lib/maple_tree.c | 3 +++
1 file changed, 3 insertions(+)
--- a/lib/maple_tree.c~maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap
+++ a/lib/maple_tree.c
@@ -1518,6 +1518,9 @@ static unsigned long mas_leaf_max_gap(st
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++) {
_
Patches currently in -mm which might be from zhangpeng.00@xxxxxxxxxxxxx are
maple_tree-avoid-checking-other-gaps-after-getting-the-largest-gap.patch
