Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Date:   Wed, 13 Feb 2019 08:12:58 -0800
From:   Matthew Wilcox <willy@infradead.org>
To:     Wei Yang <richard.weiyang@gmail.com>
Cc:     "Tobin C. Harding" <tobin@kernel.org>,
        linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH] xarray: Document erasing entries during iteration
Message-ID: <20190213161258.GS12668@bombadil.infradead.org>
References: <20190212072958.17373-1-tobin@kernel.org>
 <20190212135129.GL12668@bombadil.infradead.org>
 <20190213144744.ifejzbxrbaltivwc@master>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20190213144744.ifejzbxrbaltivwc@master>
User-Agent: Mutt/1.9.2 (2017-12-15)
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

On Wed, Feb 13, 2019 at 02:47:44PM +0000, Wei Yang wrote:
> On Tue, Feb 12, 2019 at 05:51:29AM -0800, Matthew Wilcox wrote:
> >That is _fine_.  As you know I hope to get rid of the radix tree soon ;-)
> 
> You mean replace radix tree in whole kernel? That would be a big effort.

Already mostly done.

http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/xarray-conv

The only remaining user of the radix tree in that tree is the IDR.  So
now I'm converting the IDR users over to the XArray as well.


But that isn't what I was talking about.  At the moment, the radix
tree and the XArray use the same data structure.  It has good best-case
performance, but shockingly bad worst-case performance.  So we're looking
at replacing the data structure, which won't require changing any of the
users (maybe the page cache ... that has some pretty intimate knowledge
of exactly how the radix tree works).

> BTW, have we compared the performance difference?

It's in the noise.  Sometimes the XArray does a little better because
the APIs encourage the user to do things in a more efficient way.
Some of the users are improved just because the original author didn't
know about a more efficient way of doing what they wanted to do.