On Thu, 31 Jan 2002, Linus Torvalds wrote:
> > then there must be some collision handling that raise the complexity to
> > O(N) like with the hashtable, if the depth is fixed and if 32bits of
> > index are enough regardless of how many entries are in the tree.
>
> No collisions. Each mapping has its own private tree. And mappings are
> virtually indexed by 32 bits. No hashes, no collisions, no nothing.
Yes, it's very nice. Anton Blanchard has benchmarked both patch variants
(tree vs. scalable-hash page buckets) for SMP scalability against the
stock hash, on big RAM, many CPUs boxes, via dbench load. He has found
performance of radix trees vs. scalable hash to be at least equivalent. (i
think Anton has a few links to show the resulting graphs.)
In fact the radix trees showed a slight performance/scalability edge in
some parts of the performance curve. So given the fact that hashes/buckets
were *purely* designed for speed/scalability and not for RAM usage, this
proves that radix trees are superior. Plus the locking is much simpler
than for the hash buckets solution. Which make radix trees a clear winner
IMO.
Ingo
-
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/
This archive was generated by hypermail 2b29 : Thu Jan 31 2002 - 21:01:37 EST