lkml.org 
[lkml]   [2005]   [Nov]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH 04/16] radix-tree: look-aside cache
    Wu Fengguang wrote:
    > This introduces a set of lookup functions to radix tree for the read-ahead
    > logic. Other access patterns with high locality may also benefit from them.
    >

    Hi Wu,

    Does this cache add much performance compared with simple repeated
    lookups? If the access patterns are highly local, the top of the
    radix tree should be in cache.

    I worry that it is a fair bit of extra complexity for something
    slow like the IO path - however I haven't looked at how you use the
    cache.

    > Most of them are best inlined, so some macros/structs in .c are moved into .h.
    >

    I would not inline them. You'd find that the extra icache misses
    that costs outweighs the improvements for larger functions.

    > +
    > +struct radix_tree_node {
    > + unsigned int count;
    > + void *slots[RADIX_TREE_MAP_SIZE];
    > + unsigned long tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS];
    > +};
    > +

    Would be much nicer if this weren't declared in the header file, so
    people don't start trying to use the nodes where they shouldn't.
    This ought to be possible after uninlining a couple of things.

    > struct radix_tree_root {
    > unsigned int height;
    > gfp_t gfp_mask;
    > struct radix_tree_node *rnode;
    > };
    >
    > +/*
    > + * Support access patterns with strong locality.
    > + */

    Do you think you could provide a simple 'use case' for an overview
    of how you use the cache and what calls to make?

    > +struct radix_tree_cache {
    > + unsigned long first_index;
    > + struct radix_tree_node *tree_node;
    > +};
    > +

    > +static inline void radix_tree_cache_init(struct radix_tree_cache *cache)
    > +{
    > + cache->first_index = 0x77;
    > + cache->tree_node = NULL;
    > +}
    > +
    > +static inline int radix_tree_cache_size(struct radix_tree_cache *cache)
    > +{
    > + return RADIX_TREE_MAP_SIZE;
    > +}
    > +
    > +static inline int radix_tree_cache_count(struct radix_tree_cache *cache)
    > +{
    > + if (cache->first_index != 0x77)
    > + return cache->tree_node->count;
    > + else
    > + return 0;
    > +}
    > +

    What's 0x77 for? And what happens if your cache gets big enough that
    the first index is 0x77?

    Thanks,
    Nick

    --
    SUSE Labs, Novell Inc.

    Send instant messages to your online friends http://au.messenger.yahoo.com

    -
    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-11-10 00:31    [W:4.360 / U:0.028 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site