Date: Thu, 23 May 2002 18:33:25 -0700 (PDT) From: Alan Cox <alc@FreeBSD.org> To: cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <200205240133.g4O1XP047545@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
alc 2002/05/23 18:33:25 PDT
Modified files:
sys/vm vm_map.c vm_map.h
Log:
o Replace the vm_map's hint by the root of a splay tree. By design,
the last accessed datum is moved to the root of the splay tree.
Therefore, on lookups in which the hint resulted in O(1) access,
the splay tree still achieves O(1) access. In contrast, on lookups
in which the hint failed miserably, the splay tree achieves amortized
logarithmic complexity, resulting in dramatic improvements on vm_maps
with a large number of entries. For example, the execution time
for replaying an access log from www.cs.rice.edu against the thttpd
web server was reduced by 23.5% due to the large number of files
simultaneously mmap()ed by this server. (The machine in question has
enough memory to cache most of this workload.)
Nothing comes for free: At present, I see a 0.2% slowdown on "buildworld"
due to the overhead of maintaining the splay tree. I believe that
some or all of this can be eliminated through optimizations
to the code.
Developed in collaboration with: Juan E Navarro <jnavarro@cs.rice.edu>
Reviewed by: jeff
Revision Changes Path
1.236 +103 -80 src/sys/vm/vm_map.c
1.82 +3 -1 src/sys/vm/vm_map.h
To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe cvs-all" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200205240133.g4O1XP047545>