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

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

James Bottomley wrote:
> On Sun, 2005-08-28 at 18:35 -0700, Andrew Morton wrote:

>>It does make the tree higher and hence will incur some more cache missing
>>when descending the tree.
> 
> 
> Actually, I don't think it does:  the common user is the page tree.
> Obviously, I've changed nothing on 64 bits, so we only need to consider
> what I've done on 32 bits.  A page size is almost universally 4k on 32
> bit, so we need 20 bits to store the page tree index.  Regardless of
> whether the index size is 5 or 6, that gives a radix tree depth of 4.
> 

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.

> 
>>We changed the node size a few years back.  umm.... 
>>http://www.ussg.iu.edu/hypermail/linux/kernel/0206.2/0141.html
> 
> 
> Yes, but that was to reduce the index size from 7 to 6 for slab
> allocation reasons.  I've just reduced it to 5 on 32 bit.
> 
> 
>>It would be a little bit sad to be unable to make such tuning adjustments
>>in the future.  Not a huge loss, but a loss.
> 
> 
> Well .. OK .. If the benchmarks say I've slowed us down on 32 bits, I'll
> put the variable sizing back in the tag array.
> 

I'm curious: what do the benchmarks say about your gang lookup?

Thanks,
Nick

-- 
SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com