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
Date: Thu, 14 Feb 2019 14:33:00 -0800 [thread overview]
Message-ID: <20190214223300.GH12668@bombadil.infradead.org> (raw)
In-Reply-To: <20190214221652.rwctk7wrocpojtfy@master>
On Thu, Feb 14, 2019 at 10:16:52PM +0000, Wei Yang wrote:
> On Wed, Feb 13, 2019 at 08:12:58AM -0800, Matthew Wilcox wrote:
> >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.
>
> Wow, really a HUGE work.
Yes ... but necessary. Have to pay down the technical debt.
> >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).
>
> Two questions from my curiosity:
>
> 1. Why you come up the idea to replace radix tree with XArray even they
> use the same data structure?
The radix tree API was just awful to use. I tried to convert some users
with their own resizing-array-of-pointers to use the radix tree, and I
gave up in disgust. I believe the XArray is much simpler to use.
> 2. The worst-case performance is related to the data structure itself?
Yes. Consider the case where you store a pointer at its own address in
the data structure. It'll allocate 11 nodes occupying one-and-a-half pages
of RAM in order to store a single pointer.
> >> 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.
>
> So sometimes XArray does a little worse?
>
> Why this happens whey XArray and radix tree has the same data structure?
>
> Interesting.
I'm not sure there are any cases where the XArray does worse.
Feel free to run your own measurements ... the test cases in
tools/testing/radix-tree can always do with being improved ;-) (that
directory is a bit misnamed as it now features tests for the radix tree,
IDR, IDA and XArray).
next prev parent reply other threads:[~2019-02-14 22:33 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-02-12 7:29 [PATCH] xarray: Document erasing entries during iteration Tobin C. Harding
2019-02-12 13:51 ` Matthew Wilcox
2019-02-13 14:47 ` Wei Yang
2019-02-13 16:12 ` Matthew Wilcox
2019-02-14 22:16 ` Wei Yang
2019-02-14 22:33 ` Matthew Wilcox [this message]
2019-02-16 21:53 ` Wei Yang
2019-02-13 1:13 ` Tobin C. Harding
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190214223300.GH12668@bombadil.infradead.org \
--to=willy@infradead.org \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=richard.weiyang@gmail.com \
--cc=tobin@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).