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 85947CE7AB0 for ; Fri, 6 Sep 2024 03:44:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 076DA6B0082; Thu, 5 Sep 2024 23:44:16 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 0260A6B0085; Thu, 5 Sep 2024 23:44:15 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id E08CD6B0088; Thu, 5 Sep 2024 23:44:15 -0400 (EDT) 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 C42896B0082 for ; Thu, 5 Sep 2024 23:44:15 -0400 (EDT) Received: from smtpin19.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay04.hostedemail.com (Postfix) with ESMTP id 6CD171A0DFF for ; Fri, 6 Sep 2024 03:44:15 +0000 (UTC) X-FDA: 82532920470.19.85FDD40 Received: from mail-ej1-f52.google.com (mail-ej1-f52.google.com [209.85.218.52]) by imf02.hostedemail.com (Postfix) with ESMTP id 7D59A80005 for ; Fri, 6 Sep 2024 03:44:13 +0000 (UTC) Authentication-Results: imf02.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=YkyjIob1; spf=pass (imf02.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1725594156; h=from:from:sender:reply-to:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=rzGio6pyfMdHZ6YH/LgAMN4H/SEre9BBkKo8rufQ9l8=; b=v/na90bNvK6Ghqt6QOMX8f3AtsjQm64yq8oTugmH3TqY80GPEG6dnekhb82CRnL/5Vwfdq 6E0GAc3Uf9QD5/rTtijPJRrqXPjmDt2KwgtX7BzgO+ZGtWTtUF2A+uDVdtvdK2GCN1LNB1 ka1dPiJyA0N2/YE4B/F9G+5elUNxwvI= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1725594156; a=rsa-sha256; cv=none; b=esGX3RNas8FLdMmcuiFcsxTclaS2DjrFO7eLqYMwzFl0wto/O7Q92/LKInoC1ubHdXk9HZ fh/D4NYm03fS3FCgMkBlVBj2ai98KjNhSd1oYnes0/HKurTpOmRDPHtS1DVt2Wm2e5TkNk VuXOqRdKBrwd2dpGOgIDEka8jYp4QnA= ARC-Authentication-Results: i=1; imf02.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=YkyjIob1; spf=pass (imf02.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.218.52 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-ej1-f52.google.com with SMTP id a640c23a62f3a-a867a564911so206331866b.2 for ; Thu, 05 Sep 2024 20:44:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1725594252; x=1726199052; darn=kvack.org; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:from:to:cc:subject:date :message-id:reply-to; bh=rzGio6pyfMdHZ6YH/LgAMN4H/SEre9BBkKo8rufQ9l8=; b=YkyjIob1DubWm9xQ9tBTwGHnEl7qpbZpjFuMYrK759aV6dzfpPFimcp/4okAYFC6yK nHn2tLE/4ANpDXmykE2cQpKy5E6wxe0iEHCBwvrCxOtR5QEGjFBLDxJHR9ZGGYLm1LrY JdKCo5aSuM8io7Qyby03bI4SKulP6MZdbaklecO1gq/Ja2PowsE0tKViN5eFWI67oNT9 Wmz3B2m5/FyRWITgJf431J6/LDevk8gbwo4PFUv27PQJtwRyszyHEfWIUqdve4MvivdV VafEmWkYUak+85u2o7m5NrUhP1MV7tSDIUO8clPQuXPHdg1Cxf1guJ1V/tF851dh3Oz/ oVPg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1725594252; x=1726199052; h=user-agent:in-reply-to:content-disposition:mime-version:references :reply-to:message-id:subject:to:from:date:x-gm-message-state:from:to :cc:subject:date:message-id:reply-to; bh=rzGio6pyfMdHZ6YH/LgAMN4H/SEre9BBkKo8rufQ9l8=; b=gZ98bk9LpR9Bz/cmT1cs3KKabHJAs9dPKCz1PQQ1EtG6SBHcIvyN9i1i5qPzIYnI9T tK0E+crK1GV5ocv3XEK8hK3lJ95XgFQWYLA1vjI53BNlXiPBsaNq9ZllsxJK2SEdzuYz Y1/2tiKlaWFihUizpDLY3WaFfMi0WdCBjSFhsrOY3ZN343f1YQJKPLi2Je/2aZEyLhQ/ nq1GQbnUD4jXouAb5DyEsPpVNoCsRP4dfnhoreEMnwmce4QywyRaMfUFqQk01LPNJqIV t02kBGfgndwMF3PfCzrG7HWvJLuHrvy9onGKlYW7TlUgFCDdx75oKAvsmOpavqx/gWUK NDJg== X-Forwarded-Encrypted: i=1; AJvYcCV0VYVIwnj9iC02LhqqMvMH6Rx/bWNfpQ2VmmStQ5lM3c4yFA9rePTE3RheojC9ENthmx7mv7dqFw==@kvack.org X-Gm-Message-State: AOJu0Yw8p4DWj2aMMbgonzFS8g5DVQP5vReXTLA9yG5PzW0t3INFRjPr Y/rnIEuhZyhauYrwkfbgnWiR/co0QPYu0CYHMjPYxNyKmZW+ZSQq X-Google-Smtp-Source: AGHT+IGmXeGuPErk9oTVvd5KcLo1L8nIKIvTXjyPr5DlbBVo5qvh+c3Zk3lGtBdnIGKe4Ujnd5Tilg== X-Received: by 2002:a17:907:7289:b0:a72:5470:1d6a with SMTP id a640c23a62f3a-a8a886680c4mr77118266b.35.1725594251548; Thu, 05 Sep 2024 20:44:11 -0700 (PDT) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a8a86bc6049sm52107066b.211.2024.09.05.20.44.10 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Thu, 05 Sep 2024 20:44:10 -0700 (PDT) Date: Fri, 6 Sep 2024 03:44:10 +0000 From: Wei Yang To: "Liam R. Howlett" , Wei Yang , akpm@linux-foundation.org, maple-tree@lists.infradead.org, linux-mm@kvack.org Subject: Re: [PATCH 1/3] maple_tree: use ma_data_end() in mas_data_end() Message-ID: <20240906034410.zzs4n2acrgkneekr@master> Reply-To: Wei Yang References: <20240831001053.4751-1-richard.weiyang@gmail.com> <20240904001525.5zshbivv7op4ana7@master> <20240904075819.5vgnelkxxj7myyn4@master> <20240904145305.dq7jolrwd6fp6dmf@master> <7lu4ere4h3lmpwxwgyhlymk25bxj3iqisjdzcsyymcxmo74dev@sv76tlhchbee> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <7lu4ere4h3lmpwxwgyhlymk25bxj3iqisjdzcsyymcxmo74dev@sv76tlhchbee> User-Agent: NeoMutt/20170113 (1.7.2) X-Rspamd-Queue-Id: 7D59A80005 X-Stat-Signature: 1dbxyuyhtx4dym3n8nzyxee6taoejwuq X-Rspamd-Server: rspam09 X-Rspam-User: X-HE-Tag: 1725594253-674010 X-HE-Meta: U2FsdGVkX198W7WF/rsy9SskoHyHrIKf9qCKjGdTb8DK+Ix4cpbHgnZN+Wj+iuiAxF5YJfjpLb2TV1TYyRwA2YLO/BJ0ArCk1PXZunPV3dmRjNcwaB19mWzpwegEXcmN0PCjMuyaNjL/8er7yLrHLJoG+uZqwFhNHnzXoU6akobVOvn3eT0xgRPHu1MVUQeW9Q8A55fHR4C2ncCVe80qv4FgevblR3t3fgqUkOtLyQe1ZP6+8D5GoQLYwI4slGYgwGa1/ap+YA+Dan0G0RlUitVAqiCHOqj5cuKhj5nwhzSAsUMT0C2pDppc3WDca15T025+/soeGe8CMJCncOO1egWr+ya1sRgSuKkd3FYfc0JloYCc6OkPOmKK6YUH6AFQJiyWfAqRTG9RrCQvsBRYBbAq0RnJM8x8LVs6NC9A+NCgFqyp8m9riY7kh1VP+T4WemZm1wCO6XiEJIUTuP0a7gB5p8QUtgKMDor7djDG3dJJPQ8GDVO1EkV9WdX3EgmylU6QNYyCt21o1xsau08rpsYrrQZ3v5RJ8tcU+GyXRTfP10snlnJi7oX/Vfk33Q0Q1P7Jf0ATtwr3Z5ntsVU3zN+hElu1ik+BeugAw4LAIJAUBaPqbu/ZkLgLO5G5dRXKNT1FiUuW/1JO/1I7EbVpDmAoDMV4rdyc9/PGNu86xrv6lYoiZ4gFBaoRJOUAqrsCdEcedR0jHDQy9zIyUckCqtZGh1bu7ZXlK0dphFKkqkEwlc+HZ5wJVYbTqLPNq21lOOy1FyKqTEcpqBvZJ4cI2spFm+fFOS+mUUJcU2Iw5ju8fkqxHhkMf8ZA1k2Ao1QeWKFCNccJR+HNE0hDPCqAgr/L8Cha9KMYozsOlz5Cj7qNIhrW1Gk7iHl09HEMa8y67XIAf3NyVk+y9aL8Il/433teBfqlY4kgbl+WPAB26i+8KQAEPad2aPFA/+/50/J/GCc1UMGW8OBQjJbICv8 f+nvRG5W CHLLYWpJu4w3mYqeONI2U007JGRvYS8+m3pEZ6854IH65VzJAGPiTys6/r460il+KOTvTHN0mk9JTlw1LdM2ybaFNYB1FVmihddiRrS5Kh8HWYAMp3jJtACTMhe+LOS/sKdOMHpo526YPxNyRR7G87HdHdOPMYNBT7d4CTlvc56y96vRp0LNVDhmWR3jITM5xok6/E8mPA1V4D2M2WH4THzLVrVFFqVl5nN6WXEY9Q3sXPXhZwWivQlS0yrwicuWvK+KiAlUQoWi2dxeXo3mrr9cMB1AM/F1IIie3SNCdNOQDw8LjyJt0nT/FTz8sx8Ih8c6rO0F5AK3YJ1NHqq+AIUjP9kOs2xPw+knrEIjEWV8789F9+hHet7ViSDUtSvwoUpdd2/kGocZA/2JtuVM0vFit9qYMYkE4qQdtrOdQJZDxReiCLjHIe/NK+YZF6XQg9dZ/BvoGluHycQ7E/XfQRihzr53EeOFBEbKyhbn6AKHTMb9a0KbmHXfh7tRcrOXoEJl4KwfcUPLIBaWkIMfQS/huK7wU5ksOxaf2+/6zz1K8wISkl51r8xnOL7JITlWY9DX3K0r8BM+wTtcoLUJ+L9HYcCo/18ALZvBRXu05T2L6uHAH+RQ6hBlRc8SXZ6hlWKy2Qeld8XeF4+9blhVkIwovDY1k847v7DteNSQpBUF1FLZjzPfEYBrKxg4J2a2DIgK2 X-Bogosity: Ham, tests=bogofilter, spamicity=0.001142, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: On Thu, Sep 05, 2024 at 04:13:15PM -0400, Liam R. Howlett wrote: >* Wei Yang [240904 10:53]: >> On Wed, Sep 04, 2024 at 07:58:19AM +0000, Wei Yang wrote: >> [...] >> >>It is only changing code for the sake of changing code. And it looks >> >>like it will be slower, or the same speed if we are lucky. I have to >> >>take time to verify things aren't slower or add subtle issues (maybe an >> >>RCU race) because the code looked similar. It's just not worth it. >> >> >> > >> >I am trying to make the code more easy to read, but seems not helping. >> > >> >BTW, I found in mas_update_gap(), if (p_gap != max_gap), we would access >> >the first parent, parent's type and its gap twice. Once in mas_update_gap() >> >and once in mas_parent_gap(). >> > >> >Do you think it worth a change to reduce one? >> > >> >> Liam, >> >> I am trying to understand what kind code change you don't like. > >Any change that cleans things up and verifies the performance would be >acceptable, but your previous changes didn't do that so the burden is on >me to verify that your code isn't going to cause a regression. > Thanks for your reply. It contains much information which I am trying to digest. If I misunderstand, please let me know. >> >> Is the following change worth? > >Not like it is right now, but this is worth fixing. > >Test using the tools/test/radix-tree/maple.c Look in that file for >BENCH defines at the top, and examples of the benchmarking. > I guess I could run them by comment out those #define at the beginning of lib/test_maple_tree.c? I have comment out one of it, what I get is: TEST STARTING maple_tree: 80000597 of 80000597 tests passed My question is how we leverage this test case? From the output itself I just see all passed, but I am not sure it breaks the benchmark or not. >Before you submit anything, run the testing to make sure it all passes. > Yes, I make and run ./maple for each change. >If you are changing anything for cleanup/optimisation, then write a >benchmark that will test the runtime, add that before your change and >run it in both before/after with the results. > I guess is to add a #define BENCH_XXX with related function and call it in maple_tree_seed(), right? >Look also into the perf tool to see what is going on and where your time >is spent, then you can avoid optimising something that's not worth >optimising. > This is use the perf tool on the new added benchmark test? I am lack of the experience of perf tool. I may need to spend some time to use it. Usually we begin with 'perf record ./maple', right? >> >> diff --git a/lib/maple_tree.c b/lib/maple_tree.c >> index 2b310dd3addf..e331d086eb7c 100644 >> --- a/lib/maple_tree.c >> +++ b/lib/maple_tree.c >> @@ -1595,32 +1595,33 @@ static inline unsigned long mas_max_gap(struct ma_state *mas) >> /* >> * mas_parent_gap() - Set the parent gap and any gaps above, as needed >> * @mas: The maple state >> - * @offset: The gap offset in the parent to set >> * @new: The new gap value. >> * >> * Set the parent gap then continue to set the gap upwards, using the metadata >> * of the parent to see if it is necessary to check the node above. >> */ >> -static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, >> - unsigned long new) >> +static inline void mas_parent_gap(struct ma_state *mas, unsigned long new) >> { >> unsigned long meta_gap = 0; >> struct maple_node *pnode; >> - struct maple_enode *penode; >> + struct maple_enode *enode = mas->node; > >Set this with the rest of the configuration, before the ascend label >would make more sense and be more clear. > >> unsigned long *pgaps; >> - unsigned char meta_offset; >> + unsigned char offset, meta_offset; > >Make this two lines. > >> enum maple_type pmt; >> >> - pnode = mte_parent(mas->node); >> - pmt = mas_parent_type(mas, mas->node); >> - penode = mt_mk_node(pnode, pmt); >> +ascend: >> + pnode = mte_parent(enode); >> + pmt = mas_parent_type(mas, enode); >> + offset = mte_parent_slot(enode); >> pgaps = ma_gaps(pnode, pmt); >> >> -ascend: >> MAS_BUG_ON(mas, pmt != maple_arange_64); >> meta_offset = ma_meta_gap(pnode); >> meta_gap = pgaps[meta_offset]; >> >> + if (pgaps[offset] == new) >> + return; >> + > >So every time we go up a level in the tree, we will now check if the >offset gap is the same as the new gap? Doesn't this mean every level >now has an extra check that was previously only done for the first >level? This is an unreasonable trade off. Yes, this seems not very good. > >I don't like what is there today, but I don't see this as a meaningful >improvement and I suspect this extra check is going to cost more than >the extra hot-cache check that exists today. > One thing I found is we may have this case, when we walk up the tree. This happens when we have a node with two slots have the same max gap. This means offset != meta_offset, but pgaps[offset] == pgaps[meta_offset]. Even we decrease pgaps[offset], the max gap of this node is not changed. So we don't need to change gap in parent . Currently we would first assign the same value then return because gap isn't change. With this change, we first compare then set if not equal. But this case is very rare if I am correct. >> pgaps[offset] = new; >> >> if (meta_gap == new) >> @@ -1640,11 +1641,7 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, >> return; >> >> /* Go to the parent node. */ >> - pnode = mte_parent(penode); >> - pmt = mas_parent_type(mas, penode); >> - pgaps = ma_gaps(pnode, pmt); >> - offset = mte_parent_slot(penode); >> - penode = mt_mk_node(pnode, pmt); >> + enode = mt_mk_node(pnode, pmt); > >Essentially, you have replaced the penode with enode and reversed the >order of setting things up. This seems reasonable, as it reduces the >lines of code. > >If you undo this change, you can move the check back outside the loop >and avoid checking it every iteration and avoid the double check you are >trying to avoid. > >> goto ascend; >> } >> >> @@ -1654,24 +1651,13 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, >> */ >> static inline void mas_update_gap(struct ma_state *mas) >> { >> - unsigned char pslot; >> - unsigned long p_gap; >> - unsigned long max_gap; >> - >> if (!mt_is_alloc(mas->tree)) >> return; >> >> if (mte_is_root(mas->node)) >> return; >> >> - max_gap = mas_max_gap(mas); >> - >> - pslot = mte_parent_slot(mas->node); >> - p_gap = ma_gaps(mte_parent(mas->node), >> - mas_parent_type(mas, mas->node))[pslot]; >> - >> - if (p_gap != max_gap) >> - mas_parent_gap(mas, pslot, max_gap); >> + mas_parent_gap(mas, mas_max_gap(mas)); > >This was optimised to skip updating the parent if we don't need to - and >the parent update was called elsewhere in the past. Since there's not >much here, we can probably delete this function and rename the >mas_parent_gap() with the two tests here for mt_is_alloc() and >mte_is_root(). > I guess your suggestion is to merge mas_update_gap() and mas_parent_gap(). Here is the drat, hope I get your idea. diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f81e3946b1d5..c04718e6acfa 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1593,28 +1593,34 @@ static inline unsigned long mas_max_gap(struct ma_state *mas) } /* - * mas_parent_gap() - Set the parent gap and any gaps above, as needed - * @mas: The maple state - * @offset: The gap offset in the parent to set - * @new: The new gap value. - * - * Set the parent gap then continue to set the gap upwards, using the metadata - * of the parent to see if it is necessary to check the node above. + * mas_update_gap() - Update a nodes gaps and propagate up if necessary. + * @mas: the maple state. */ -static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, - unsigned long new) +static inline void mas_update_gap(struct ma_state *mas) { unsigned long meta_gap = 0; struct maple_node *pnode; - struct maple_enode *penode; + struct maple_enode *enode; + unsigned long new; unsigned long *pgaps; unsigned char meta_offset; + unsigned char offset; enum maple_type pmt; + if (!mt_is_alloc(mas->tree)) + return; + + if (mte_is_root(mas->node)) + return; + + new = mas_max_gap(mas); pnode = mte_parent(mas->node); pmt = mas_parent_type(mas, mas->node); - penode = mt_mk_node(pnode, pmt); pgaps = ma_gaps(pnode, pmt); + offset = mte_parent_slot(mas->node); + + if (pgaps[offset] == new) + return; ascend: MAS_BUG_ON(mas, pmt != maple_arange_64); @@ -1640,38 +1646,13 @@ static inline void mas_parent_gap(struct ma_state *mas, unsigned char offset, return; /* Go to the parent node. */ - pnode = mte_parent(penode); - pmt = mas_parent_type(mas, penode); + enode = mt_mk_node(pnode, pmt); + pnode = mte_parent(enode); + pmt = mas_parent_type(mas, enode); pgaps = ma_gaps(pnode, pmt); - offset = mte_parent_slot(penode); - penode = mt_mk_node(pnode, pmt); - goto ascend; -} + offset = mte_parent_slot(enode); -/* - * mas_update_gap() - Update a nodes gaps and propagate up if necessary. - * @mas: the maple state. - */ -static inline void mas_update_gap(struct ma_state *mas) -{ - unsigned char pslot; - unsigned long p_gap; - unsigned long max_gap; - - if (!mt_is_alloc(mas->tree)) - return; - - if (mte_is_root(mas->node)) - return; - - max_gap = mas_max_gap(mas); - - pslot = mte_parent_slot(mas->node); - p_gap = ma_gaps(mte_parent(mas->node), - mas_parent_type(mas, mas->node))[pslot]; - - if (p_gap != max_gap) - mas_parent_gap(mas, pslot, max_gap); + goto ascend; } /* -- 2.34.1 >... > >Thanks, >Liam -- Wei Yang Help you, Help me