From owner-cvs-all Thu May 23 20:42:42 2002 Delivered-To: cvs-all@freebsd.org Received: from elvis.mu.org (elvis.mu.org [192.203.228.196]) by hub.freebsd.org (Postfix) with ESMTP id 26CE737B40F; Thu, 23 May 2002 20:42:36 -0700 (PDT) Received: by elvis.mu.org (Postfix, from userid 1192) id F0533AE1EE; Thu, 23 May 2002 20:42:30 -0700 (PDT) Date: Thu, 23 May 2002 20:42:30 -0700 From: Alfred Perlstein To: Mike Silbersack Cc: Alan Cox , cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <20020524034230.GE54960@elvis.mu.org> References: <20020524023327.GB17481@cs.rice.edu> <20020523221001.X18281-100000@patrocles.silby.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20020523221001.X18281-100000@patrocles.silby.com> User-Agent: Mutt/1.3.27i 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 * Mike Silbersack [020523 20:11] wrote: > > On Thu, 23 May 2002, Alan Cox wrote: > > > P.S. I hope this motivates others on this list to look at splay trees. > > They are extemely easy to work with and to implement. (Notice that vm_map.c > > only grew by 24 lines.) > > Hm, they look pretty neat from what I've been able to gather. It looks > like they would be a great replacement for hash tables in many cases. > What are the practical downsides? I'm surprised that I haven't heard of > them before. I spoke to the Linux Alan Cox about using splay trees for the vm page lookup instead of the AVL tree they have. The problem is that you need exclusive (writer) locks for all accesses when you use a splay tree (unless of course you have a modified tree that only rebalances when exclusively locked). Also all the modification required (to rebalance) may induce contention rather than effective caching when the tree isn't frequently added-to/remove-from. I'm not sure if they actually tried a splay implementation, but at least that was his opinion on the matter. -- -Alfred Perlstein [alfred@freebsd.org] 'Instead of asking why a piece of software is using "1970s technology," start asking why software is ignoring 30 years of accumulated wisdom.' Tax deductible donations for FreeBSD: http://www.freebsdfoundation.org/ To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe cvs-all" in the body of the message