From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 8EC77C35274 for ; Mon, 18 Dec 2023 20:20:59 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0C2266B0078; Mon, 18 Dec 2023 15:20:59 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 071766B0087; Mon, 18 Dec 2023 15:20:59 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E54466B0088; Mon, 18 Dec 2023 15:20:58 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id D6FA36B0083 for ; Mon, 18 Dec 2023 15:20:58 -0500 (EST) Received: from smtpin18.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay07.hostedemail.com (Postfix) with ESMTP id A4DD916024D for ; Mon, 18 Dec 2023 20:20:58 +0000 (UTC) X-FDA: 81581057796.18.C3D2817 Received: from mx0b-00069f02.pphosted.com (mx0b-00069f02.pphosted.com [205.220.177.32]) by imf12.hostedemail.com (Postfix) with ESMTP id B69C340007 for ; Mon, 18 Dec 2023 20:20:53 +0000 (UTC) Authentication-Results: imf12.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=hFNgTsBL; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=yuJDSrgk; dmarc=pass (policy=none) header.from=oracle.com; spf=pass (imf12.hostedemail.com: domain of liam.howlett@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1702930853; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=NPjz8u/RzULheJVPOtpWendK6KGjybQcV5VGcFkLOXw=; b=sHaX8eGkguiG/alc0Wfe+yhbEYHxMQU67XJ2hIoMbDRDV5MxlVPSP0FnTN/JVw7q0793Vq lKhYCXM6zR3DICjD25POoTOUNZmX0r86GxjFuYvJRRbZvWjPxuk6i7wiiMWST9oVC7GnEd 9aOPQL9iEm7gK8V93lilIlh4JPVldS8= ARC-Authentication-Results: i=2; imf12.hostedemail.com; dkim=pass header.d=oracle.com header.s=corp-2023-11-20 header.b=hFNgTsBL; dkim=pass header.d=oracle.onmicrosoft.com header.s=selector2-oracle-onmicrosoft-com header.b=yuJDSrgk; dmarc=pass (policy=none) header.from=oracle.com; spf=pass (imf12.hostedemail.com: domain of liam.howlett@oracle.com designates 205.220.177.32 as permitted sender) smtp.mailfrom=liam.howlett@oracle.com; arc=pass ("microsoft.com:s=arcselector9901:i=1") ARC-Seal: i=2; s=arc-20220608; d=hostedemail.com; t=1702930853; a=rsa-sha256; cv=pass; b=gXNsQ4zgg0RtSumPbrtOBr6q0EElivL79AeSsKrRlKc/kUwPucGCVAOwgh7+G8bTE79eLS cIN8cNTdy6U4z8wUd6Eq8bnMpd7/AgurN1a6NooVsKzqepjttnfZ32Zq4wWhccTGgD34RZ X/0whAujW7oIy98H7GWvc7Kenpltlfo= Received: from pps.filterd (m0333520.ppops.net [127.0.0.1]) by mx0b-00069f02.pphosted.com (8.17.1.19/8.17.1.19) with ESMTP id 3BIHXkVB018113; Mon, 18 Dec 2023 20:20:19 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=date : from : to : cc : subject : message-id : references : content-type : in-reply-to : mime-version; s=corp-2023-11-20; bh=NPjz8u/RzULheJVPOtpWendK6KGjybQcV5VGcFkLOXw=; b=hFNgTsBL6OYogJdt+ThXfwYrnrlM3fZhJau4u/XDm0dUNNxaeh7qih2PpY0h8T9goK8n jOV4mQwwUkhf2qFqEPgicuTf1o+ExCV2LNq+NtQSU98Lz09sc1HC46W6pH/aWuOE2i6L bbbByokEPMzD4HT1G11A0gpmbzzMuYdoqqagSFVIUcGrqGo4pxNFINQHgfo/dnMDGXCA KP5ngu+Xf6xhNtiJcIo905jeNiy9bjkhe5VuNKlDKXChWsnx3uvprJixFfVjGL4tdak6 bZ2vGiTAhl9jH0hi6JTAG16KCdJbNHUA3/lbOKTdRwuBaIOeQmeWgmEJ5HgKOubOUIXw cQ== Received: from iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (iadpaimrmta02.appoci.oracle.com [147.154.18.20]) by mx0b-00069f02.pphosted.com (PPS) with ESMTPS id 3v13xdc8f6-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 18 Dec 2023 20:20:19 +0000 Received: from pps.filterd (iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com [127.0.0.1]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (8.17.1.19/8.17.1.19) with ESMTP id 3BIJg3kD030989; Mon, 18 Dec 2023 20:20:18 GMT Received: from nam12-dm6-obe.outbound.protection.outlook.com (mail-dm6nam12lp2168.outbound.protection.outlook.com [104.47.59.168]) by iadpaimrmta02.imrmtpd1.prodappiadaev1.oraclevcn.com (PPS) with ESMTPS id 3v12bbtb3h-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Mon, 18 Dec 2023 20:20:18 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=KeVi1o/AtZKrtE1QarGxTGxRg8LnofE68JJgDks8PNUJNg9C9/aSPc91eo7YOqaWB8rjy82xxm2R6Fc0GB0F20hKyMLX+gsT7Gv9qZmF78t3qZ1tf7cWLiW+Fzl8jtakPxK10a9Mui2qRlG08LAq53NaDksHrVhDIrMvWRPt0uSjxxkP2f9FtBm+MnJu6PC5w+Q/ylwPGF/OoTwFhn0v6Fy7JLjcANSqt9gzOzzvl1nEP1WfzERisccJhFaPDpZDfHsFhXDReqmh22BxOt4s996+nOqPaiGgSIiYZsiLNdPlcONv+CJcEVXZo7Dq6UDd0/W/lakz/L2SGnoDfPpAuA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=NPjz8u/RzULheJVPOtpWendK6KGjybQcV5VGcFkLOXw=; b=Rro0cBETc/J1ANAANozK4Hb2MqnLe7Fdf57oHI6FxCxOD6aos9LUCCKHESYvoeYLQg/u9D3a7Q0tMphlt1W8yabrgez1wNAsiT6RORlhMdCz+DCX5vRkR0ni80Br1TC5pHyAtLnHOo+mPhretSfk8ofQrmd6S5QRZvvoGk1Rinr4mxB6VRnXkrDoxuQ5qpcQOmwHLdw/lkK57yL9hZpDeA+Cd5TsdDjNqJCnzjprGyR6FsNpklAAKp8p2EujXidBtSoDpCPdAtMz6htRCvwiid+L7QxsxNJEbLc8T6/gYMUqEmJlvN53OOusd72qaLQihFNTTNQB60/U55+kmJz7oA== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.onmicrosoft.com; s=selector2-oracle-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=NPjz8u/RzULheJVPOtpWendK6KGjybQcV5VGcFkLOXw=; b=yuJDSrgkcrPCmKYnpCMAkjRtsWLJIGZ9tTuW/C7m5JNGkNoN12X/AflO7BwsY2AblQxyIuvKuB1PN+vEzfZCveU49lWBXZUoM1o+5V/KArBN8usA8a07Gw92yhD39wIS8/qgD5hgRqlAozD/k/+hcruhlLbIn6xovIxddxRvgRU= Received: from SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) by PH0PR10MB5594.namprd10.prod.outlook.com (2603:10b6:510:f6::12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.7091.38; Mon, 18 Dec 2023 20:20:16 +0000 Received: from SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::a5de:b1cb:9ae1:d0cc]) by SN6PR10MB3022.namprd10.prod.outlook.com ([fe80::a5de:b1cb:9ae1:d0cc%7]) with mapi id 15.20.7091.034; Mon, 18 Dec 2023 20:20:16 +0000 Date: Mon, 18 Dec 2023 15:20:14 -0500 From: "Liam R. Howlett" To: Peng Zhang 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" , Peng Zhang , 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 X-ClientProxiedBy: YT4PR01CA0307.CANPRD01.PROD.OUTLOOK.COM (2603:10b6:b01:10e::11) To SN6PR10MB3022.namprd10.prod.outlook.com (2603:10b6:805:d8::25) MIME-Version: 1.0 X-MS-PublicTrafficType: Email X-MS-TrafficTypeDiagnostic: SN6PR10MB3022:EE_|PH0PR10MB5594:EE_ X-MS-Office365-Filtering-Correlation-Id: ebc52006-f49c-4293-d799-08dc0006bfa4 X-MS-Exchange-SenderADCheck: 1 X-MS-Exchange-AntiSpam-Relay: 0 X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: +cwx0nP28HRpm4CilON3ddil1cjN+jKUacBpaXZQiPW4UtQop47zhxhXmfb6gKQBKXl/kzBKisf8iOXvXucS/JyAlqhjsNlRcBFQPXu9da3w4MFQyRNUgHDKAyctbkGm9D/EO6ubrQqpG3cQCaVbTit7KEgugevRuO5XL2pz89YKcK2o2iEfEExFy6hh3mIG6fdFAg69J7ot6E33domqcSwIlopP2GzGaxuVyPCYtQbPvW29e8CSoyLis8OSv0cFZF+VSrsVWk3Y22ojmQ6h5yeL+zh/0iI+nWBYlAlN6oRyk3YCMsNDs7zq6h2ndelyiRdW0w1l430j664F/uAk6xMa464PklIlL8RG2MRySR1Yj0XICPgfjBWfuAwk/g60zwsDnVo+spZgVYI1RbtgID7b4peDNcHbkh3nKEXM2w+Jiv3RAAKLZXTiz61VSbzYupuLXEYNns96V4BCmdQBtOSurL3wsf/9Qse2arnAVygoQAdaR7+XewiYKCDyRbXw41xsJd9Z0iOV2qG00wmsi+7wTB/5GaVQhTaGQ8qG+MwPImDgNT2ko9K+QZ+DRfGv X-Forefront-Antispam-Report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:SN6PR10MB3022.namprd10.prod.outlook.com;PTR:;CAT:NONE;SFS:(13230031)(7916004)(39860400002)(366004)(136003)(396003)(346002)(376002)(230922051799003)(64100799003)(186009)(451199024)(1800799012)(86362001)(38100700002)(83380400001)(26005)(33716001)(1076003)(478600001)(6486002)(66556008)(2906002)(316002)(66946007)(6512007)(66476007)(6916009)(6506007)(9686003)(4326008)(5660300002)(8936002)(8676002)(41300700001);DIR:OUT;SFP:1101; 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 X-Rspamd-Queue-Id: B69C340007 X-Rspam-User: X-Rspamd-Server: rspam02 X-Stat-Signature: kntfrq9d8axt7qfu78bofptf6ohda7mm X-HE-Tag: 1702930853-183352 X-HE-Meta: U2FsdGVkX19O9vJoxtjlHwW8FHoTeqYbVPFoM11ewT9RFw8wh2blE/RGoIHKwi6eiAJXhN5BScxD5s8rQpacr1ptN9ve/ap1+K9u8nQxf2LXXDuEG+aiODrdURKZvt+RRo9Dkzymm0kl6Qbf1M7aAKR8fCOxWuwBwHiix/L5WCCR9zmrJeqCxSHlDmlwQzYm7n3X7jZ3a12dQ0PL3xkoKVK1s1dKKw2mg9HFySuEhXhlvVj+NnQTBh1XX1wHJjUA7m3n1oiLmNcJxAUob8o/Y/ckV6YYY9BAA65uq3X6DHvxlgql45aVNfwFqGCu2WbeQ4snUu0qA+bWAN6Ed80Ism2tlpSbRPdNqo0jFbhf0X5autGL63BABT4vjcoIM2F4RPOO4oOksgQeVjw2YcK8VfwdltCZUraEz5+dA2dxfB1l4gOq1VDifOf+tBC9gjv+RrQk+knPntSX6ja6jsf0T8unbxMgTUeSE5TROylaVoCEHJlzSpHCjO45dIz6Efjb13iRnmeLPJcsvAtCwH9SIGyotq4IEhqcJWZR0mUtt3f9O+hn9j49r1IsyVQqLQ2vVY9KO1dT0rc6HrVobybtAZYXSqMY4lvuB8j8Lgm6Vmy7SYb1HDPJ6Vx6y9d+rUQdR1FgvY6r0UmArYfmvePcQqf/UjowgPfv372CNVJvcEiA6AI2ceeH4iW9BbJn2sWSYv0yumaAhDchndnqZ3wJKAIEUA73XX9CBYIDFAP6HN7Gcps4akPhNYe4eJplJDTcX8FkIm98TesrdblhWSnLeDQerCK7PBQOX8A9GxoR94PfIUKz+pDLq44rsHTaVDZVc/HEVMP/tETd3w28+dhifRhqGzZJbzWcUIQgzNRp/2XiIi0HaUBGed6TLu2HV1XuLm38vyMfqUQQUY4zRJHVudv4++9+6x2um3WN8Da7eFCbJwxmLHv6Jp6q02mBy40sab5guzrFemNdJDYx/Ok AO3AnDuq B7s0JCyg/Bsn5L3fwn+TWTFiP35jo7STvblrO0hh9uBBAg6n144gwAPAKNWAsG60BNM4B2Qk1Suw47YscJ8gA4A7TySINAb7HSny2BqHwxf7XRHfXDBcEypgX9SyyxRFK8L+rcMKS5w+jCFLQuCtXBioGSXU1LxaXmgXGgae85uOiwo26fKooeZLiKo32v1jX9Hpa4vYiqpglYDQ0r+gaKRhyU4BdIM8P6F7y49+cRrHqWEQPSjRGAsosc6ZY3WavEUDwA99F9FvFMDMtxh58JDHC84PAKpidBmSX0PrPKVngjmAvbtsmcIWCz/BcUwYt22ISQyfqBN5G2WK/FHY291zhlhZpmBb+NpfJy+5vmUzwRbumaPZAvlweqiRV+0ONZXN/gQSKWLw2RG89u2aSlVpghp0xAtSh2F29ZE+ff+oEzr/pgYX65wjS3YNqWzd3rtaZqznKSVC1PvQysxKV5iWzoujats1fbw+cVwYU1gL/NH97Be36qtVI6n+ePrAvt0I3xllYSYqR+iymcTMH0KfNPg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000016, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: * Peng Zhang [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 Reviewed-by: Liam R. Howlett > --- > 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 >