linux-kernel - Re: [PATCH] xarray: Document erasing entries during iteration

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Sat, 16 Feb 2019 21:53:05 +0000
From:   Wei Yang <richard.weiyang@...il.com>
To:     Matthew Wilcox <willy@...radead.org>
Cc:     Wei Yang <richard.weiyang@...il.com>,
        "Tobin C. Harding" <tobin@...nel.org>,
        linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] xarray: Document erasing entries during iteration

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