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

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

On Sun, 2005-08-28 at 18:35 -0700, Andrew Morton wrote:
> > Well ... It's my opinion (and purely unsubstantiated, I suppose) that
> > it's more efficient on 32 bit platforms to do bit operations on 32 bit
> > quantities, which is why I changed the radix tree map shift to 5 for
> > that case.
> > 
> > It also makes much cleaner code than having to open code checks on
> > variable sized bitmaps.

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

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

James