lkml.org 
[lkml]   [2005]   [Nov]   [10]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH 04/16] radix-tree: look-aside cache
    Hi Nick,

    On Thu, Nov 10, 2005 at 10:31:09AM +1100, Nick Piggin wrote:
    > 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.
    It just guarantees constant lookup time for small/large files.

    My context based read-ahead code has been quite tricky just to avoid many radix
    tree lookups. I made it much simple and robust in the recent versions by just
    scanning through the cache. With the help of look-aside cache, the performance
    remains comparable with the tricky one. Sorry, the oprofile log was overwrote.
    But if you do need some numbers about the cache, I'll make one.

    >
    > 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 are one-liners, except radix_tree_cache_lookup_node(). Which is about 10
    lines. Currently it is always called with a constant @level, where inline can
    help. Only several speed critical functions call it, so I guess icache misses
    will not be a big problem. But I do feel it ugly to expose internal data
    structures in .h :(
    >
    > >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.
    Ok. I'll try it.
    >
    > > 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?
    Ok, here it is:

    void func() {
    + struct radix_tree_cache cache;
    +
    + radix_tree_cache_init(&cache);
    read_lock_irq(&mapping->tree_lock);
    for(;;) {
    - page = radix_tree_lookup(&mapping->page_tree, index);
    + page = radix_tree_cache_lookup(&mapping->page_tree, &cache, index);
    }
    read_unlock_irq(&mapping->tree_lock);
    }

    >
    > >+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?
    Sorry for the ugly code. It is better written as:
    if (cache->first_index & RADIX_TREE_MAP_MASK)
    return 0;
    else
    return cache->tree_node->count;

    The 0x77 is an invalid value that will be detected in radix_tree_cache_lookup_node():

    mask = ~((RADIX_TREE_MAP_SIZE << (level * RADIX_TREE_MAP_SHIFT)) - 1);

    ---> if ((index & mask) == cache->first_index)
    return cache->tree_node->slots[i];

    node = radix_tree_lookup_node(root, index, level + 1);

    It can be initialized to 1, 0xFF, or any i that (i & RADIX_TREE_MAP_MASK != 0).
    I'd better just init it as RADIX_TREE_MAP_MASK.

    Regards,
    Wu
    -
    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 12:04    [W:2.470 / U:0.200 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site