Re: [PATCH] make radix tree gang lookup faster by using a bitmap search

[James Bottomley <James.Bottomley@SteelEye.com>]

On Tue, 2005-08-30 at 10:56 +1000, Nick Piggin wrote:
> Sonny Rao wrote:
> 
> >On Mon, Aug 29, 2005 at 01:37:48PM +1000, Nick Piggin wrote:
> >
> >>s/common/only ?
> >>
> >>But the page tree is indexed by file offset rather than virtual
> >>address, and we try to span the file's pagecache with the smallest
> >>possible tree. So it will tend to make the trees taller.
> >>
> >>
> >
> >I did some experiments with different map-shift values,
> >interestingly overall read throughput didn't change much but the
> >cpu-utilization of radix_tree_lookup (from oprofile) changed quite a
> >bit, especially in the case of MAP_SHIFT == 4 :  
> >
> >http://www.linuxsymposium.org/2005/linuxsymposium_procv2.pdf 
> >
> >Look on page 80, where I have the table.
> >
> Nice. So we can see that 6 is a pretty good choice of shift,
> 4 is too low. That doesn't tell us much about 5, but if you
> fit the curve, 5 should be between 14 and 15 ... so getting
> expensive.

Actually, several crucial pieces of data are missing.  It's not hard to
imagine that the results for 8, 10 and 12 are all equal to within the
error bars.  The missing piece of data, of course, is how big the file
was, which would tell us how deep the tree was.

> Of course, different systems and different workloads will
> be different. But I'd be wary of going below 6 unless there
> is a good reason.
> 
> >>I'm curious: what do the benchmarks say about your gang lookup?
> >>
> >
> >Gang-lookup isn't used in the page-cache lookups presently, so I'm
> >not sure why optimizing it is very important -- unless someone is
> >planning on implementing gang-lookups for page-cache reads. This would
> >also cut down on number times a lock is taken and released (expensive,
> >in the case of rwlock).  Perhaps there is another reason?
> >
> >
> 
> Gang lookup is mainly used on IO paths but also on truncate,
> which is a reasonably fast path on some workloads (James,
> this is my suggestion for what you should test - truncate).

Actually, I don't think I can test this.  In order to show a difference
between index 5 and index 6 on 32 bit, I'd have to deal with files > 4GB
in size.  My 32 bit machines are the voyagers and only have 4GB discs.

The machine with all the huge discs, is, naturally, ia64.

James