Messages in this thread | | | Date | Thu, 10 Nov 2005 17:50:09 +1100 | From | Nick Piggin <> | Subject | Re: [PATCH 04/16] radix-tree: look-aside cache |
| |
Wu Fengguang wrote:
>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. > >
But it isn't *really* constant time lookups? I mean you'll always have the O(logn) lookup. Amortised I guess that becomes insignificant?
Briefly: is there a reason why you couldn't use gang lookups instead? (Sorry I haven't been able to read and understand your actual readahead code).
>>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); > } > >
OK, I guess that seems reasonable. You have introduced some other APIs as well...
Profile numbers would be great for the cached / non-cached cases.
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/
| |