Received-SPF: pass (google.com: domain of linux-kernel+bounces-4339-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161;
Date: Mon, 18 Dec 2023 15:20:14 -0500
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To: Peng Zhang <zhangpeng.00@bytedance.com>
Cc: 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: <20231218202014.mpotsekdkszasn4t@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>
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20231215074632.82045-1-zhangpeng.00@bytedance.com>
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?Gcy4NjaEOjwuQltxCFjhJiERivFXyB3ce8dF9pAnApSGhtpazq14b+lLgK9b?=
 =?us-ascii?Q?iYKogb8dOsQiIU+mG++9FcRKe2wAjKxGeQ1uSy/JjxjLK/3v3QXijG7WEm4J?=
 =?us-ascii?Q?JSk67IVLqmPSPsNl8v3S8Vu8f/xihHLIpAFbBj1+PfLF1ZtU5iTsIh/qiIpT?=
 =?us-ascii?Q?RXF6GlJCUBBB8QMKraedpuIDQ8mxAHsoLU0bvKj+Rl23V5K2RERFNe2I10vd?=
 =?us-ascii?Q?/3EITLFS40Whdx/wvl5ut9nJdP3xO4D1QlmQBOy48mKvarSx+REg4jLZoZQ7?=
 =?us-ascii?Q?ePPAQeJl+qqn2sibzrtW0Nrm/JJHFeOh8SnHBrdeBzwVXmxE+lGx7fPCrjKF?=
 =?us-ascii?Q?SOrLKCmTcHPZDVdQFCJXZdlWWTK64pNWUDKk4MYZ2Eu/6kOmuzZ5wwZ/Cd9T?=
 =?us-ascii?Q?/xBkBzSmAMJUHzHJ3pEBAxdS1xfbO/6gBCEVPXqtx8RLPIJ19BeqYZR7Njqe?=
 =?us-ascii?Q?2JYLYc4UznP804RqGxJyXcq2KiLRMyuFhWFL1PdUZVAm5SDqqZoKBJGLYx6i?=
 =?us-ascii?Q?3Ql2Ie145wAgU7fIco1nDj0pt3BfQ1gldMGHb5dt3R+g3n4HPy5Tm0KltSgv?=
 =?us-ascii?Q?p6yducgfImxdJjUz1ucFU0rlHVweK5iGu8XFKFH+5fl4ZZ3S8bVxKC3Y4cg2?=
 =?us-ascii?Q?1zfoyzrI1j8PXpVugmQbDccrWr+mYSkzvhKpT1gL2QSJ8vy1EYBzFxYaJB69?=
 =?us-ascii?Q?aY7L02p0EZy357YGkk+cY95/QMl0AczNorh8PhZ5aS8o862AJgupW2fAhohP?=
 =?us-ascii?Q?PlsOVFJe31cLl8IQryla0qmfwbOC7lrMATrk5QncpAOETzsCXhf51lF9sAZw?=
 =?us-ascii?Q?52lKVns8dVtdkPaToIGC1VP0SJHpLMxg9LorKy3ij0+wIX37LFkk5dA/mXJf?=
 =?us-ascii?Q?H8X5qsPp5a7gLSdxl8nI+mma6dMjgvPMd8Y/gq4zW3ODZPvtVFgH5r3rO2tL?=
 =?us-ascii?Q?+Y4qfgfGrqPV7aGL3viG6VBW8OB0BbswbdLg4xe2tjnuUa9eMHckggxR1DUP?=
 =?us-ascii?Q?2K16hy12OTMQWaH0JMeFJWcQENL3CkqpNExpLd2w982vnWAp2k04cKGHBTw4?=
 =?us-ascii?Q?y/JrC+Jg9/vqgtbkURkaAV34JMmQTT8nlRBCMZnDcMxPuyrRm54bYHF70BN+?=
 =?us-ascii?Q?ukdjJC/vCN3NOIKxvC3KFAIP7Vxsrj9sUwlml46Z4RC5PMeXGB2BNRW/Cpd+?=
 =?us-ascii?Q?PEUWkG5cz8pyuXove3J4waG5zdYRyXWkiy0mnxluTYxZs/YGD0daG1jc8tUZ?=
 =?us-ascii?Q?MZA106bSOzmgHCzixT0XR3+QvWxB2wvAR6ePMz2PnrwbGzMSD5vbwyYFUEnC?=
 =?us-ascii?Q?g7/pJ/mKgWIIHiFwa5SegQerhOhc+i3FAviSqxO0SR3MVQEiXVx2o3Uz7j9s?=
 =?us-ascii?Q?JjpIO5wNeV2IrztVwWB7W4hHi4NH6fwhvfUs9GKGXZMxNdK28XMaGePgd6o2?=
 =?us-ascii?Q?uyXt3Z32gqKSZa5kPv4kyYItarVKCxhrg272Wo150INNclvU4MF4S4uURs//?=
 =?us-ascii?Q?EdjYO3+iPSm4ySG734iE88yaGynANIFVuN/kkN4w/5ueCnZLTR7qV5l3/GWU?=
 =?us-ascii?Q?0xziv44E9bdqNQIbzbq58vfk7doCGM3K438YHUSu?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 
	IjBxJ6BLdh9DSLdye1IW9+gCbi+Ecct5JtFJc9KPgNxgJmdYUnNsylIIbdEPyUTMngP4jtYTomzdrnoEbAu8fbHB7uUZhBzRRYYuQN3468RKzf6J/DQ4UPi/l4QLdtPjhUluFlEptMtGSmMTBuINFACAFR7y+vugOz3LDBWlhvnPD4z10IIWx4xatns7z7P5JXZFR94PZQxcSVt9Dyq0JVXwfj5NC63+lIGNy0TQmPPsLIjbssXcvJSoLp3VLsdEQoD7fJvOvhOJP82yt3BmdZPG/xNhQzN6iolj2XylLsEBjQ1wO6JSNYXxTwkNCUNLDtdv+/C8WY63EpYTGxxR+r1DsyNFtSZ0TW160cxIrCSja1Xuc9S0opot5IPzh9v2zzoe8blyPfQpHnpeto7Kl8Bm7k7yW/CNtEJKEWeygKLw30zahvDZ1Vn+xsDpBC3dCJSky1Qc/KGbONxv/WWrqr75gUPrHRPNCq/BziTr6XqR5jgIFVgZR8U/KcMg2+g3dZMRCj2YO5l+ITU2cXSEaaEcp+mt/JhXDxOkWZalRokbtty/SNw32C0yclruTIqC9XvRkUBAVyvLXLiuTXVAnQk3YyGlyFAxSHCJzrs6NBg=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: ebc52006-f49c-4293-d799-08dc0006bfa4
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:20:16.7058
 (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: DaS8y0BHuzrQLf6nvAKCZ55xLp6xbKix6UGimndEvtAlYg2uTXrnil9cQD+U/a7efmxHJSATjqgSQaLItQPQag==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH0PR10MB5594
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 bulkscore=0 phishscore=0 mlxscore=0
 adultscore=0 suspectscore=0 spamscore=0 malwarescore=0 mlxlogscore=999
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2311290000
 definitions=main-2312180151
X-Proofpoint-GUID: vzG7SOfqFFF9HphZpP8VRzfc7qrruWAh
X-Proofpoint-ORIG-GUID: vzG7SOfqFFF9HphZpP8VRzfc7qrruWAh

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