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 16136C433EF for ; Wed, 23 Feb 2022 16:45:25 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 89DF78D0029; Wed, 23 Feb 2022 11:45:24 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 84B1A8D0011; Wed, 23 Feb 2022 11:45:24 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 712D98D0029; Wed, 23 Feb 2022 11:45:24 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0158.hostedemail.com [216.40.44.158]) by kanga.kvack.org (Postfix) with ESMTP id 47E938D0011 for ; Wed, 23 Feb 2022 11:45:24 -0500 (EST) Received: from smtpin25.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay03.hostedemail.com (Postfix) with ESMTP id DFD028249980 for ; Wed, 23 Feb 2022 16:45:23 +0000 (UTC) X-FDA: 79174620126.25.C30CFD3 Received: from casper.infradead.org (casper.infradead.org [90.155.50.34]) by imf16.hostedemail.com (Postfix) with ESMTP id 4591918000F for ; Wed, 23 Feb 2022 16:45:22 +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=OZnbt00zUnS8m67NiJ13USs9kJgohLQZFhnBYLNvjWA=; b=t1hv85IizsOcqi6ScA1osGJdhK C6T3qQUf4HaqeHhLFp0kdn1ZhElva1yJ37TUA70l21Xfxoj2OCyr4OyoZ8jwvaooeUzIcBH0Z3rc9 aoxZfCuHWwjZGoBx9soiJXVHsNEIgQCt/w4O0fij7MtB+vszov3WveCOCXXeEsMXet7T+TWahh3wV 15thF9YS0I8dkpfQ0jNZtMFC7YnqUQR+SpjLyw7X4pXat596haEGKgzBj/1NgOUUwKR0vizkQa1I5 KhR6dZD1S4rvd2XsLrkq8iyf+vyfS4eLvUEyaEhxofPZ0/i35bVrpDGhmscA0bvUWrnAfhE2tq6Vl GRanFDog==; Received: from willy by casper.infradead.org with local (Exim 4.94.2 #2 (Red Hat Linux)) id 1nMulL-003vdN-GX; Wed, 23 Feb 2022 16:45:11 +0000 Date: Wed, 23 Feb 2022 16:45:11 +0000 From: Matthew Wilcox To: Mel Gorman Cc: Andrew Morton , Liam Howlett , "maple-tree@lists.infradead.org" , "linux-mm@kvack.org" , "linux-kernel@vger.kernel.org" Subject: Re: [PATCH v6 00/71] Introducing the Maple Tree Message-ID: References: <20220215143728.3810954-1-Liam.Howlett@oracle.com> <20220216114700.f9473d88144dc59fc4d764fb@linux-foundation.org> <20220223163509.GH4423@techsingularity.net> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20220223163509.GH4423@techsingularity.net> Authentication-Results: imf16.hostedemail.com; dkim=pass header.d=infradead.org header.s=casper.20170209 header.b=t1hv85Ii; dmarc=none; spf=none (imf16.hostedemail.com: domain of willy@infradead.org has no SPF policy when checking 90.155.50.34) smtp.mailfrom=willy@infradead.org X-Rspam-User: X-Rspamd-Server: rspam10 X-Rspamd-Queue-Id: 4591918000F X-Stat-Signature: jip55ee3zjjmswgq717mitigga865zbu X-HE-Tag: 1645634722-779237 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 Wed, Feb 23, 2022 at 04:35:09PM +0000, Mel Gorman wrote: > On Wed, Feb 16, 2022 at 08:24:34PM +0000, Matthew Wilcox wrote: > > On Wed, Feb 16, 2022 at 11:47:00AM -0800, Andrew Morton wrote: > > > On Tue, 15 Feb 2022 14:37:44 +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 > > > > that a non-overlapping range-based tree would be beneficial, especially > > > > one with a simple interface. The first user that is covered in this > > > > patch set is the vm_area_struct, where three data structures are > > > > replaced by the maple tree: the augmented rbtree, the vma cache, and the > > > > linked list of VMAs in the mm_struct. The long term goal is to reduce > > > > or remove the mmap_sem contention. > > > > > > Has a path been chosen which gets us from here to significant reduction > > > in mmap_lock overhead? > > > > > > If so, what's the plan and what must be done? > > > > I would say there are still competing ideas for how that is to be done. > > > > First, the Maple Tree is independent (to a certain extent) of all the > > approaches to reducing mmap_lock overhead. It's a better data structure > > for VMA lookup than the rbtree. Set against that, it has higher overhead > > for modifications. That means that benchmarks which primarily measure > > modification overhead see worse performance. We believe this is not > > representative of real workloads, and indeed we see ~parity on workloads > > like git and make -jN. > > I'm way behind and only got around to looking at SPF properly today. Maple > is working its way up my list and I need to gather new data but I did > have old data queued from a time when I thought I would get around to > maple tree soon. The big result that stood was was brk performance from > will-it-scale but for processes specifically Yup, we know about the brk1 regression. It's a really unrealistic benchmark, which is why we added brk2. To quote the commit message: Linux has this horrendously complicated anon_vma structure that you don't care about, but the upshot is that after calling fork(), each process that calls brk() gets a _new_ VMA created. That is, after calling brk() the first time, the process address space looks like this: 557777fab000-557777ff0000 rw-p 00000000 00:00 0 [heap] 557777ff0000-557777ff1000 rw-p 00000000 00:00 0 [heap] so what brk1 is actually testing is how long it takes to create & destroy a new VMA. This does not match what most programs do -- most will call exec() which resets the anon_vma structures and starts each program off with its own heap. And if you do have a multi-process program which uses brk(), chances are it doesn't just oscillate betwee zero and one extra pages of heap compared to its parent. A better test starts out by allocating one page on the heap and then throbs between one and two pages instead of throbbing between zero and one page. That means we're actually testing expanding and contracting the heap instead of creating and destroying a new heap. For realism, I wanted to add actually accessing the memory in the new heap, but that doesn't work for the threaded case -- another thread might remove the memory you just allocated while you're allocating it. Threaded programs give each thread its own heap anyway, so this is kind of a pointless syscall to ask about its threaded scalability. Anyway, here's brk2.c. It is not very different from brk1.c, but the performance results are quite different (actually worse by about 10-15%).