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