Messages in this thread | | | Date | Thu, 31 Jan 2002 10:32:35 -0800 (PST) | From | Linus Torvalds <> | Subject | Re: [PATCH] Radix-tree pagecache for 2.5 |
| |
On Thu, 31 Jan 2002, Andrea Arcangeli wrote: > > > > 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).
NO.
The radix tree is an index lookup mechanism.
The index is 32 bits.
That's true regardless of how much RAM you have.
> 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.
Considering that the radix tree can _remove_ 8 bytes per "struct page", I suspect you potentially win more memory than you lose.
Linus
- 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/
| |