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 8328AC433F5 for ; Tue, 26 Apr 2022 20:23:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 023216B0073; Tue, 26 Apr 2022 16:23:25 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id F156C6B0074; Tue, 26 Apr 2022 16:23:24 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id DDD746B0075; Tue, 26 Apr 2022 16:23:24 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (relay.hostedemail.com [64.99.140.26]) by kanga.kvack.org (Postfix) with ESMTP id CFE296B0073 for ; Tue, 26 Apr 2022 16:23:24 -0400 (EDT) Received: from smtpin26.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay10.hostedemail.com (Postfix) with ESMTP id A08B6EFC for ; Tue, 26 Apr 2022 20:23:24 +0000 (UTC) X-FDA: 79400155128.26.882692B Received: from casper.infradead.org (casper.infradead.org [90.155.50.34]) by imf29.hostedemail.com (Postfix) with ESMTP id 384B2120052 for ; Tue, 26 Apr 2022 20:23:21 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=In-Reply-To:Content-Type:MIME-Version: References:Message-ID:Subject:Cc:To:From:Date:Sender:Reply-To: Content-Transfer-Encoding:Content-ID:Content-Description; bh=mwa7X/DoIUYu9hVhfOkZkhZH7rVCuWPYP5Vab781DGM=; b=MEERirgAFqgieTtSNaCHB/+ynL FaFpxb1rKiiD9IXT7ObhE+QIWSGL80BvDr5428oa9ASLDoTt9kGtRYJHQvsEPM2eoLWqnDnkbCLOl DuZoq/T4+UT0uENCCuzCO5X4/pAykTO2Dvdh7vCBfKDeiyn7hNK8x2kLub2ifegMlOFBDViVNWBi+ NCbM7jmNDtuzVC6X7xyTwaZj5VvIZSA0/W3WTORuFn8kmoOc7fEWjxy76fEcvwbuXl6ousM4KiKI1 26k/4wB4+gi0I9S3y8CN8h5Q7IpB0CTbNWfe+/b4XTWk+t3BdWNrmhZ1AYqgJ/fZHP3hDlq9oW8Xy dAJ3jGkA==; Received: from willy by casper.infradead.org with local (Exim 4.94.2 #2 (Red Hat Linux)) id 1njRiL-009z23-0v; Tue, 26 Apr 2022 20:23:13 +0000 Date: Tue, 26 Apr 2022 21:23:12 +0100 From: Matthew Wilcox To: Andrew Morton Cc: Liam Howlett , "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" , Yu Zhao Subject: Re: [PATCH v8 00/70] Introducing the Maple Tree Message-ID: References: <20220426150616.3937571-1-Liam.Howlett@oracle.com> <20220426130857.09f40743b42b5f0bf4f19a59@linux-foundation.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20220426130857.09f40743b42b5f0bf4f19a59@linux-foundation.org> X-Stat-Signature: kz79w8i8a8y9bgwam48w8ap8b96qe4eh Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=infradead.org header.s=casper.20170209 header.b=MEERirgA; spf=none (imf29.hostedemail.com: domain of willy@infradead.org has no SPF policy when checking 90.155.50.34) smtp.mailfrom=willy@infradead.org; dmarc=none X-Rspam-User: X-Rspamd-Server: rspam01 X-Rspamd-Queue-Id: 384B2120052 X-HE-Tag: 1651004601-667844 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: On Tue, Apr 26, 2022 at 01:08:57PM -0700, Andrew Morton wrote: > On Tue, 26 Apr 2022 15:06:19 +0000 Liam Howlett wrote: > > The maple tree is an RCU-safe range based B-tree designed to use modern > > processor cache efficiently. There are a number of places in the kernel > > I think it would be helpful to expand on "a number of places". > Specifically which places? The page cache would be a good place to use it once it has a few more features to bring it up to par with the radix tree. I can go into more detail if you want. In general, anywhere that's using the IDR/Radix Tree/XArray would benefit. The radix tree has some pretty poor space consumption properties, particularly for anyone using the cyclic variants. Many users of the rbtree would have better performance if converted to the maple tree. Ultimately, it's going to be incumbent on people who know their own chunk of the kernel to say "Oh, yes, I can use that data structure", rather than on Liam to go around converting everybody's code for them.