Messages in this thread | | | Date | Mon, 7 Sep 1998 14:31:18 +0400 | From | Savochkin Andrey Vladimirovich <> | Subject | Re: [TIMINGS] Re: 2.1.xxx makes Electric Fence 22x slower |
| |
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
| |