![]() | |||||||||||||
Messages in this thread |
On Mon, Sep 07, 1998 at 03:07:51AM -0700, David S. Miller wrote: > From: Bruno Haible <haible@ilog.fr> > Date: Mon, 7 Sep 1998 12:02:12 +0200 (MET DST) > > And I dispute the "good scalability" claim. In the case of the app > David Gadbois sketched (lots of 64KB VMA segments), the hash > function of all segments returns the same value, thus we are back > to n/2 VMA accesses in each operation on average, as in the > linear-list scheme. Whereas AVL has 2*log(n)/log(2) accesses in the > _worst_case_. > > All you have shown is that the hash function needs tuning, and nothing > more. > > Talk to researchers on this topic (I do), tree schemes only begin to > give you back _lookup_ performance at 1,000 or so entires compared to > any hash or skiplist scheme. And trees _never_ give you the > insert/delete characteristics hash/skiplist schemes do (balancing > overhead of trees vs. hash's constant time insert delete). > > I picked a suboptimal hash function in my "not ready for prime time, > untuned" implementation, so shoot me. Well, I'm finishing a fuzzy hash implementation with find_vma not less than 20% better than the previous for the case of small number of VMAs. It's not only the hash function that can be tuned :-) Best regards Andrey V. Savochkin - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/faq.html | ||||||||||||
| Last update: 2005-03-22 12:44 [from the cache] ©2003-2008 | |||||||||||||