Date: Thu, 23 May 2002 20:42:30 -0700 From: Alfred Perlstein <bright@mu.org> To: Mike Silbersack <silby@silby.com> Cc: Alan Cox <alc@cs.rice.edu>, 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> In-Reply-To: <20020523221001.X18281-100000@patrocles.silby.com> References: <20020524023327.GB17481@cs.rice.edu> <20020523221001.X18281-100000@patrocles.silby.com>
next in thread | previous in thread | raw e-mail | index | archive | help
* Mike Silbersack <silby@silby.com> [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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20020524034230.GE54960>