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

[Nick Piggin <nickpiggin@yahoo.com.au>]

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.

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).

> I actually talk about this a little bit at the end of the paper as
> well. I think gang-lookup when readahead has been turned off is
> potentially a good way to go, since we are fairly confident that all
> the pages are in the cache, unfortunately I haven't had (and probably
> won't) have any time to implement it. 

It is fairly difficult to do gang lookups in the cached cases,
but probably not impossible. But the code around there is already
probably as complicated as we would want it to be, so it would be
nice if it could be cleaned up first (or maybe it is already as
simple as possible :( ).

> Of course, if we go the lockless path it's much less important.

Yep, that's what I'm thinking. The lockless patches I have can do
lockless gang lookup and use it for truncate. It should be usable
in the same way as the current locked gang lookup is.

But of course gang lookup is only useful if a single read() call
asks for more than 1 page - is that a performance critical path?

Nick


Send instant messages to your online friends http://au.messenger.yahoo.com 
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/