Received-SPF: pass (google.com: domain of linux-kernel+bounces-4352-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1;
Date: Mon, 18 Dec 2023 15:28:45 -0500
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To: Peng Zhang <zhangpeng.00@bytedance.com>, akpm@linux-foundation.org,
        linux-kernel@vger.kernel.org, linux-mm@kvack.org,
        maple-tree@lists.infradead.org
Subject: Re: [PATCH] maple_tree: Avoid checking other gaps after getting the
 largest gap
Message-ID: <20231218202845.buffbdq3vhpiv2py@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
	Peng Zhang <zhangpeng.00@bytedance.com>, akpm@linux-foundation.org,
	linux-kernel@vger.kernel.org, linux-mm@kvack.org,
	maple-tree@lists.infradead.org
References: <20231215074632.82045-1-zhangpeng.00@bytedance.com>
 <20231218202014.mpotsekdkszasn4t@revolver>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20231218202014.mpotsekdkszasn4t@revolver>
User-Agent: NeoMutt/20220429
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: 
	=?us-ascii?Q?/a5j5fUDz7SWfDzFr9gfSwG23rpUaBymy1PK1K1sot2S/xUsoA2qYi8kFzb/?=
 =?us-ascii?Q?+zI2B1tLx0FOyrdzZTrgQ5z3snNQ4eTdf8bEsdZrnlL2BINFldpR/Cwoa2OH?=
 =?us-ascii?Q?Vl0smcNQHbRTQrYB0CdP8vGz/9OsIDwFVHDjhuddzfZIjUL8VqZfeOk1Sa9C?=
 =?us-ascii?Q?gbI44pN2CCIT7lk5mPeqOYqfyqmqA3MuCvMr8E5AtElbb4+KXIZfrXGiKFbf?=
 =?us-ascii?Q?4mSv4vyqoxkAW93J8GXPziN22nfQjCxKjT0KethLCU1c8juLayjzn8Mvq/iO?=
 =?us-ascii?Q?mPKKObakxIyiAh3xU4KZy9Di1t4PcCzbeKs5osW5FTZbMp8SlJZgpMdHBnnC?=
 =?us-ascii?Q?8Z4aKlttZ+gem4pWmyH1zNfNxr+yoPgOctF4gNx2alf4rLAx0vAcfULLREZ9?=
 =?us-ascii?Q?Clf5EmUhdGwKipOZoFs4US5n5GPklPt2s6ailcH656PoS+GCcwdvYMw/jsqS?=
 =?us-ascii?Q?yh+WIDQdNnKFO9ucx6SXuNNStc6lClQv7ZiQjC3mbc+jnn6dE2IkKJEZjSLY?=
 =?us-ascii?Q?+3GRnCVPJ5OLZgmSIEe8ecyEy9fbBEQsZNLI6/pwnLtTk7sUoKs0Ijadjpn0?=
 =?us-ascii?Q?/a/Cqvz2NJMwrobvlQb0Ioe68Px7ajA26F46dxfv7jLYGtMqUK6AH01Ckqfx?=
 =?us-ascii?Q?xv4KgtNwWTfK7n2xT3+N24l/ex8nY+Zqx8AewUa7dQwf6nsrYAnmugbQPqs8?=
 =?us-ascii?Q?LyePfTTigD7SeyQ4LBO8bA1PbTclP308oaDGUFk+RHz/Y/k4l/LNCMOUIFtc?=
 =?us-ascii?Q?KDNufP8R8K93PjalBafJVFU5meZRoFNX5rlVHPgeIQ0TxII/DHKPIDsSMEEK?=
 =?us-ascii?Q?N0vktEpQGS6+k8aWdb9QtIBUfv8F9zSg90ZbwPjf0I5TRXzx18sO2MGl2GZD?=
 =?us-ascii?Q?/Q5JGDF/5hQchMEZMmCKf/4oWDFInoUejZZZbvXwch4CAdVvcL0eSR1qlUgH?=
 =?us-ascii?Q?pbjhPtRGE9QWigFwC6AXAkEbbV2G1WhASGfWhGpsjifkczzeII/HSWnDhQLc?=
 =?us-ascii?Q?g+CYWrokX9lGKLehFUe2XFu9IuLGDiIaLcKjIRt5wHwA+fm0GWSxkPLm5/cM?=
 =?us-ascii?Q?Ksl6zLapWisbNRThRM5an1+gZMCmOiVUUjKHQnqq8NVY7CuV73AlBYCBPY3Q?=
 =?us-ascii?Q?qZdy2mBq3qWXdpjtlV+5mcIDfjZnyBTA/7OSYBlZ4qocRpLko9A+kD/kilC8?=
 =?us-ascii?Q?Ot98PQOVqbFfZXYhd9xm1kE8OgRrH+/9tQSgmg9ngtoYEA2mEuSU+Yx6PIjK?=
 =?us-ascii?Q?CzB7iu9IGJjh8cvjl99y/m8tP2Fp+2upTQhSjtURREgSAukUPnW/XRxJQ9ZE?=
 =?us-ascii?Q?XnbZnvKxFRZSzDA1IwktzwJnJ8YRyYFQiCDanMpL9SI9ezGutSOOMuzXxhN5?=
 =?us-ascii?Q?DdcwljEtfeCU8PpJ2153KK7vUy2Ns5Sk5YQ9nwtgVNaiLH9HO1LRoYP72p06?=
 =?us-ascii?Q?lL0P45YLxcBLVra2GXYqWH8qOO/aISR3ENYD1qfEUGCq64thijn0V4dkyevu?=
 =?us-ascii?Q?0eYOm0BlBR4GfluQoss24V5VrKfhhSqPAdcHEqDQ6Akcd+fXHEgh3vxv32+Y?=
 =?us-ascii?Q?PzesMn7LthsZlgr0zppaWJj36mmHH9535RVH4VE1?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 
	OBHlwN+Hs6V6GrK984sfwKJgmgNN5OWvI2gC9CF1hiVQEB7bO/dVVZtEgwBgo4mcrusOBxisOs5diQHQIP6OOvgVzpLJTCAbNQAUpLynOw1h9a4moi4l2TC+W/oHjABiFY8bXsjGBsAsmYx+6i8H7goSDUB3yJv0Bcx1SC72cyUK1JAi9iwN9rkcNOOag87Gn1o1cKEWggUPZ0G5I1IejcpL8Vv2Fc1SBjN5kWuczfXgNR26qDJliwQu39qAWotj6L3bhq09WwjpKGPp/pLVW5ZYZWBfiJcCpFrVpd1qEzHmwaSaPJX8rdpVAQ7j/+uCieoQEEdqY3KD6LhK3Mu2MAXk44kLgKt+3whHjikHz3c7iYd8W6yAhESZ/D1Oj1Iv2K5GtSOuB+feKKw24d/W7UBNfxW8v4r37pDrlX5wnJ17Z358RxIS6KX+5pCyzb/B9BP/AUoNLAZQA3dCpEff6B/6joElfLZIKtuUe/WKWEnFKLGHhC5NdusiAt8GHkO3LHAjx5QUf9VirhNt83F7DQeQwG61A3HjisFOsSqcLtn8M1vgNU9V6jUdkyVMkpOZpstlYzkboVFKSKL/m3fbNWqc54Pu4g16bBUWtEclzHE=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: a5a49bab-4770-48c4-b739-08dc0007f080
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 18 Dec 2023 20:28:48.0270
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: d9RinggWibA1s0tfeY7Y0cpI6Lg116smJiZmGkFBIPh5c7UuDxlT/SkFU4qfLH88n2lkL6BjimcwH82SYsiwVw==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: BL3PR10MB6041
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.272,Aquarius:18.0.997,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2023-12-18_13,2023-12-14_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 spamscore=0 mlxscore=0
 mlxlogscore=999 bulkscore=0 adultscore=0 suspectscore=0 phishscore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2311290000
 definitions=main-2312180152
X-Proofpoint-ORIG-GUID: SkQ4wP_Xe86g3Vf6CN6avNIjUmVxwxDT
X-Proofpoint-GUID: SkQ4wP_Xe86g3Vf6CN6avNIjUmVxwxDT

* 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
> >