xfs
[Top] [All Lists]

Re: Re: [PATCH 06/14] repair: use a btree instead of a radix tree for

To: Christoph Hellwig <hch@xxxxxxxxxxxxx>
Subject: Re: Re: [PATCH 06/14] repair: use a btree instead of a radix tree for theprefetch queue
From: Barry Naujok <bnaujok@xxxxxxxxxxxxxxx>
Date: Fri, 13 Nov 2009 11:17:40 +1100
Cc: Alex Elder <aelder@xxxxxxx>, Barry Naujok <bnaujok@xxxxxxxxxxxxxxx>, xfs@xxxxxxxxxxx



> Christoph Hellwig <hch@xxxxxxxxxxxxx> wrote:
> 
> On Wed, Oct 21, 2009 at 12:12:33PM -0500, Alex Elder wrote:
> > - I accept that this uses less memory for sparsely populated
> >   key space than radix trees; but it would be nice if that
> >   could be characterized a bit more precisely (i.e., what
> >   will the range of values that'll be represented be, just
> >   how sparse is it, and at what point does this really
> >   pay off?).
> > - Related to the previous one--it would be good to have
> >   a little info about why the value 7 was chosen as the
> >   number of keys per node.  Perhaps I just don't know
> >   enough of the history (or content of the upcoming
> >   patches).
> 
> Maybe Barry still remembers some of this.  I've added his current
> personal address to the Cc list.

Radix tree was instantly dismissed as during my early testing, it actually used 
more memory than the original flat array on a large filesystem!

I experimented with different values for the key, it didn't make a huge 
difference. A short node involves less memory copying and more node splitting 
and merging and tree traversals. Bigger nodes, a lot more memory copying when 
inserting and deleting entries. No clear winner - can tune it for specific 
workloads though (and what Dave Chinner said is correct too and started as my 
basis). 

Barry.

<Prev in Thread] Current Thread [Next in Thread>
  • Re: Re: [PATCH 06/14] repair: use a btree instead of a radix tree for theprefetch queue, Barry Naujok <=