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

James


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