Re: [Fwd: Re: + radixtree-look-aside-cache.patch added to -mm tree]
- From: Wu Fengguang <wfg@xxxxxxxxxxxxxxxx>
- Date: Thu, 25 May 2006 18:23:46 +0800
On Thu, May 25, 2006 at 03:45:22PM +1000, Nick Piggin wrote:
Introduce a set of lookup functions to radix tree for the read-ahead logic.
Other access patterns with high locality may also benefit from them.
Your radix tree stuff doesn't _seem_ like a bad idea, but I would be
much more comfortable if it was in a completely different patchset.
Ie. implement your readahead stuff using the current radix-tree API,
then show eg. 15% CPU reduction on workload X when using look-aside
cache for blah.
It is more complexity, and the intention might be nice, but it might
not actually help as much (or at all) as you think: eg. it might
increase cache footprint and actually slow things down.
I have oprofile numbers against the look-aside cache:
http://marc.theaimsgroup.com/?l=linux-kernel&m=113231595618167&w=2
Indeed, there's not much gain. It's ok to remove it.
- radix_tree_lookup_parent(root, index, level)
Perform partial lookup, return the @level'th parent of the slot at
@index.
- radix_tree_cache_xxx()
Init/Query the cache.
- radix_tree_cache_lookup(root, cache, index)
Perform lookup with the aid of a look-aside cache.
For sequential scans, it has a time complexity of 64*O(1) +
1*O(logN).
Typical usage:
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);
}
Still not really convinced with this. I can't see why you shouldn't just
use a gang lookup or "scan" type function. Let's take your real example:
+static pgoff_t find_segtail_backward(struct address_space *mapping,
+ pgoff_t index, unsigned long
max_scan)
+{
+ struct radix_tree_cache cache;
+ struct page *page;
+ pgoff_t origin;
+
+ origin = index;
+ if (max_scan > index)
+ max_scan = index;
+
+ cond_resched();
BTW. cond_resched here? It should normally be in the caller if they expect
really high latency.
Right, will remove it.
+ radix_tree_cache_init(&cache);
+ read_lock_irq(&mapping->tree_lock);
+ for (; origin - index < max_scan;) {
+ page = radix_tree_cache_lookup(&mapping->page_tree,
+ &cache, --index);
+ if (page) {
+ read_unlock_irq(&mapping->tree_lock);
+ return index + 1;
+ }
+ }
+ read_unlock_irq(&mapping->tree_lock);
This should just be a scan_page_backward (not scan_hole), should it not?
I didn't find other usages of the radix tree cache after a quick scan, but
if you point them out, let's see if they can't be replaced with something
else.
Sure ok. The radix tree cache is trivial to remove.
However this function is not performance critical, so I'd like to
rest on the poor man's scan_page_backward() implementation :)
int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
-void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
-void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
+void *radix_tree_lookup_parent(struct radix_tree_root *, unsigned long,
+ unsigned int);
+void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned
long);
void *radix_tree_delete(struct radix_tree_root *, unsigned long);
+unsigned int radix_tree_cache_count(struct radix_tree_cache *cache);
+void *radix_tree_cache_lookup_parent(struct radix_tree_root *root,
+ struct radix_tree_cache *cache,
+ unsigned long index, unsigned int level);
Nitpick: I don't really like the name lookup_parent. No better suggestions
though ;)
But the function seems really nasty for an exported API: callers should
have no concept of the internals of the data structure. If you just need
it to implement these inline functions, maybe prepend it with a double
underscore.
It was once named lookup_node, and was distasted by Christoph Lameter.
Maybe we can settle with __radix_tree_lookup_parent() and only use it
inside radix-tree.c/.h.
+void *radix_tree_lookup_parent(struct radix_tree_root *root,
+ unsigned long index, unsigned int level)
{
unsigned int height, shift;
- struct radix_tree_node **slot;
+ struct radix_tree_node *slot;
height = root->height;
if (index > radix_tree_maxindex(height))
return NULL;
- if (height == 0 && root->rnode)
- return (void **)&root->rnode;
-
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
- slot = &root->rnode;
+ slot = root->rnode;
This couldn't work: we have direct data now in -mm (unless that's been
thrown out).
Should be ok: the while loop below will be skipped if height == 0.
- while (height > 0) {
- if (*slot == NULL)
+ while (height > level) {
+ if (slot == NULL)
return NULL;
- slot = (struct radix_tree_node **)
- ((*slot)->slots +
- ((index >> shift) & RADIX_TREE_MAP_MASK));
+ slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
- return (void **)slot;
+ return slot;
+}
+EXPORT_SYMBOL(radix_tree_lookup_parent);
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long
index)
{
- return __lookup_slot(root, index);
+ struct radix_tree_node *node;
+
+ node = radix_tree_lookup_parent(root, index, 1);
+ return node->slots + (index & RADIX_TREE_MAP_MASK);
}
EXPORT_SYMBOL(radix_tree_lookup_slot);
radix_tree_lookup_parent can return NULL, right? Oops.
Thanks, I'm amazed that it didn't crashed my machine ;)
Regards,
Wu
-
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/
- References:
- [Fwd: Re: + radixtree-look-aside-cache.patch added to -mm tree]
- From: Nick Piggin
- [Fwd: Re: + radixtree-look-aside-cache.patch added to -mm tree]
- Prev by Date: Re: [PATCH 3/3] pci: gt96100eth use pci probing
- Next by Date: Re: [PATCH 1/2] request_firmware without a device
- Previous by thread: [Fwd: Re: + radixtree-look-aside-cache.patch added to -mm tree]
- Next by thread: [PATCH 2/2]: ufs: not usual amounts of fragments per block
- Index(es):
Relevant Pages
|
|
