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 CA128C54EBE for ; Mon, 16 Jan 2023 08:40:56 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 0AE6D6B0071; Mon, 16 Jan 2023 03:40:56 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 05F286B0072; Mon, 16 Jan 2023 03:40:56 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E68FA6B0073; Mon, 16 Jan 2023 03:40:55 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0012.hostedemail.com [216.40.44.12]) by kanga.kvack.org (Postfix) with ESMTP id D65AE6B0071 for ; Mon, 16 Jan 2023 03:40:55 -0500 (EST) Received: from smtpin02.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id 94EB8C044D for ; Mon, 16 Jan 2023 08:40:55 +0000 (UTC) X-FDA: 80360016870.02.F8556CE Received: from mail-pj1-f44.google.com (mail-pj1-f44.google.com [209.85.216.44]) by imf15.hostedemail.com (Postfix) with ESMTP id 282ADA0004 for ; Mon, 16 Jan 2023 08:40:52 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=70wIzIqS; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.44 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1673858453; 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=bEb72C/frQfArwPtQinDRwWrx1ltU8v74zNyyIO4oyM=; b=rsMxy+LgaKa98gwYGH0XmBnlDY7sTwi3mQ6RXU52xIjmDzy+zS5llGSs5I/H6nl3pI0QVz jjC3QnVeAJ2TnEpGpQa62s2GmIGSgVp2QJjNRj7aJyRrlKKCv/CAoi9fVjzv1r328hvyoW TN3YvYifIbHSHC2PWI/qPX/EZrqR/Yw= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=bytedance-com.20210112.gappssmtp.com header.s=20210112 header.b=70wIzIqS; spf=pass (imf15.hostedemail.com: domain of zhangpeng.00@bytedance.com designates 209.85.216.44 as permitted sender) smtp.mailfrom=zhangpeng.00@bytedance.com; dmarc=pass (policy=none) header.from=bytedance.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1673858454; a=rsa-sha256; cv=none; b=ZKmheREW6CuTsJBHgVGcXwecMdX0lPmxfMKM3qVdulc0zWsJq8Ptuyc2szD9r2y/B+bkHE +ooArdAsFO3aFd8vYavg3u0WcWtibkQX52zg/PiJr3QXT3QVR3KVo99NeGp//nK5/wEmN1 W0I7xTTGCC7YxL9trb+xRujKlO6eNxg= Received: by mail-pj1-f44.google.com with SMTP id o13so24910861pjg.2 for ; Mon, 16 Jan 2023 00:40:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bytedance-com.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:from:to:cc:subject:date :message-id:reply-to; bh=bEb72C/frQfArwPtQinDRwWrx1ltU8v74zNyyIO4oyM=; b=70wIzIqS5PHYs/wx55I/kYhXzJvgzLv/QbuMQDjFXqIP7qFP9pafYEhRV35zjE41nm bHLVtho2Y5WKecfl9VToPr0gdKEbNh8Vl/XnxMdSU6/sIB9ZrMRbYYXZScDgsIUjGRM6 QZk5810wU5Ja7OmuKH4Rdr3C7pwCj1tycTeDTAXQ3hIIoDcbu8aKUWAbSO0FY8MeKStR D+bXb6OxnFDoFgnC4jK5I/Z4JTdxGzHEx+d060RT6akaIhp3UPY0+IWMfe5IVuCs2LIC Vn/k4S9cwlQ0FVLGTglxqBtKqwYuf3plk6am0kp4Gojn4KryrKQi1pQ6VPFeV34oR1oo o16Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to:subject :user-agent:mime-version:date:message-id:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=bEb72C/frQfArwPtQinDRwWrx1ltU8v74zNyyIO4oyM=; b=DilgbYB8K4/o8hXCEYHbcBGPG2MLVRv0kPV++NUx9wfLpxLiI3bB+rYv9jJvu6l/YB ssQlI503jFvqxgKkLEIPa2duqYH5UureglaSWE/ixVEFUWKxG/ScJplR+BbA/WAptQ5E 9RP+8k9eh+m/CXxijJ0gKp5kREXJZnwibjuAu0xGDAZ2cizVlYMmX+9pibVCK3m0WSSR RuiTZ9XYSvF+LxVDcEVeZWC+Xi31+Z2tfFdc99TV1Gj6NKWx75jy4sEPcMInDa06lPQg kwNLn4qkUhPbmpCTb/5rQsDPo02iPUV63pwc/TTsQyJyYpEcB9vmwR0j3BCpnb7APZCs 6o1w== X-Gm-Message-State: AFqh2kq2n9ch0E1Okc2hau9gqS5q5mJVW2IlGhISJZpUB1bL22vSxR8H mbYSIXArQPUcaafL3Gs+qbm8oQ== X-Google-Smtp-Source: AMrXdXtodyd3wASxNOG8btTnZoEfcCXYqPhDmV8llKqkMaVOBYQDi3nt9CLvWvtiVf6ERc65m79FPA== X-Received: by 2002:a17:902:b48f:b0:192:8502:77f9 with SMTP id y15-20020a170902b48f00b00192850277f9mr20251942plr.27.1673858451651; Mon, 16 Jan 2023 00:40:51 -0800 (PST) Received: from [10.90.35.114] ([139.177.225.239]) by smtp.gmail.com with ESMTPSA id z10-20020a1709027e8a00b001947222676csm5849391pla.249.2023.01.16.00.40.49 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 16 Jan 2023 00:40:51 -0800 (PST) Message-ID: <49b867c1-2b68-c034-9f60-b26a77ff326a@bytedance.com> Date: Mon, 16 Jan 2023 16:40:47 +0800 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.5.1 Subject: Re: [PATCH 2/3] memblock: Make finding index faster when modify regions. To: Mike Rapoport Cc: akpm@linux-foundation.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org References: <20230113082659.65276-1-zhangpeng.00@bytedance.com> <20230113082659.65276-3-zhangpeng.00@bytedance.com> From: Peng Zhang In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Rspamd-Queue-Id: 282ADA0004 X-Stat-Signature: 8haeci8p9n5m8pq3p8fpqgpjuc4sgx9h X-Rspam-User: X-Rspamd-Server: rspam08 X-HE-Tag: 1673858452-310139 X-HE-Meta: U2FsdGVkX18pV7TUOvDn9C0LGOj1nlZwfLrkpMrhHIXUD9a8nieNBGGNGhrz30Matd68e6QBrzRzwnxl8umr7P4xNsxLwyJdx35uslAz0qGFxVccXVPHSqdBMT5TfNVUPiyqj/OBwUmn2Bbc70L4zSE2msBp3RQPD4JtBQLHRNTCUkR/01Vh8PvTTGp/cyqeB05QlzsxdkE14hN1aejihDHHK0toZba0M+AJWG3ggYH5S1TxMn9U1IMjemXNPkXXrHlNeU+d4qkxcHANOJHHfYQMpztbOzUrEUot4Nha9Oe1IWk+8GiY3rot/H6wtADSPOsGox7XMLcG6vMPGa4QZ9fKGX9u5mXAWnAuNIRJIpIDozkI+MNHyivaMbIVB/Jc8uMjm5XzCEu03S85EA14Va47/an5+g98uo3L2Tv7cj28cdbm3gqacC4aFrujFhaa8RoZTI01e1ImDDt50gfWIyZGpgkctsnJiU5THXdg8qZrDIMC4Em120NLTbsw2jLTFmurKe8zP/jr+L2GSRv1K3vNg4t7oTbsZRqkitMk6iNagTmGSyjFrnzUns39uUPP4Rm2zPUlwuARinosDqyIhsBpKrWRtnN9xOGC4Mqz57kq/ojEJ5AvytKvKt3iMGFMftig9VsUDb3mKlJMdSoM6y8SBf3H9PLL7rYY3QtUhhiW8SKfxcSIwi4lEqtdK+8eC92RUna2tdoOMS1PaCqW5s5nE4Sy7FunTKDl1pOeDOmpn6HIQETbmLpfEAOM25FIz+5fFgbNvGe4sS+KyKVJOGw0UwpvwrnLrhQ1Ed5E8hMDB5aa+8qzjX/OXX7Fl9N+rczcu3h5KWE0HNfE40CiVjnMQuJkh4cPKSNYMYj1Csh/4iBsQB0GdcgBM2ffgMa2+AHReaLnAXR9r0ecTWTZRO01FF7lDhXlwCKEj6vChmEnGYYaLYu+hLNbMX8JJmKhrBfSRoyhykF10BJw7WI wHFhSZNt R7j+jJ7N/7Ymozi4dazqC9wXKhrL2Jrgk07pUPykJLBNz7biabU+oWGDQQL8KVkJ++QGCpmRW7GbewcfJZblJ6eZajOkVbh4PeiMTrjkkk1+yDucYbPvPYpXyhaYN7BxNkgL5/D4n1y3OjMGJc4KU+hvKswt+z9igO9je X-Bogosity: Ham, tests=bogofilter, spamicity=0.002085, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: 在 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 If max_nr_regions is larger, the difference will be more. Thanks. Sincerely yours, Peng