Date: Sat, 25 May 2002 14:07:01 -0500 (CDT) From: Mike Silbersack <silby@silby.com> To: Alan Cox <alc@cs.rice.edu> Cc: Alfred Perlstein <bright@mu.org>, <cvs-committers@FreeBSD.org>, <cvs-all@FreeBSD.org> Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <20020525140040.U3212-100000@patrocles.silby.com> In-Reply-To: <20020524050256.GD22588@cs.rice.edu>
next in thread | previous in thread | raw e-mail | index | archive | help
On Fri, 24 May 2002, Alan Cox wrote: > 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 I think your argument for splay trees is compelling. Even if there is contention between processors waiting on the tree mutex, I can't see it being a large problem; the vm system probably doesn't need extremely fine grained locking anyway. I'm wondering if we could take advantage of splay trees in other cases where we currently use hash tables, such as for tcp socket lookup, etc. The only problem there is that we'd have to sort on 96 bits worth of data, which could be a bit of a pain on < 96 bit architectures. Hmph. Mike "Silby" Silbersack 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?20020525140040.U3212-100000>