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

1 files changed, 3 insertions, 1 deletions

diff --git a/sys/vm/vm_map.h b/sys/vm/vm_map.h
index 8ad633f..aff3833 100644
--- a/sys/vm/vm_map.h
+++ b/sys/vm/vm_map.h
@@ -101,6 +101,8 @@ union vm_map_object {
 struct vm_map_entry {
 	struct vm_map_entry *prev;	/* previous entry */
 	struct vm_map_entry *next;	/* next entry */
+	struct vm_map_entry *left;
+	struct vm_map_entry *right;
 	vm_offset_t start;		/* start address */
 	vm_offset_t end;		/* end address */
 	vm_offset_t avail_ssize;	/* amt can grow if this is a stack */
@@ -154,7 +156,7 @@ struct vm_map {
 	vm_size_t size;			/* virtual size */
 	u_char system_map;		/* Am I a system map? */
 	u_char infork;			/* Am I in fork processing? */
-	vm_map_entry_t hint;		/* hint for quick lookups */
+	vm_map_entry_t root;
 	unsigned int timestamp;		/* Version number */
 	vm_map_entry_t first_free;	/* First free space hint */
 	pmap_t pmap;			/* (c) Physical map */