Received-SPF: pass (google.com: domain of linux-kernel+bounces-4948-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) client-ip=147.75.199.223;
Date: Tue, 19 Dec 2023 04:14:54 -0500
From: "Liam R. Howlett" <Liam.Howlett@Oracle.com>
To: Peng Zhang <zhangpeng.00@bytedance.com>
Cc: maple-tree@lists.infradead.org, akpm@linux-foundation.org,
        linux-kernel@vger.kernel.org, linux-mm@kvack.org
Subject: Re: [PATCH] maple_tree: Avoid checking other gaps after getting the
 largest gap
Message-ID: <20231219091454.5ouig5jnvjziol4e@revolver>
Mail-Followup-To: "Liam R. Howlett" <Liam.Howlett@Oracle.com>,
	Peng Zhang <zhangpeng.00@bytedance.com>,
	maple-tree@lists.infradead.org, akpm@linux-foundation.org,
	linux-kernel@vger.kernel.org, linux-mm@kvack.org
References: <20231215074632.82045-1-zhangpeng.00@bytedance.com>
 <20231218202014.mpotsekdkszasn4t@revolver>
 <20231218202845.buffbdq3vhpiv2py@revolver>
 <00ffc2e3-446b-473e-89b9-a859f36e43dd@bytedance.com>
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <00ffc2e3-446b-473e-89b9-a859f36e43dd@bytedance.com>
User-Agent: NeoMutt/20220429
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: 
	=?utf-8?B?dzFXU2w2U2pIU0FEN3Z5Z1M0WFN1U1pqc0VhdE5RWmNOa2ZSOXpsakUzTnIw?=
 =?utf-8?B?UExaRTVmOW12WlpqYTRPTzBvM1dTeXFoN0VkR2g5NFNEV1dpeDdaSUhXSFBq?=
 =?utf-8?B?cCtRK0xHTDIzSHd6RXVaTVVtaXFWbzAwZUxRaEJheSs1Ry9uaUtKL2d5MEFy?=
 =?utf-8?B?SHdRVmh6eS80V0VqTmt2TnZaQTlra3Vkd0tHeU85c3lOS01QcmhkVTA2YXha?=
 =?utf-8?B?MUJsTVRBbEkxMlFxMlgzYUtYU3EyenNMNDZIZmpqeHVYa1I5RlN6UkJlWkRQ?=
 =?utf-8?B?MTVqTkNhcW9XcC95TmczQ25NTEY0QUlTcTJtK1BOVkJMcy9IcU5DSlZGZnp5?=
 =?utf-8?B?OFQwOEJaNjJCS2FrWE4xZEVheUZsYXdWZlhpQlQzYkh1bElEMWtEQk5hc2I2?=
 =?utf-8?B?MjVQc0hMWkZRbFlyTFJ2MTNFSHppVEFkNFdmTkVqUjZHQUFnUlN2a252cUlv?=
 =?utf-8?B?ODVNUm5jTmttWXAwQ1lnclRRZWNEdXRkYkZZM0Q1OVdFQWpmeXlDTkdPdzky?=
 =?utf-8?B?eHljQXJ6UThabEt1cXBEdEJpNlVwbyszVjJNL1ZTNm0yWkE0c2ZiS2VjaGRv?=
 =?utf-8?B?V2RXdnVRYTl5ZFlZMHcyNGk5cUhKRVk1NXFXR2VLZkxFbHNBenpOUkRNT3Jr?=
 =?utf-8?B?blo2TVFLZzEyYVdURjBwL1IwbGNBaDVHZCtMVEQrY0xnLzNqTzVKSDYwMHdn?=
 =?utf-8?B?VG02bnFEaEc1ZWNUaElwdWZ5MmJGNUxwUlpWaDZUOXk2TExtSHpqZzVZczJR?=
 =?utf-8?B?ZjZCcWNGeXcvTHFKSmJkUHVyOWpRb0M2QStzNWVNOFNLNkFzalNtZytxSWR3?=
 =?utf-8?B?MlhKaDMvcXp4Mk5xR0JVTkE4L00xVnM2T1lCVXlGemFrcUNuRmlBVmZnbTcr?=
 =?utf-8?B?bnlUaVJmTFBuZTlIYVdCbi94VXRWTWFWVWJxNjF1TXVPcThHWVNoK2ZQRFpS?=
 =?utf-8?B?czVhMlZnaWxEZ2xzRGk4SDVhMGIwWHRYbnRvaVhQRHBXUUkwNk01SGlNc1Ri?=
 =?utf-8?B?TWpGVXBrNlFESzNta1hHTWVQdDlTcTlPVHVXUXYvWXpuZzQwcXZYUjBHWVpi?=
 =?utf-8?B?R2c1VG9mdkpXSEhmZnh1V0ZnQXpBa1Q2YWJkUFBtSW9pL0tYYXFsQmV4cTZi?=
 =?utf-8?B?aFNIZEdySG1kNld0dVEzZE5aZUtBTWU5ZGNuR3RGeHJGeUNpaGVuVENJZVlh?=
 =?utf-8?B?enRSRThJblptVEltTDRNVC85Y00rTm9HalhNdzYrdUhFSGtuWFJnWEVWSVhU?=
 =?utf-8?B?a1VqbVR0TVlYeWNwWXpvNG9tMVJDUWs2cXNEYy9KZ1FIQkJ4M08vL0c2TTdX?=
 =?utf-8?B?U3FpWjl1QmRCZFNoeWxaR2ZXNW13UG1YWGFYWUJBcGYxdXRiMFE3a3E5ZFNS?=
 =?utf-8?B?K2FmellvR3ZuUlNlOVYxL1F5dmhvRUk3Slh2RGpZbnZLTDFPdXN4ZEN5SHhw?=
 =?utf-8?B?azBzQUFDVUxoWjB5WjIrampOa0xQa0k3N3luT0cwMWlkRU0vQlEyaXQxWXRo?=
 =?utf-8?B?VWMyYnczb1c2cmwzWm5RZTZVaGUydnNXQ3BOZnFsamdEeUsyTGNGWTlNaFMw?=
 =?utf-8?B?ZVBoL3hmd2V5WDRPWnZNRHdhc3hjUmpWazdIaDdyQVdieEVPTE1SVHoxSFJT?=
 =?utf-8?B?OTFpcWtndzFVK3hWV0M3MHJpZW5WQmlWZmovOW9HUHBWclNxeDNmUmhPUGVT?=
 =?utf-8?B?amNtWWdwYWZvTTRQb2txb3grNHZ5Tm5nTkFDblJoMFFsdTJnTFJuL1VzTTZK?=
 =?utf-8?B?dCtoVnJ1K3Q5RDVzcituaHNYcTN3NGVOQmlGMjNab1pYNkFHemw0ajJkNFp6?=
 =?utf-8?B?eWVXcXladkNXbzdqUnVObkhSN3ltdFVqYVlUNTN2VkNRR0FZWkNWVjlBdGsz?=
 =?utf-8?B?SUZRaW1mT21ZZUJieExaQmJjUW5rOXhrY3VmUGE2akhKREJtN3dhTmFYdDhQ?=
 =?utf-8?B?VWxmZ1AvQ0dEeVpycmNBbnFWVWVIbkZ0UmhBUElGd1AzdTEvWitycTNteDg2?=
 =?utf-8?B?bWxBR3BKNCtEWVNRNXZNU09IZlZFdlRZZjh1SlRqWjlLWVVwcEp3b0NnbFNE?=
 =?utf-8?B?Y3FjRTNhTU8rZkU5cElwMXppZ3RrTE1xbUpKRG5xNUNmS3h4c0E1QXlmcFZB?=
 =?utf-8?Q?wM0LHA3aWF7R3Dt4nPA0wGITg?=
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-ExternalHop-MessageData-0: 
	sC3/DZoMYBnt63nW2VGoWihNBfQZwienzrW3dLpRcynvUx63mVfww3AX9SNgChcPwl3m381Jak7aDbe1Ja+iKTUBjIJqZHd1hFasxhs1d6CrGQ2cUmRkDxmF0ZAcflrmfMuffJJZWKf/0pnzmnC8CY2G3lm3hpFWdg3yNphc+Lpc9OE6ftsC+PO/03RVLd9EsPI+f19wagJOt++x3R8wYLMZ7yygtyyD4taJ/3ofwty68M08v5yzQvaVj3cbfH+SfxCg9VAVK0vsiyRgY1smZyQP0B7Cd9eS9NuWrpzxzRuc2jeqaP3xTZDf8NlbMKsr90uXPf2Pp63anCB+3ax/6X52+x1unpSzPtRv3NPjHQZ6yj6sVDdlq5dlacRWg20frdDFkv48yjc6ckQeM9OT8sSaAL8nOUhuRtmDvXNO0sNUhVIoteT0blndFb0p/nS2etwO2SrEK93wHCI5JXVKW4h7FSUjESGYFiX4Vj0pTLzJNOxrE/ertN1ueYmrB7t6c/Ri8AgPvQdX+X1KYHvOnji8+XUDg6+dXDTnc8Zr7Y8TJJIkLRJr8PC2cOt4srHWAg7MZJ6eNcVvCLyPK53Pnxvd4cFx9AfpQnAhcZkGnkU=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 35a5a471-02db-443a-1a56-08dc0072f84e
X-MS-Exchange-CrossTenant-AuthSource: SN6PR10MB3022.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 19 Dec 2023 09:14:57.7119
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: rY2Og/L28Id1JqLxlscpZzPmrKkGglRJ8aZTuHw+uJ9ezdLjp+y72Imrok1I+FLgpneLunZprJpaOyJx3s/y8Q==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DS7PR10MB5085
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.272,Aquarius:18.0.997,Hydra:6.0.619,FMLib:17.11.176.26
 definitions=2023-12-19_04,2023-12-14_01,2023-05-22_02
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 mlxscore=0 spamscore=0
 adultscore=0 phishscore=0 bulkscore=0 mlxlogscore=999 malwarescore=0
 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2311290000
 definitions=main-2312190068
X-Proofpoint-ORIG-GUID: yy0KVZxPv4QhPG-LBu_fmYniXJZ4gJh0
X-Proofpoint-GUID: yy0KVZxPv4QhPG-LBu_fmYniXJZ4gJh0

* Peng Zhang <zhangpeng.00@bytedance.com> [231218 21:34]:
>=20
>=20
> =E5=9C=A8 2023/12/19 04:28, Liam R. Howlett =E5=86=99=E9=81=93:
> > * Liam R. Howlett <Liam.Howlett@Oracle.com> [231218 15:20]:
> > > * Peng Zhang <zhangpeng.00@bytedance.com> [231215 02:46]:
> > > > The last range stored in maple tree is typically quite large. By
> > > > checking if it exceeds the sum of the remaining ranges in that node=
, it
> > > > is possible to avoid checking all other gaps.
> > > >=20
> > > > Running the maple tree test suite in user mode almost always result=
s in
> > > > a near 100% hit rate for this optimization.
> > >=20
> > > This should only be triggered for right-most nodes and root though,
> > > correct (mas->max  =3D=3D ULONG_MAX from just before this)?
> Yes, only for right-most nodes and root.
> > >=20
> > > I wonder if it's worth special case checking the first gap if the nod=
e
> > > min is 0 as well.  Might be worth looking at, but this patch is
> > > certainly worth doing.
> >=20
> > Actually, not just when the min is 0, we have a special case close to
> > here for slot 0 so we could just check the same sort of thing there.
> I think that the first slot in a node does not have any special
> significance. It has a lower probability of being the largest gap,
> so it may not be worth considering.

It has a higher probability of being a gap, but since there is a special
case for it already it won't be checked unless it is a gap.

The left-most node at each level will probably exhibit the same larger
gap in practice except for the root where it will the be end gap - at
least on x86.

Since these will be hit-cache I'm not sure either will make much of a
practical difference though.

> >=20
> > >=20
> > > >=20
> > > > Signed-off-by: Peng Zhang <zhangpeng.00@bytedance.com>
> > >=20
> > > Reviewed-by: Liam R. Howlett <Liam.Howlett@oracle.com>
> > >=20
> > > > ---
> > > >   lib/maple_tree.c | 3 +++
> > > >   1 file changed, 3 insertions(+)
> > > >=20
> > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c
> > > > index c9a970ea20dd..6f241bb38799 100644
> > > > --- a/lib/maple_tree.c
> > > > +++ b/lib/maple_tree.c
> > > > @@ -1518,6 +1518,9 @@ static unsigned long mas_leaf_max_gap(struct =
ma_state *mas)
> > > >   		gap =3D ULONG_MAX - pivots[max_piv];
> > > >   		if (gap > max_gap)
> > > >   			max_gap =3D gap;
> > > > +
> > > > +		if (max_gap > pivots[max_piv] - mas->min)
> > > > +			return max_gap;
> > > >   	}
> > > >   	for (; i <=3D max_piv; i++) {
> > > > --=20
> > > > 2.20.1
> > > >=20
> >=20