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 Sat, 2005-08-27 at 10:53 -0700, Andrew Morton wrote:
> > a) fix radix_tree_gang_lookup() to use find_next_bit()
> > 
> > b) remove radix_tree_node.count
> > 
> > c) Add a new tag field which simply means "present"
> > 
> > d) remove radix_tree_gang_lookup() and __lookup() altogether
> > 
> > e) Implement radix_tree_gang_lookup() via radix_tree_gang_lookup_tag()
> 
> OK, here it is: the combined version which treats the present bits as a
> private tag, combines __lookup and __lookup_tag and does a fast bitmap
> search for both.
>
> ...
>
> +#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.