Re: [patch] arca-vm-2.2.5

Chuck Lever (cel@monkey.org)
Sat, 24 Apr 1999 23:22:32 -0400 (EDT)

On Wed, 7 Apr 1999, Stephen C. Tweedie wrote:
> On Wed, 7 Apr 1999 00:27:21 +0200 (CEST), Andrea Arcangeli
> <andrea@e-mind.com> said:
>
> > 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.
>
> Trees are O(log n) for insert/delete, with a high constant of
> proportionality (ie. there can be quite a lot of work to be done even
> for small log n). Trees also occupy more memory per node. Hashes are
> O(1) for insert and delete, and are a _fast_ O(1). The page cache needs
> fast insert and delete.

i had a few minutes the other day, so i extracted just the rb-tree part of
2.2.5-arca10, and benchmarked it against 2.2.5 and against the hash tuning
patch i'm working on. i ran this on our 512M 4-way Dell PowerEdge 6300.

ref - 2.2.5 kernel with 4000 process slots and b_state fix

rbt - 2.2.5 kernel with 4000 process slots and rbtree patch applied
(b_state fix *not* applied)
hash - 2.2.5 kernel with an older version of my hash tuning patch applied
(b_state fix applied)

160 concurrent scripts. all of the benchmark fits in memory.

ref: 3725.8 s=15.23
rbt: 3893.3 s=9.82
hash: 4007.3 s=15.95

"hash" tunes the page cache, the buffer cache, the dentry cache, and the
inode cache. "rbt" just replaces the page cache with per-inode rbtrees.
i think the rbtree patch compares pretty favorably for very large memory
machines.

- Chuck Lever

--
corporate:	<chuckl@netscape.com>
personal:	<chucklever@netscape.net> or <cel@monkey.org>


The Linux Scalability project:
	http://www.citi.umich.edu/projects/linux-scalability/






-
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/