Re: [PATCH] Radix-tree pagecache for 2.5

[Linus Torvalds]

On Thu, 31 Jan 2002, Andrea Arcangeli 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.

Think of the page tables. We can have 64GB of memory, and the page tables
will shrink and grow dynamically to match the needs for virtual memory.
The radix tree is no different, except it ends up being a bit more
aggressive about shrinking by virtue of not always using the maximum depth.

(A fixed depth tree is much simpler, and has equivalent memory use for
not-very-dense mappings. But file mappings are 99% dense).

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

But you still need the hashtable.

Right now the hashtable is _roughly_ the size of 4 bytes per physical page
in the machine - and it was done that way explicitly to avoid havin gto
walk the chains. That's a LOT of memory.

For example, on my 2GB machine, I have 2MB worth of hash-tables.

In addition, each "struct page" has 8 bytes in it, so we have a total of
12 bytes per page just for the hash chains.

And yes, you could use kmalloc to allocate the hash chain entries. But
we're _guaranteed_ that 12 bytes, and kmalloc overhead might make it
worse.

In short: the radix tree certainly isn't any worse.

		Linus