Messages in this thread | | | Date | Wed, 7 Apr 1999 00:27:21 +0200 (CEST) | From | Andrea Arcangeli <> | Subject | Re: [patch] arca-vm-2.2.5 |
| |
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 from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |