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 BB8DFC00A5A for ; Thu, 19 Jan 2023 13:01:08 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 47F846B0074; Thu, 19 Jan 2023 08:01:08 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 42F806B0075; Thu, 19 Jan 2023 08:01:08 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 2F86B6B0078; Thu, 19 Jan 2023 08:01:08 -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 213CC6B0074 for ; Thu, 19 Jan 2023 08:01:08 -0500 (EST) Received: from smtpin14.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id CB81E1A0D46 for ; Thu, 19 Jan 2023 13:01:07 +0000 (UTC) X-FDA: 80371558974.14.DA811B7 Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by imf10.hostedemail.com (Postfix) with ESMTP id EB0BAC0038 for ; Thu, 19 Jan 2023 13:01:05 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=gg+W9kuA; spf=pass (imf10.hostedemail.com: domain of rppt@kernel.org designates 145.40.68.75 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=1674133266; 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:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=xJUgRRLcfzFWFIH4HJczRS4srnifhQwCWD9KRbXq7LM=; b=vxGfBTqyf6pmZhlqNZBb0GvOcjWF0v9HtrodoB+ETaIJ5ENDfT2QkbvavnN/1yUYfzEGtv hnWZqK6bE84YKhHyK//IERzZn3bY/xz4KZwSyUTx0iTwazibDDAoZkX12XfsiiiZU0thLy UmxYa2/b19Z0rlZoSKhnFrdG5KRXjk8= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=gg+W9kuA; spf=pass (imf10.hostedemail.com: domain of rppt@kernel.org designates 145.40.68.75 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=1674133266; a=rsa-sha256; cv=none; b=bLkiUMZ6NfD+cd0FWQpWK8fTjUfhtLz2jEgaelG+eYqbKkJfwoYtqUKjcnR5hFQiTzYnWy W/eMvOE5UhxoQhUcH9so1mKXtDkCR/Rq83GD5On203lVvdDTXHo5XmQm+ha5tH4ALCFkys BBBBMlUw7B+g+40ue84UcRL7OmWR5qY= 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 ams.source.kernel.org (Postfix) with ESMTPS id 873D6B82117; Thu, 19 Jan 2023 13:01:04 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id E67A2C433EF; Thu, 19 Jan 2023 13:01:01 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1674133263; bh=rXkl/DGFD1+8+kXI2HLkjSe5GI6vKmolaKZBDMc5QeI=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=gg+W9kuAJ96cAS2RtMcNSKOMRpsfX14XEnLclcRcxOc5N8GpxD+8F0QK2BQw0YLGi NtyNhaBZreK0SpMH7dHuH/K29G/jKMgJX3NYyuDe5ClmtwhVgEcpktOa70ImQFXV7+ R7hQZpI4MGZweZ/KDpdqpVJdS7r5jbmEhwRcXM946RudRUDjHqyjHO8nyCeaPERSOL yorCjsK2cTjR/w3gRhpThsl3kGJBpWO4fJusE3/rnxxfqbr3JWpNm7rxYLCfDeUBxd ZD3XkQcoUwoT7YOVZIqQElFA5AIEez+Y109aLqrCiF/rhtBPDp1sSeiauJWkiFD35c qpZwbc4gtmBpw== Date: Thu, 19 Jan 2023 15:00:51 +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> <49b867c1-2b68-c034-9f60-b26a77ff326a@bytedance.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <49b867c1-2b68-c034-9f60-b26a77ff326a@bytedance.com> X-Rspam-User: X-Rspamd-Server: rspam03 X-Stat-Signature: yt78mjtugg3xnqpq6yrs49hg7t6h87i3 X-Rspamd-Queue-Id: EB0BAC0038 X-HE-Tag: 1674133265-864630 X-HE-Meta: U2FsdGVkX19w5zKJzqK9jJfwAygJrwpamTgTvHjShDGlMk9HKX2pTyI3IwjtgzrWNo8thitkMpBcFlYedAWywbAeVQQ5VBRuUXHRymrOqCmD1oJ0SWPk5GH2bJ9P8tjqLbonieAm52UCa8I+MxFJbVD5SoqmpBP85isfe7KbQhc/GPdFverK9ln7kyS9Q2tFbp43qtY/GnlG0An0/FtEDrfdBPxHVMZKwc6oQLFHfCHMAb9RlUgCaQUyvofeVfOedAJpxsBepY1CrKHCTizd6QZqErPgOEgyZEolt3T2X24ybgzLsa4BO6t+khAQgGaefndIkibDPw+Y9N9rxy6y6UVVmrXaO6A/Wd+lZjJb295I96RCFAAOZ8wubUQzX82m7hDX56SMosAXp/Fa3qA46LGRWpBFIm2BnlFU5VYIxKnsifKw39upDgKYSM6yBE6fJZTZy8Ml9Jez11/cy7rG6pKm1HN3lU4p4GgT7RE1z2sUSdMm9v8m9PzVL2nNQs5dRy+3g5oocbkMGfetPxUWedjhzT+1VUXcRcH8x+8ReCTZscxn9aq8An19FTA212vBqzv/lBO81J84oJV3RQLGLbg6vB/4lBg1HJt1RFkrg1D1wM02rEjfx2jFazszCCgJR1w83d4DkcoYuOf1fLX5aHQak1nMEc6Q7d6nmyXLGBfUy/F6sSzAS8R3sbhFXE5NJUjQtf8yNGZJ7nBcvOvqwDSGYkxZ4gYcHd45tkH8gTaMO+/QsQkLiLD9N8CZ4F71YWVZh4vkh7Q9RhlcCJzC9brPB5RufTsFT6yjk4H8D9jpT5CUqcbGUO4E7vvQmmilT3ZNPxrHbNM/gPK4nTlvb/MFi+SWOYU4U8QSh+sTKKNCPHGUdvO2h2x0bg+LN+kWHeabNQotFhQvaXmiYAmhJm5yWqZfPKtGBaB1inWrNDecU21u7ZKyRpYA0ZC2Ute6DNkQW3+opMH9ha9yW3k gXrhqKyU v7bWiUO+2XS/vz0HlmZj/MPcywKSdWdpanCUl X-Bogosity: Ham, tests=bogofilter, spamicity=0.000024, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Mon, Jan 16, 2023 at 04:40:47PM +0800, Peng Zhang wrote: > > > 在 2023/1/16 15:37, Mike Rapoport 写道: > > On Mon, Jan 16, 2023 at 11:17:40AM +0800, Peng Zhang wrote: > > > > > > > > > 在 2023/1/15 22:02, Mike Rapoport 写道: > > > > 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. > > > > > > > Thank you for your reply. I haven't measured this patch yet, theoretically > > > this small optimization might be difficult to observe. > > > If you think this patch complicates the code, you can ignore this patch. > > > > > > These three patches are independent and they can be applied independently. > > > The logic of the third patch is very simple. It will not complicate the > > > code. It is tested by the default configuration of qemu. The total number of > > > iterations of memblock_merge_regions() in the third patch is reduced from > > > more than one thousand to more than one hundred, this is only in the case of > > > a small number of regions. Can you consider the third patch? > > > > Can you please send the numbers and show how did you obtained them? > > > > > Sincerely yours, > > > Peng. > > > I obtained the numbers like this: > > void memblock_merge_regions(struct memblock_type *type) { > static int iteration_count = 0; > static int max_nr_regions = 0; > > max_nr_regions = max(max_nr_regions, (int)type->cnt); > ... > while () { > iteration_count++; > ... > } > pr_info("iteration_count: %d max_nr_regions %d", iteration_count, > max_nr_regions); > } > > Boot the kernel by qemu. > The folowing numbers is the last output. > > master branch: > iteration_count: 1762 max_nr_regions 41 > > patched: > iteration_count: 182 max_nr_regions 41 The numbers that indicate what speed up your patch achieves should be a part of the changelog. It would be great if you could test it on a real machine and measure the actual time saved by your changes. > If max_nr_regions is larger, the difference will be more. > > Thanks. > > Sincerely yours, > Peng -- Sincerely yours, Mike.