From: Wei Yang <richard.weiyang@gmail.com>
To: Matthew Wilcox <willy@infradead.org>
Cc: Wei Yang <richard.weiyang@gmail.com>,
"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 22:16:52 +0000 [thread overview]
Message-ID: <20190214221652.rwctk7wrocpojtfy@master> (raw)
In-Reply-To: <20190213161258.GS12668@bombadil.infradead.org>
On Wed, Feb 13, 2019 at 08:12:58AM -0800, Matthew Wilcox wrote:
>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.
>
Wow, really a HUGE work.
>
>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?
2. The worst-case performance is related to the data structure itself?
>> 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.
--
Wei Yang
Help you, Help me
next prev parent reply other threads:[~2019-02-14 22:17 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 [this message]
2019-02-14 22:33 ` Matthew Wilcox
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=20190214221652.rwctk7wrocpojtfy@master \
--to=richard.weiyang@gmail.com \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=tobin@kernel.org \
--cc=willy@infradead.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