From owner-cvs-all  Thu May 23 18:33:30 2002
Delivered-To: cvs-all@freebsd.org
Received: from freefall.freebsd.org (freefall.FreeBSD.org [216.136.204.21])
	by hub.freebsd.org (Postfix) with ESMTP
	id 42B9C37B400; Thu, 23 May 2002 18:33:25 -0700 (PDT)
Received: (from alc@localhost)
	by freefall.freebsd.org (8.11.6/8.11.6) id g4O1XP047545;
	Thu, 23 May 2002 18:33:25 -0700 (PDT)
	(envelope-from alc)
Message-Id: <200205240133.g4O1XP047545@freefall.freebsd.org>
From: Alan Cox <alc@FreeBSD.org>
Date: Thu, 23 May 2002 18:33:25 -0700 (PDT)
To: cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org
Subject: cvs commit: src/sys/vm vm_map.c vm_map.h
X-FreeBSD-CVS-Branch: HEAD
Sender: owner-cvs-all@FreeBSD.ORG
Precedence: bulk
List-ID: <cvs-all.FreeBSD.ORG>
List-Archive: <http://docs.freebsd.org/mail/> (Web Archive)
List-Help: <mailto:majordomo@FreeBSD.ORG?subject=help> (List Instructions)
List-Subscribe: <mailto:majordomo@FreeBSD.ORG?subject=subscribe%20cvs-all>
List-Unsubscribe: <mailto:majordomo@FreeBSD.ORG?subject=unsubscribe%20cvs-all>
X-Loop: FreeBSD.ORG

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