From owner-cvs-all Thu May 23 19:10:44 2002 Delivered-To: cvs-all@freebsd.org Received: from obsecurity.dyndns.org (adsl-64-169-107-187.dsl.lsan03.pacbell.net [64.169.107.187]) by hub.freebsd.org (Postfix) with ESMTP id 7905F37B40A; Thu, 23 May 2002 19:10:35 -0700 (PDT) Received: by obsecurity.dyndns.org (Postfix, from userid 1000) id C768C66DC0; Thu, 23 May 2002 19:10:34 -0700 (PDT) Date: Thu, 23 May 2002 19:10:34 -0700 From: Kris Kennaway To: Alan Cox Cc: cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <20020523191034.A5058@xor.obsecurity.org> References: <200205240133.g4O1XP047545@freefall.freebsd.org> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-md5; protocol="application/pgp-signature"; boundary="VS++wcV0S1rZb1Fb" Content-Disposition: inline User-Agent: Mutt/1.2.5.1i In-Reply-To: <200205240133.g4O1XP047545@freefall.freebsd.org>; from alc@FreeBSD.org on Thu, May 23, 2002 at 06:33:25PM -0700 Sender: owner-cvs-all@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG --VS++wcV0S1rZb1Fb Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Thu, May 23, 2002 at 06:33:25PM -0700, Alan Cox wrote: > alc 2002/05/23 18:33:25 PDT >=20 > Modified files: > sys/vm vm_map.c vm_map.h=20 > 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.) > =20 > Nothing comes for free: At present, I see a 0.2% slowdown on "buildw= orld" > 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. Awesome! Kris --VS++wcV0S1rZb1Fb Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (FreeBSD) iD8DBQE87aEaWry0BWjoQKURAssyAKC5/Glbo8U6yrWzBVHtdGIx6hcFPgCgl5w9 3MDXdAbv2DTPAaqRA0kbkaw= =9Us+ -----END PGP SIGNATURE----- --VS++wcV0S1rZb1Fb-- To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe cvs-all" in the body of the message