Received-SPF: pass (google.com: domain of linux-kernel+bounces-562-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3;
From: Peng Zhang <zhangpeng.00@bytedance.com>
To: Liam.Howlett@oracle.com,
	akpm@linux-foundation.org
Cc: linux-kernel@vger.kernel.org,
	linux-mm@kvack.org,
	maple-tree@lists.infradead.org,
	Peng Zhang <zhangpeng.00@bytedance.com>
Subject: [PATCH] maple_tree: Avoid checking other gaps after getting the largest gap
Date: Fri, 15 Dec 2023 15:46:32 +0800
Message-Id: <20231215074632.82045-1-zhangpeng.00@bytedance.com>
Precedence: bulk
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit

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

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