From patchwork Fri Dec 15 07:46:32 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Peng Zhang X-Patchwork-Id: 13494097 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 53A24C4332F for ; Fri, 15 Dec 2023 07:46:55 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BADF38D011D; Fri, 15 Dec 2023 02:46:54 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id B5DE38D0103; Fri, 15 Dec 2023 02:46:54 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id A25858D011D; Fri, 15 Dec 2023 02:46:54 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 901E18D0103 for ; Fri, 15 Dec 2023 02:46:54 -0500 (EST) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id 61F718051F for ; Fri, 15 Dec 2023 07:46:54 +0000 (UTC) X-FDA: 81568271148.02.8269CC5 Received: from mail-pf1-f173.google.com (mail-pf1-f173.google.com [209.85.210.173]) by imf27.hostedemail.com (Postfix) with ESMTP id 3705740013 for ; Fri, 15 Dec 2023 07:46:51 +0000 (UTC) Authentication-Results: imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=KkKbHY4T; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1702626412; 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-transfer-encoding:content-transfer-encoding: in-reply-to:references:dkim-signature; bh=CURAtT+EULVw1WUO/LymnRu4QScwQ/mpUpF54vPt0wo=; b=Zy5rul9EbjMPM3g9D6weIkiFhXLYNft6W4CXcyH92mUIJ86GLlUioz7VO0+xEEMEVMwhDS z79vb6l02cHbJAtAPqDqH96drnoZHxkTTHb5o6hj5hGGGdSzf3Ptr8BZe68rLIEM7qokNJ NaVvBwNHcMcNJMNNMq2G7aYEtoz7SkM= ARC-Authentication-Results: i=1; imf27.hostedemail.com; dkim=pass header.d=bytedance.com header.s=google header.b=KkKbHY4T; dmarc=pass (policy=quarantine) header.from=bytedance.com; spf=pass (imf27.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.210.173 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1702626412; a=rsa-sha256; cv=none; b=mMZb7+0SA5udTtwBcH8qyyeIp1Mg4VK+pORrL39ZsBmG5UO7GFXTUZ54vq7YnA18JbSGNr ze6zxK6c3+SLudzd+HhQg971AThyYXW2LBcMEO1+nQDIzWAE9l3POjdZgUei78E93vCDM5 0RwYa8XM2EQ+BHvaj+rG/fBHbKNbfhw= Received: by mail-pf1-f173.google.com with SMTP id d2e1a72fcca58-6ce26a03d9eso183562b3a.0 for ; Thu, 14 Dec 2023 23:46:50 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance.com; s=google; t=1702626410; x=1703231210; darn=kvack.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=CURAtT+EULVw1WUO/LymnRu4QScwQ/mpUpF54vPt0wo=; b=KkKbHY4TBKnIE24WV6h8GmWt3QVihnUc48qwGlu8+vqHhW6FYPmN09Nq6hVeLk6HWe ND+PYJlB86Do1bPwYHyVrDq6ekfzTM3/eVludXg1veWNkujug8YEVXK0WWooZHdbHAvT cSj9ZQJy7J9qL43zhIZKiz3PV43kHMx2mvI8d2TjT/+jpa9sEQwbrzlsY1qU1dty1mDx LEv848k+CwGZBX1dTBF0SDos2g5jVApjHU9xc5urya11QvreuP0Mpiqont6cyJHXh8bw O2rg69AF2xMokmq7wQ2IcHskdqmAlwc3/0D+0SXArAaep59J/Jx6hQ7/xYFGe8SM2FhG v4jw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1702626410; x=1703231210; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=CURAtT+EULVw1WUO/LymnRu4QScwQ/mpUpF54vPt0wo=; b=hsqEzmrQ60bGl76f0P68NofGFcWRqG3zpsY//jTAElfxXzKbxnyi9N9hQj7tmMmGta gFUtnLZKHkMp/rSnLdaez6Q7unkH+9Vw0CriHkygrOEVZRM6917IHsHyIl4grby3uDBQ IQumqGGuFMHHV+j7h0f6bKQHKaedwsT293qZu0Ft3iMBGRTgc8a2mWKTNtOYSExAj15H KuGDUpCkvI8NvUX3fVhdfwuA8AnC/RxtiGmzS8GSCdOSiSE3Me7+0rO2IEQCfxLfXXQh FCyx4WnSRtNwPO+79xxBzCugSegR0dXHeaCUJeyuhRxwlXqWrbKR+9OcOfRKnJ6O9+pJ AjLQ== X-Gm-Message-State: AOJu0YyIeyhtF0HVr1WqzdgM2xBjYo8Y2JNiKPaVg4LfrJa7mkAKAHcg eCJjM00utxdNYvNbaC1BxREwng== X-Google-Smtp-Source: AGHT+IGbl4tSvWzLdqBdv1C+br/qeaLBNQi/RO+pfmEb3VdxMcWDGLvFxcjKUE2VnMHln98cwQAz5Q== X-Received: by 2002:a05:6a20:8e01:b0:187:97fc:6c56 with SMTP id y1-20020a056a208e0100b0018797fc6c56mr7173650pzj.49.1702626409748; Thu, 14 Dec 2023 23:46:49 -0800 (PST) Received: from GL4FX4PXWL.bytedance.net ([139.177.225.235]) by smtp.gmail.com with ESMTPSA id 28-20020a17090a1a1c00b00280070a2613sm2823175pjk.51.2023.12.14.23.46.46 (version=TLS1_3 cipher=TLS_CHACHA20_POLY1305_SHA256 bits=256/256); Thu, 14 Dec 2023 23:46:49 -0800 (PST) From: Peng Zhang 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 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> X-Mailer: git-send-email 2.39.3 (Apple Git-145) MIME-Version: 1.0 X-Rspamd-Queue-Id: 3705740013 X-Rspam-User: X-Rspamd-Server: rspam04 X-Stat-Signature: zq8ap3n1n4zhmgcbykqcmx6nqqw5gxuq X-HE-Tag: 1702626410-834646 X-HE-Meta: U2FsdGVkX18ILLtBXNfAemFYmYi+LViuWB89f3KzYO2s5mVu6RlaxDU3QD2rFKKjywN4IAOuQ4/E8PmWDCnWVyrsA6siNfxtMVx5L0zkNZQ62Uc9kni1dHwBww4KjqoOCtKY1TueSJuUwEYykk1s9iVp9N9h8d93VrVgWu+xYOUUnLsb+1VIw/8biLxHkttJx+r2DmPkiwuWosD5VnUgLKEXxVt/XD1ZPqv15E0n1qfYYVo03qtbeaqgUnIsx5To4zu/9+9JJUcR9zsF6yUcGWgD9y6mYmAaE7vSF0wM8vQ8JB7liBje7KM/qCI6pPDDfLdJ0GVZvJhE5ETtWpfobch63OuHoMkXKXl+OfT5eUCaSV3/IZqObcYmJASTbA8fdssBOBHPbcpUW3CJEd+NpXGPGl/vpWRpsn7iperdLhAov31VLECU278jlGJvmGC8VAVptJf/DW8Kvu0kSiMEYGgjsMh7PagZi7XjXYIaWNhdOwSuzvp3DWf2ZVnD+MVBKUPc1/CjILQvlCjVyVlCTkUFPPzOwBh3kbKjbw0vhA6lrwn+8nnj31gwTabDkfaonpKWt599ndfeGBuRz9WVumqOqJPMOD1Z3SJ8K9rN5RVP0WAAIwSU/vKCETPN3A4xzC8O2aHJcd1caE4JzkOwZwTHAKU1y2i+IDpp4SYiTKQhYJRWeJCwgTJyKvkteq9nSftWLYtki05Ng4nPu6vP+rokcQLRj2sHpU9yKx8hwhqpUMokJ+LxxglcNdOB5SSfdBn7c70IFf04L5S1FjuI1e9SzgdqhIo6ORl4MIau+fTM7N5vTSAjSnFreRL13BnSSoKflmo6QGe0ko/CYWUPegnCPr6fFYVxXfOtnQIvGGWi41WV2Y8VBQBf3VFp9Gvo/saruD7cs5Crz4zYwdjK2YQd7FHBfhbawW4mjS39AoePJgf7PcPAWVGiWjNACJxvVE3odCbx2RD7AxgF5n0 Ja3hbk8U TZHliRi6ovdaT4+1ndbuS7J4XrjKSP8a5HDPYLJ9lXN4BofRX9Hgq8uoV6MFZdVRwAZlC/Db3SB8YJaSDV1h5vKZAQ0s4TmwRLyF73ZKi+1St48PpD5AQtqxMF5/xabwPqqgNWOqqmHSXcesGtLcguWKmx+PnSvX5lXJvTOYtHbbEsrMsWcLpaySKnpsQSJJR0ZCXan64We08RriNWVCdw1adFX+fwlPVWhMqgDNyfMXd7Xmeg0hr/euDLznrT6CtjvydCOPGknBKDsIL80ZxJBae6+o4io3Y6Rszzx1hY7ihh8GlaDMF6EsnKqgRkePgQmKe8BBqrOHHpEfzeG5Cut9rcYxWT3DWRHOqZNtph2r17y17vE8V5c4yDM1MhfzdKztkEV4npuM6HnZroMzGZLfshYrsWex7xeIqEeIjy+2Bffd3s1nGU4c2bV1pQb6om9qDXyctkLLeuL0E2SuHzPib2euyHtKTPKX0hoWd+f7KLKEoxztj/HtpdxI58yr3+nCA X-Bogosity: Ham, tests=bogofilter, spamicity=0.128351, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: 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 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++) {