Date: Thu, 23 May 2002 22:41:26 -0500 From: Alan Cox <alc@cs.rice.edu> To: Mike Silbersack <silby@silby.com> Cc: cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <20020524034126.GC22588@cs.rice.edu> 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
On Thu, May 23, 2002 at 10:11:41PM -0500, Mike Silbersack 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. > In comparison to the more widely known schemes for creating height-balanced binary search trees, such as AVL (ick!) and red-black trees, splay trees only guarantee _amortized_ logarithmic performance. In other words, any single, isolated operation may be O(n), but the average over a sequence of operations will be logarithmic. So, if you need a hard logarithmic bound on every single operation, splay trees are not appropriate. Secondarily, the structure of the splay tree is potentially modified on every operation. This means that you'll need an exclusive lock just to perform a lookup(). If, and when, we reimplement shared locking on vm_maps, this means that we'll need to introduce a simple mutex on the splay tree's root that will synchronize changes to the tree regardless of whether any vm_map entries are being added or subtracted from the vm_map. (The old SMP-enabled Mach VM sources from which we sprung had a simple mutex on the vm_map's hint anyway.) Why haven't you seen them mentioned in more places? Amortized complexity proofs aren't trivial. That's enough to keep splay trees out of most college text books. Regards, Alan 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?20020524034126.GC22588>