Messages in this thread | | | Date | Thu, 31 Jan 2002 19:02:02 +0100 | From | Andrea Arcangeli <> | Subject | Re: [PATCH] Radix-tree pagecache for 2.5 |
| |
On Thu, Jan 31, 2002 at 09:46:52AM -0800, Linus Torvalds wrote: > On Thu, 31 Jan 2002, Andrea Arcangeli wrote: > > > > but with the radix tree (please correct me if I'm wrong) the height will > > increase eventually, no matter what (so it won't be an effective O(1) > > like the hashtable provides in real life, not the worst case, the common > > case). With the hashtable the height won't increase instead. > > No. > > The radix tree is basically O(1), because the maximum depth of a 7-bit > radix tree is just 5. The index is only a 32-bit number.
then it will break on archs with more ram than 1<<(32+PAGE_CACHE_SHIFT).
Also there must be some significant memory overhead that can be triggered with a certain layout of pages, in some configuration it should take much more ram than the hashtable if I understood well how it works.
Also its O(1) may be slower than the O(N) of the hashtable in the 99% of the cases.
> > We could, in fact, make all page caches use a fixed-depth tree, which is > clearly O(1). But the radix tree is slightly faster and tends to use less > memory under common loads, so.. > > Remember: you must NOT ignore the constant part of a "O(x)" equation. > Hashes tend to be effectively O(1) under most loads, but they have cache > costs, and they have scalability costs that a radix tree doesn't have.
the scalability cost I obviously agree :) (however on some workload with all tasks on the same inode, the scalability cost remains the same).
Andrea - 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/
| |