Date: Fri, 24 May 2002 00:02:56 -0500 From: Alan Cox <alc@cs.rice.edu> To: Alfred Perlstein <bright@mu.org> Cc: Mike Silbersack <silby@silby.com>, cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <20020524050256.GD22588@cs.rice.edu> In-Reply-To: <20020524034230.GE54960@elvis.mu.org> References: <20020524023327.GB17481@cs.rice.edu> <20020523221001.X18281-100000@patrocles.silby.com> <20020524034230.GE54960@elvis.mu.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, May 23, 2002 at 08:42:30PM -0700, Alfred Perlstein wrote: > * 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. > I had thought some of these issues and addressed them to some extent in my response to Mike. I'll add a little more here: 1. Historically, in the SMP-enabled Mach VM sources, the vm_map's hint was guarded by a separate mutex from the vm_map's general-purpose shared/exclusive lock. Tomorrow, if we return to supporting shared/exclusive locks on the vm_map, that same mutex will be the mutex controlling access to the root of the splay tree. In contrast to the lock on the entire vm_map, this mutex is only held for a short time. In our case, that would now be for the duration of vm_map_entry_splay() and the assignment to the root. 2. Even supposing that the vm_map entries are still in your L2 or L3 cache when you next access the vm_map, the number of cache lines modified is logarithmic in the number of entries in the vm_map. That's not very many. :-) So, I don't buy the contention argument. Furthermore, I would point out the following thing: Splay trees take advantage of any locality in the access pattern. In a splay tree, the last k accessed items are at most log k distance from the root. So, going back to point #2 above, the more locality in the access pattern, the fewer the writes. 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?20020524050256.GD22588>