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 17751D5E369 for ; Sat, 9 Nov 2024 12:22:20 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id D90146B007B; Sat, 9 Nov 2024 07:22:19 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id D400C6B0083; Sat, 9 Nov 2024 07:22:19 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id C2E6D6B0085; Sat, 9 Nov 2024 07:22:19 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id A46886B007B for ; Sat, 9 Nov 2024 07:22:19 -0500 (EST) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id EBC8C1411CD for ; Sat, 9 Nov 2024 12:22:18 +0000 (UTC) X-FDA: 82766468022.26.9232744 Received: from mail-ed1-f53.google.com (mail-ed1-f53.google.com [209.85.208.53]) by imf15.hostedemail.com (Postfix) with ESMTP id 2CB39A001C for ; Sat, 9 Nov 2024 12:21:37 +0000 (UTC) Authentication-Results: imf15.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=PrSbJM8p; spf=pass (imf15.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 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=1731154767; 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=kQVfhbtipdYzWJdOK3EGqSLI/Rfarx8EYcLjmW96pNA=; b=pmguhNBylDDahniHRUXwh+7XWpKXTAxXeWvCqFudZhKOYZrBOrHEqBlpANOocvjYba93Ru FqKT9DhjORI3h7h4obt8z1mp6kGFFF692PWE3D8TniwYZm2iASty6muDkloJMIqMfnkZDR LPhii3rUJLs3HrNm2gx3sNeaWtj4LJ8= ARC-Authentication-Results: i=1; imf15.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=PrSbJM8p; spf=pass (imf15.hostedemail.com: domain of richard.weiyang@gmail.com designates 209.85.208.53 as permitted sender) smtp.mailfrom=richard.weiyang@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1731154767; a=rsa-sha256; cv=none; b=eHvgOkT82cwbEk6fznxKDackDeiA6XYruJwH6k4eIRYTm0nsK8HRhoW25hL5S2sih0qmwb DIG//Mizm/QhJ4IJR1KEN9LVbMYpTrSP02NyvmVY2xRBjMH76CMTD3jfrp1Nr2wPQ/C5zI QxXGCwqgj//+OhvXRfYKU6aDvYhZKIw= Received: by mail-ed1-f53.google.com with SMTP id 4fb4d7f45d1cf-5cec7cde922so3996148a12.3 for ; Sat, 09 Nov 2024 04:22:16 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1731154935; x=1731759735; 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=kQVfhbtipdYzWJdOK3EGqSLI/Rfarx8EYcLjmW96pNA=; b=PrSbJM8pS5KPN0kdvgeTKNVMLJ8MgMPvtyG0M0re7f7kKxin5fR7bjwnB3FvJfCPf0 Hp3dxjaBbjd9otVb9U7Nr1OA/8cpd3mCb4XSuwuFex1ybfl2N8svR2JaB+Y8kP8RbsXh uRKZy+LH9h0i74tZnjHSJjF7+d2THPiHGl/1zBO+7PKz2yP6ydtSKPgIYmAAz7qF7y1V g1cLjtC9PhRu7LxMEeGeHvCUkFYVwXU0ClvS3hiCedy5PBenNLPR7wq0pvQEM8mZKn/Q 8LF5dc3aVlbtppOI1QJ0M3aferb6vkDprL0CLGHV8HfVkUAmCY3lANElpfro3CF9coWr nseA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1731154935; x=1731759735; 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=kQVfhbtipdYzWJdOK3EGqSLI/Rfarx8EYcLjmW96pNA=; b=PaYy9mup73DkXjw8yNEKssj+6epGeKM9Ff0j4pEUZoJLGQeCfbF4sGElFOnVXWgMID 7/tGgrl7T3Tt231KsUAjN7vzTw0qm/eQ8+T05mhpitd7oOo78sLRwCXLyurE9im4Uhw5 i7WhM+lXUIQw3HhgxTnffpLSI8wq8RyMrVFNdc8PLREsJpTo1+KnFXzUxm3PM8b92L16 IfdwszqpqEAY+HpMznjZ5OlqrhOsmtybAgzelZzSNFyW+oe4N1a5NaRbTvZ3c8f/LIxN C3Ib07a5qi5VG0rEVyy8sr3MM46yDusSwBIvCfqiZZhwW555c8/fcIUv1Ppz/rHOGcMO Bqaw== X-Forwarded-Encrypted: i=1; AJvYcCWlP6TqW86WuJZQYY9lTxg9V7enLEGoYuFT9jmczyCgSAVTgQY+K0uPDgVxVxFI5SaR2gJEz2qU6A==@kvack.org X-Gm-Message-State: AOJu0YwEvRp7YljcuUJFz2i5pNqJPlE6HjNThMYwzcHZpJVhG5OLluWA PaI69ey70mYFJ8lAfRpkdHV55rk6OM/cYcI9I/27ZqAzCz2R1XLW X-Google-Smtp-Source: AGHT+IH4X94DMPteYpBgocoz2FRRBcj0Z3LPo92FN5QLu93L8IR9DKDKohQ/iIo5vbJUHlAsLW3B5Q== X-Received: by 2002:a05:6402:90a:b0:5ce:cfef:1d08 with SMTP id 4fb4d7f45d1cf-5cf0a45f7a0mr3701123a12.32.1731154934925; Sat, 09 Nov 2024 04:22:14 -0800 (PST) Received: from localhost ([185.92.221.13]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-5cf03bb760fsm2937082a12.47.2024.11.09.04.22.11 (version=TLS1_2 cipher=ECDHE-ECDSA-CHACHA20-POLY1305 bits=256/256); Sat, 09 Nov 2024 04:22:12 -0800 (PST) Date: Sat, 9 Nov 2024 12:22:11 +0000 From: Wei Yang To: "Liam R. Howlett" , Wei Yang , akpm@linux-foundation.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, Sidhartha Kumar , Lorenzo Stoakes Subject: Re: [PATCH 3/4] maple_tree: use the correct min to calculate split Message-ID: <20241109122211.663x2mmvlajib77n@master> Reply-To: Wei Yang References: <20241020024628.22469-1-richard.weiyang@gmail.com> <20241020024628.22469-4-richard.weiyang@gmail.com> <20241108025542.whll2orsuj7aru43@master> <20241109014038.m3arxtj2pqhqjmoq@master> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Rspamd-Server: rspam09 X-Rspamd-Queue-Id: 2CB39A001C X-Stat-Signature: f35hkjxg3yiks5pacshpwz3u3wunih4z X-Rspam-User: X-HE-Tag: 1731154897-958301 X-HE-Meta: U2FsdGVkX19N/0HiO34Tnymzq8+f/YBIDfQc9eGUkqLpO9QsMHhJPaO/q6vv0ZadDJvO25cmer3U1rlMriQFUZ5wS2IqCTLGTOh6vdwwYhjsYjGy3Yq2G3krJtMeC69KHIP35nY7XZYtTiuioIvX4N49UUKbsxYBVKsHnjRqyppJ35LJGFAdoPbOp6GQ5XYwgmtO4g7hcXEGEawKiJZIANNGcc71x0M4vD5IKimu/gcZJWC4o2wSO5wJKk/PTXpr5YJjs2Bp4rDBnbinfjQZ/eag3BgKRMtTjKAhzsjSbAFkWGoTSzfszRzBmj4EnLJub+/0hVzh7NL+O8E+fa1AQ9NCNy+mup/LRrCHn87H3/anqAKcoFMQoRLzX0ztDO3NpMMGe3izleUiux/HqMolLbpZDmULsyOh4Kysrz+27F7OoQzMACp5hUFESW26XHHyjMSGRa4MVcFgY/mVWYe01L44xJ7JWYTfgqsrHMUi0TtqFQoRaNHdumQiHj5dY/Jlyj0kDUiRp9gFPYytw4IFka5eQWltwq4KZ2OJknmOfClTGZkYa21t07YPKhVMx05w0WXnjgJ6CvsTU/CU66qnBWCRaNm1klJmh/U+jNa8PWZX/o19s1kmK9V7hLcsv7UvKgyf2zWxIea1s4npYdWS5qwHV1m5AvFLo9bANOQCMpeX+XM5HMdr9xcGS/hpdKQsuTmICsUk1lX8B/JBuiOFz0FJ+jJDSBrtLdYdXC8ERiwqrWZFaMg+B3gyOjvT5+FSMvNZ3/jGrkr3HQy9ZlUdxm3rxmtc7SaPLfUho2+K7mRWM+O7aaGELQdkT/nAopjphhpTTIfsP4F/E9GQKOHVLhCozEiJcL+UVWdW2MAsQ7LHiAnR7fwfQ86t6MID5lxUf3CdZ6+8bmcZjd9AYZdSo2wSOpjo5YEprEXW5Ksm2UuLAEbXWsPiEF5xswDZFL8HRZ/KTG9LmxIT+++WIM3 ye4NBwAE O4ELThj7kVYVZyl7Qqxe+NyVZZO+cLdlv/v/WhtiQ6TGipoW8oMmQanWqqtrcEziU6es7oPGXeaviALjvQH27m6Wi2dKg90xkdSQ6jcjVid+hHoSBxKLu3Jq5sT9IpB7cvXlNAullSPuc2t+Qzmo1ihVuN9b9UnAaxZs2biarrmscwQPS4ca7fOTMqOp2SNIB5asR5EcE918Oc30Rwjea1Mogc/hL4TFPYPA8TxXF69B/qshW4h8DDoHKq1EUA1f5i5RZ0+mR/UcVmFgPAsekhK97aYJUdoGBTcgEKHcLakCoEqhxTMeFhFOpS5frcPUXRjP3TtsAHzAd8fg3LnmkgPo+3nitJ9c2pZLEqMShddMP95GcCyNP95d0XNYyr3VDneNdU32uYtXG7t4vQ2u5KY9RxTkb36REhgAOJyCt1nqn44oIzeV2LYG0gl8wN9E1LbidxsEOJuHSZodTq+E3uLr+wDtW331tExCwHXoNVv5fnBwaXlEb7TaCajkYNNSzTBrywR2fm81C5kl7af7/03UtcOXGQfkp6J3v9zAOGrfswY4VuaoPkYKYMC0p4y2Di1bKL0b+rjCY7Dd8mnQ6Wk1WYnyQY6MOiXJkydoRGeW6Hl8HnumLlxZlfqjsQ90sRMCPK7mEamgvCFnd0f2X0HkoN8A0CdJLcZQ44LV85LmFctQaEpgMUfN/Hm7N1bqYDq5gWGYLoRnZlXzVjzm1ydHSbon1ldZ3oKl5 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000403, 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 Fri, Nov 08, 2024 at 11:01:21PM -0500, Liam R. Howlett wrote: >* Wei Yang [241108 20:40]: >> On Thu, Nov 07, 2024 at 10:19:37PM -0500, Liam R. Howlett wrote: >> >* Wei Yang [241107 21:55]: >> >> On Sun, Oct 20, 2024 at 06:00:35PM -0400, Liam R. Howlett wrote: >> >> >* Wei Yang [241019 22:46]: >> >> >> The check in mab_calc_split() is to make sure the gap between >> >> >> [0, split] won't be too small. But we don't pass the correct min. >> >> >> >> >> >> First we may encounter a pivot[split] smaller than min. For example: >> >> >> >> >> >> mt_init_flags(mt, 0); >> >> >> for (count = 0; count <= 240; count++) { >> >> >> mas_set(&mas, count); >> >> >> mas_store(&mas, xa_mk_value(count)); >> >> >> } >> >> >> >> >> >> On splitting root for storing 240, the pivot[split] is smaller than min. >> >> >> This result a huge (pivot[split] - min). >> >> > >> >> >This is fine. >> >> > >> >> >There is an open work item to make it more accurate at higher levels, >> >> >but it's not a problem as it is. >> >> > >> >> >Each level upwards needs a better 'minimum span', meaning that the node >> >> >should have at least mas.min - mas.min + level * something. >> >> >> >> Don't follow this. >> >> >> >> First, I guess it is mas.max - mas.min? >> >> >> > >> >No, the idea is that we could do better if we could keep the data more >> >densely packed. >> > >> >If we have singletons (all range of 1), and we have 10,000 singletons, >> >then a parent node with 0 - 128 and a sibling of 129-257 makes no sense, >> >there is nothing that can be inserting into the parents last two slots >> >- we can't split singletons smaller so we should have done a better job >> >at splitting. >> > >> >If you think of how this grows today, we split then rebalance until the >> >left node is full and we have to split again. This could be better >> >optimised to avoid multiple rebalances by doing something to push more >> >data to the left based on the span of the children and the nodes. But >> >we'd want to keep enough so some modifications to each node doesn't >> >cause a rebalance in the opposite direction. >> > >> >So a minimum span of parent nodes one level up from the leaves would be >> >16 * 10 = 160, so when we split we can push more to the left to try and >> >get to 160 while keeping the right node sufficient. The math of the >> >span would change based on how far up the tree we go, but would be >> >easier to maintain. >> > >> >I'd probably still want to split it 50/50 the first time, but it might >> >make sense to push more on the next rebalance. so 10 => 6|5, 6|10 => >> >9|5, but maybe it's not worth the effort. I'm starting to think so, >> >considering it's been ineffective to date. There is a chance that the >> >active area gets moved to the more-full node and ends up splitting >> >sooner anyways.. >> > >> >All of this will probably change when dense nodes come anyways. >> > >> >> Then there is sth related to level. But I don't see level is used for >> >> calculation. Would you mind sharing more your original thought? >> >> >> >> > >> >> >It works today for leaves, somewhat. >> >> > >> >> >> >> To me it works by coincidence. >> > >> >Seems like it. >> > >> >> >> >> The condition check is: >> >> >> >> (bn->pivot[split] - min) < (slot_count - 1) >> >> >> >> while slot_count is a constent, 16 for leaf node. >> >> >> >> And we always pass 0 as min, the condition for leaf is: >> >> >> >> bn->pivot[split] < 15 >> >> >> >> For the mmap world, per my understanding, we won't expect an address is smaller >> >> than 15. >> > >> >There are other users, but I think we should just drop this attempt at >> >fancy stuff. >> > >> >> You mean "set mid_split = 0 and drop the min argument all together" mentioned >> in another mail? > >Yes, please. The more I think about this, the more I think we're >wasting time trying to predict the future. And, although fun, it >usually doesn't work out. > Agree, will prepare another version with this. Thanks -- Wei Yang Help you, Help me