Re: [PATCH] Radix-tree pagecache for 2.5

[Andrea Arcangeli]

On Thu, Jan 31, 2002 at 10:32:35AM -0800, Linus Torvalds wrote:
> 
> 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.

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.

I'm confused by the comments I heard so far, but well I don't want to
bother you further until I have clear how this data structure is layed
out exactly. I mainly wanted to give a warning, to be sure some point is
evalulated properly before integration.

> Considering that the radix tree can _remove_ 8 bytes per "struct page", I
> suspect you potentially win more memory than you lose.

of course if we add kmalloc to the pagecache code we can drop such part
from the page structure with the hashtable too.

Andrea