Re: [PATCH 04/16] radix-tree: look-aside cache

[Nick Piggin]

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@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/