Re: rbtree for vm_map

On Thu, Oct 30, 2003 at 12:52:29AM +0900, Noriyuki Soda wrote:
> 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?

These results are really great. Let's get rbtree in the tree first
and fix /dev/zero problem later. :-)

Jun-Young

-- 
Bang Jun-Young <[email protected]>