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

[Andrew Morton <akpm@osdl.org>]

James Bottomley <James.Bottomley@SteelEye.com> wrote:
>
> On Sun, 2005-08-28 at 17:52 -0700, Andrew Morton wrote:
> > > +#if BITS_PER_LONG == 32
> > > +#define RADIX_TREE_MAP_SHIFT	5
> > > +#elif BITS_PER_LONG == 64
> > > ...
> > >  struct radix_tree_node {
> > > -	unsigned int	count;
> > >  	void		*slots[RADIX_TREE_MAP_SIZE];
> > > -	unsigned long	tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS];
> > > +	unsigned long	tags[RADIX_TREE_TAGS];
> > >  };
> > 
> > I don't see why the above change was necessary?  Why not stick with the
> > current more flexible sizing option?
> > 
> > Note that the RADIX_TREE_MAP_FULL trick can still be used.  It just has to
> > be put inside a `for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++)' loop,
> > which will vanish if RADIX_TREE_TAG_LONGS==1.
> 
> 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.

We changed the node size a few years back.  umm.... 
http://www.ussg.iu.edu/hypermail/linux/kernel/0206.2/0141.html

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.