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
