Date: Thu, 23 May 2002 19:10:34 -0700 From: Kris Kennaway <kris@obsecurity.org> To: Alan Cox <alc@FreeBSD.org> 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> In-Reply-To: <200205240133.g4O1XP047545@freefall.freebsd.org>; from alc@FreeBSD.org on Thu, May 23, 2002 at 06:33:25PM -0700 References: <200205240133.g4O1XP047545@freefall.freebsd.org>
index | next in thread | previous in thread | raw e-mail
[-- Attachment #1 --] On Thu, May 23, 2002 at 06:33:25PM -0700, Alan Cox wrote: > 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. Awesome! Kris [-- Attachment #2 --] -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (FreeBSD) iD8DBQE87aEaWry0BWjoQKURAssyAKC5/Glbo8U6yrWzBVHtdGIx6hcFPgCgl5w9 3MDXdAbv2DTPAaqRA0kbkaw= =9Us+ -----END PGP SIGNATURE-----home | help
Want to link to this message? Use this
URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20020523191034.A5058>