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

From: Nick Piggin
Date: Sun Aug 28 2005 - 22:41:51 EST


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 -
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/