From owner-cvs-all Thu May 23 22: 3: 7 2002 Delivered-To: cvs-all@freebsd.org Received: from cs.rice.edu (cs.rice.edu [128.42.1.30]) by hub.freebsd.org (Postfix) with ESMTP id 8953637B406; Thu, 23 May 2002 22:02:58 -0700 (PDT) Received: from localhost (localhost [127.0.0.1]) by cs.rice.edu (Postfix) with ESMTP id B067A4A9D3; Fri, 24 May 2002 00:02:57 -0500 (CDT) Received: by cs.rice.edu (Postfix, from userid 19572) id 16FA34A9B6; Fri, 24 May 2002 00:02:56 -0500 (CDT) Date: Fri, 24 May 2002 00:02:56 -0500 From: Alan Cox To: Alfred Perlstein Cc: Mike Silbersack , 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> References: <20020524023327.GB17481@cs.rice.edu> <20020523221001.X18281-100000@patrocles.silby.com> <20020524034230.GE54960@elvis.mu.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20020524034230.GE54960@elvis.mu.org> User-Agent: Mutt/1.3.28i X-Virus-Scanned: by AMaViS snapshot-20010714 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 On Thu, May 23, 2002 at 08:42:30PM -0700, Alfred Perlstein wrote: > * 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. > 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