Re: [patch] arca-vm-2.2.5

[Andrea Arcangeli <andrea@e-mind.com>]

On Tue, 6 Apr 1999, Stephen C. Tweedie wrote:

>Trees are bad for this sort of thing in general: they can be as fast as
>hashing for lookup, but are much slower for insert and delete
>operations.  Insert and delete for the page cache _must_ be fast.

It's not so obvious to me. I sure agree that an O(n) insertion/deletion is
far too slow but a O(log(n)) for everything could be rasonable to me. And
trees don't worry about unluky hash behavior.

And for the record my plan would be to put the top of the tree directly in
the inode struct. And then to queue all cached pages that belongs to such
inode in the per-inode cache-tree. So there would be no need to always
check also the inode field in find_inode() and reading small files would
be _drammatically_ fast and immediate even if there are 5giga of cache
allocated. I think this behavior will become interesting.

Maybe you are 100% right in telling me that RB-trees will lose, but I
would like to try it out someday...

Andrea Arcangeli

--
To unsubscribe, send a message with 'unsubscribe linux-mm my@address'
in the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/