lkml.org 
[lkml]   [2005]   [Aug]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] make radix tree gang lookup faster by using a bitmap search
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.

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

\
 
 \ /
  Last update: 2005-08-29 02:57    [W:0.066 / U:2.584 seconds]
©2003-2017 Jasper Spaans. hosted at Digital OceanAdvertise on this site