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 1A66CC46467 for ; Sun, 15 Jan 2023 14:02:51 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id A110B6B0071; Sun, 15 Jan 2023 09:02:50 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 9C03E6B0072; Sun, 15 Jan 2023 09:02:50 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 8AFA86B0073; Sun, 15 Jan 2023 09:02:50 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0017.hostedemail.com [216.40.44.17]) by kanga.kvack.org (Postfix) with ESMTP id 774F36B0071 for ; Sun, 15 Jan 2023 09:02:50 -0500 (EST) Received: from smtpin06.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 3A6171403F0 for ; Sun, 15 Jan 2023 14:02:50 +0000 (UTC) X-FDA: 80357199300.06.F7B5866 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by imf25.hostedemail.com (Postfix) with ESMTP id 8DA9DA0020 for ; Sun, 15 Jan 2023 14:02:47 +0000 (UTC) Authentication-Results: imf25.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=S9UU0i3Z; spf=pass (imf25.hostedemail.com: domain of rppt@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1673791367; 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=rHnAOTQr816fzFJOn+u0jXNgkSMHl4xqHJwEDkdphsM=; b=7eFgT0QdkxG+Bfd+N7yx1i/mSRNl8dJr4lhqRxiOq9g0b9tkDcByJdtF42cywyOuBjMWVF euoFIPOAvnuOmNWrQfEOZyxBJ4sGR/o8uvKy+YwCAPQFLkAqbEFIuosV1+z9bdPASOBpCw MxExGaVTT+VgFwTNG0VXql9DgkULZIA= ARC-Authentication-Results: i=1; imf25.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=S9UU0i3Z; spf=pass (imf25.hostedemail.com: domain of rppt@kernel.org designates 139.178.84.217 as permitted sender) smtp.mailfrom=rppt@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1673791367; a=rsa-sha256; cv=none; b=H8w+9Sj39q6sV6ADYiMXafCSuCtSMePY6fRJYHZaXrUySwVEEWWs6mgpVuFPfQxPCnlQDZ 8QdDTubhfk3ypN5Wu3YaoYWi4HfRJ9uWDG3LEg+/sUYt0QXkADF/xXSkTdr48D6CMm8wwW HBA6DwbH9fLyf5yjjAf4Md0+S6emm2c= Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 82A6F60C4D; Sun, 15 Jan 2023 14:02:46 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id A8111C433D2; Sun, 15 Jan 2023 14:02:44 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1673791365; bh=Iz7nC6DDEeDN9U0y1HI37zzfchxJz+j/YXBBMI+uEng=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=S9UU0i3Z9VC1fchiKPWZ4R2wyM/Mq9yTMKMwkmW04WRnyeRBukQcnBZCuMMgd0b6i zhwPUtDBE3iL98MqBIoMkna3SL5pGPodjkablrc5hbqe6Nvq4ZzXE00yUnBzumLQrs rk4s2Myu/Q1bSUzwx0YhlsgIsDUtqYfoYFlYqJ3oQLht1vBHAgwp0XkO4753kVW5Ul 5MqNhAQruZreXZQ1pgfx1eMVFVMezP7V0tYemst7R5eKTks2pNHM2/xaSEfvtzAlig Z2OyIvV14ep5BQ8Eq83eJBEAA2fj3czPeyfWQHyuvp12xxZ8IK3qUmRnRSUn47jSdu ymKCKyS2T1BDQ== Date: Sun, 15 Jan 2023 16:02:34 +0200 From: Mike Rapoport To: Peng Zhang Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH 2/3] memblock: Make finding index faster when modify regions. Message-ID: References: <20230113082659.65276-1-zhangpeng.00@bytedance.com> <20230113082659.65276-3-zhangpeng.00@bytedance.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20230113082659.65276-3-zhangpeng.00@bytedance.com> X-Rspamd-Server: rspam05 X-Rspamd-Queue-Id: 8DA9DA0020 X-Stat-Signature: 3iih6b9dmbj63iqy8i7abi7jinr8fbo1 X-Rspam-User: X-HE-Tag: 1673791367-634975 X-HE-Meta: U2FsdGVkX18q/qNTcoJhje5FnH6/NuCGiQE5AhChKaDzja8+oO4CfTF4CzjNKPcb1a+0YDRZRaHtMceiX5tTeJb7NIGzleQ/EeHBsBwo1HJq4Kk0YMvLgIbTCNGbGYwyKL2rbavPTYTf8BDnh5OcQ+N/8tUvdkyZH1bgJ+7xhdj7SF0BQiDRNbDr8vrVTOsP3/Y8Bw9Rk+BhVWginBmMCGf+xo0oacYxcVlWYdeVe7seON+fhBC80f+r6epZgfHbp4uED+tL2e6GfB/hCBP5KKe7tA+sN1gCxlUpXcKGBunqlrl95YFr8SBO5drpWtGxMLFJJNZciqHm7qC7jeV0ldHnIKNeseXPuhtc08cE5l03bFjsXytWdvX4yXf7wGWO6TGGkfno2q3qhZAg27CkYLPdUpObPPVhSKOW7NqH7gq53uxIQ2g+da9WPLH4CETpGOz9PaPN3TuEAY4NQmGjZ9ZioAaql2phVHJC8B8X2rK3CuYPqAqppwdAbWxqMLPfjSkK6QdG2ceAOrwqlENG80IVkq0CU00d2rizhEAu6JPlfDJCqJ26KfopusFo3UMaGXy8Fh2toY7lpgOxwlS76LA9iDyOXsMExg8uie9Pe85L1x3OoID/NAEh+qLXlikr9RM/bf7+4hpp+rlcD3AQYzBDtFrQEsohuDR7ptDNAORrwbnLFVwT5YmTwsCGBUrfGgiyHAvA1PHS+PtL6RmDUDg8o94FsQ9jl9jbHJwdY3d60+gY633ZN/F4ZjMVXu9ESquXXBsfdkH4oYfbVWw1jl2B8oRUtUo9DEb8q6ujUV8tpRW+LP1Q0G4YetuGviYn+S6WRrk/zML9Xk+CN53v6nm9B0rSkLTnS5bbIBM3UzX+/p7tjHyF3DB7V7ViCkioduBhHUuH5GfPF8gM8L2CYRAdifZuyEpniROMaeWSMEgjEY6ogfLa0T5MzEnVjEw+eBGsg+u/VImgsa6qQXN 9RcUv0To MyEb44IFEGuL34SIyqYtvsGjA/wCPNgzunM0J X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Hi, On Fri, Jan 13, 2023 at 04:26:58PM +0800, Peng Zhang wrote: > We can use binary search to find the index to modify regions in > memblock_add_range() and memblock_isolate_range(). Because the > arrangement of regions is ordered. It may be faster when there are > many regions. So implemented a binary search and a new macro to walk > regions. Did you see a measurable speedup with this optimization? I'm not in favor of micro-optimizations that complicate code. > Signed-off-by: Peng Zhang > --- > mm/memblock.c | 33 +++++++++++++++++++++++++++++---- > 1 file changed, 29 insertions(+), 4 deletions(-) > > diff --git a/mm/memblock.c b/mm/memblock.c > index 6eedcfc5dcc1..cb92770ac22e 100644 > --- a/mm/memblock.c > +++ b/mm/memblock.c > @@ -149,6 +149,11 @@ static __refdata struct memblock_type *memblock_memory = &memblock.memory; > i < memblock_type->cnt; \ > i++, rgn = &memblock_type->regions[i]) > > +#define for_each_memblock_type_start(i, start, memblock_type, rgn) \ > + for (i = start, rgn = &memblock_type->regions[i]; \ > + i < memblock_type->cnt; \ > + i++, rgn = &memblock_type->regions[i]) > + > #define memblock_dbg(fmt, ...) \ > do { \ > if (memblock_debug) \ > @@ -181,6 +186,24 @@ static unsigned long __init_memblock memblock_addrs_overlap(phys_addr_t base1, p > return ((base1 < (base2 + size2)) && (base2 < (base1 + size1))); > } > > +/* > + * Binary search for the first region not to the left of @base. > + */ > +static unsigned long __init_memblock memblock_lower_bound_region(struct memblock_type *type, > + phys_addr_t base) > +{ > + unsigned long idx, low_idx = 0, high_idx = type->cnt; > + > + while (low_idx < high_idx) { > + idx = (low_idx + high_idx) >> 1; > + if (type->regions[idx].base + type->regions[idx].size <= base) > + low_idx = idx + 1; > + else > + high_idx = idx; > + } > + return low_idx; > +} > + > bool __init_memblock memblock_overlaps_region(struct memblock_type *type, > phys_addr_t base, phys_addr_t size) > { > @@ -581,7 +604,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > bool insert = false; > phys_addr_t obase = base; > phys_addr_t end = base + memblock_cap_size(base, &size); > - int idx, nr_new; > + int idx, start_idx, nr_new; > struct memblock_region *rgn; > > if (!size) > @@ -607,6 +630,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > */ > if (type->cnt * 2 + 1 <= type->max) > insert = true; > + start_idx = memblock_lower_bound_region(type, base); > > repeat: > /* > @@ -617,7 +641,7 @@ static int __init_memblock memblock_add_range(struct memblock_type *type, > base = obase; > nr_new = 0; > > - for_each_memblock_type(idx, type, rgn) { > + for_each_memblock_type_start(idx, start_idx, type, rgn) { > phys_addr_t rbase = rgn->base; > phys_addr_t rend = rbase + rgn->size; > > @@ -737,7 +761,7 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type, > int *start_rgn, int *end_rgn) > { > phys_addr_t end = base + memblock_cap_size(base, &size); > - int idx; > + int idx, start_idx; > struct memblock_region *rgn; > > *start_rgn = *end_rgn = 0; > @@ -750,7 +774,8 @@ static int __init_memblock memblock_isolate_range(struct memblock_type *type, > if (memblock_double_array(type, base, size) < 0) > return -ENOMEM; > > - for_each_memblock_type(idx, type, rgn) { > + start_idx = memblock_lower_bound_region(type, base); > + for_each_memblock_type_start(idx, start_idx, type, rgn) { > phys_addr_t rbase = rgn->base; > phys_addr_t rend = rbase + rgn->size; > > -- > 2.20.1 > -- Sincerely yours, Mike.