Re: rbtree for vm_map

I measured the mmap benchmarks in http://bulk.fefe.de/scalability/
with the vm map rbtree patch ported from OpenBSD by yamt.

As you suppose, the rbtree patch made the results much better as follows:
    the mmap benchmark results:
	http://www.sra.co.jp/people/soda/scalability/mmap.gif
	http://www.sra.co.jp/people/soda/scalability/mmap.zoom.gif
	http://www.sra.co.jp/people/soda/scalability/mmaptouch.gif

    mmap()ing many small files:
	http://www.sra.co.jp/people/soda/scalability/open.gif
	http://www.sra.co.jp/people/soda/scalability/manymap-mmap.gif
	http://www.sra.co.jp/people/soda/scalability/manymap-mmap.zoom.gif
	http://www.sra.co.jp/people/soda/scalability/manymap-touch.gif

    Hardware:
	Celeron 300MHz
    Software:
	NetBSD-splay		: NetBSD-1.6ZE on Oct 26, 2003
	NetBSD-splay+rbtree	: NetBSD-1.6ZE on Oct 26, 2003 + rbtree patch
	Linux-2.6.0-test8	: RedHat9 w/ linux-2.6.0-test8 kernel

But as shown in the following mail by yamt,
	http://mail-index.netbsd.org/tech-kern/2003/08/26/0000.html
The rbtree one is worse than stock NetBSD in the /dev/zero mapping
benchmark as follows:
	http://www.sra.co.jp/people/soda/scalability/devzero.gif
This is because vm map entries for /dev/zero are merged into one entry
in this case.
So, the result on stock NetBSD may become worse even with /dev/zero
mapping, if there are some reasons which make the entries unable to be
merged, e.g. if there are gaps or other type mappings between the
/dev/zero mappings.
The following benchmark shows the fact:
	http://www.sra.co.jp/people/soda/scalability/devzeromod.gif
This is a result with a patch attached at the end of this mail.

I also tried the following case to be sure:
	http://www.sra.co.jp/people/soda/scalability/anon.gif
		... use MAP_ANON|MAP_PRIVATE mapping
	http://www.sra.co.jp/people/soda/scalability/anonmod.gif
		... use MAP_ANON|MAP_PRIVATE mapping
		    with similar patch at the end of this mail.
This shows same behavior with the /dev/zero benchmark.

The followings are the results of other benchmarks in the yamt's mail:
	http://www.sra.co.jp/people/soda/scalability/file.gif
	http://www.sra.co.jp/people/soda/scalability/walk.gif

For people who don't think that the mmap benchmark doesn't concern
with real applications, the following is a result of benchmark which
does many pthread_create() and pthreads_join():
	http://www.sra.co.jp/people/soda/scalability/pthread.gif
As you see in this result, the rbtree patch helps a lot with
the case that a program creates more than 1,000 threads simultaneously.
Perhaps you think that's nonsense, but there are people who use
even 10,000 threads simultaneously. See the following web page,
for example:
	http://www.kegel.com/c10k.html

BTW, the fork benchmark modified by Niels becomes slightly worse as
follows with the rbtree patch:
	http://www.sra.co.jp/people/soda/scalability/forkbench-niels.gif
Because of the cost to maintain rbtree?
--
soda

Index: walk.c
===================================================================
--- walk.c	Mon Aug 25 08:06:43 2003
+++ walk.c	Wed Oct 29 09:48:12 2003
@@ -22,7 +22,6 @@
 	void *vp;
 	int i, j;
 	size_t mapsz = PAGE_SIZE * PPM;
-	int prot = PROT_READ;
 	int nmap = NMAP;
 	int fd;
 	int nloop = NLOOP;
@@ -55,7 +54,9 @@
 		void *map[nmap];
 
 		for (i = 0; i < nmap; i++) {
-			vp = mmap(NULL, mapsz, prot, MAP_FILE|MAP_SHARED, fd, 0);
+			vp = mmap(NULL, mapsz,
+			    (i & 1) ? PROT_READ : PROT_READ|PROT_WRITE,
+			    MAP_FILE|MAP_SHARED, fd, 0);
 			if (vp == MAP_FAILED)
 				err(1, "mmap");
 			map[i] = vp;