![]() | |||||||||||||
Messages in this thread |
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. Later, David S. Miller davem@dm.cobaltmicro.com - 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 | |||||||||||||