On Thu, Feb 14, 2019 at 02:33:00PM -0800, Matthew Wilcox wrote: >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. > Thanks for your explanation :-) >> >> 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). Sure, I will try to play with this. -- Wei Yang Help you, Help me
