Messages in this thread | | | Date | Thu, 31 Jan 2002 22:34:33 +0100 (CET) | From | Ingo Molnar <> | Subject | Re: [PATCH] Radix-tree pagecache for 2.5 |
| |
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/
| |