lkml.org 
[lkml]   [2002]   [Jan]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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/

\
 
 \ /
  Last update: 2005-03-22 13:16    [W:0.065 / U:0.268 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site