From owner-freebsd-hackers@FreeBSD.ORG Thu Sep 30 18:24:30 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 3E593106566B for ; Thu, 30 Sep 2010 18:24:30 +0000 (UTC) (envelope-from freebsd-hackers@m.gmane.org) Received: from lo.gmane.org (lo.gmane.org [80.91.229.12]) by mx1.freebsd.org (Postfix) with ESMTP id B6F7B8FC13 for ; Thu, 30 Sep 2010 18:24:29 +0000 (UTC) Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1P1Nnw-00066M-ME for freebsd-hackers@freebsd.org; Thu, 30 Sep 2010 20:24:28 +0200 Received: from 93-138-123-63.adsl.net.t-com.hr ([93.138.123.63]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 30 Sep 2010 20:24:28 +0200 Received: from ivoras by 93-138-123-63.adsl.net.t-com.hr with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 30 Sep 2010 20:24:28 +0200 X-Injected-Via-Gmane: http://gmane.org/ To: freebsd-hackers@freebsd.org From: Ivan Voras Date: Thu, 30 Sep 2010 20:24:19 +0200 Lines: 33 Message-ID: References: <4CA4BCD2.4070303@freebsd.org> <4CA4CAE6.2090108@freebsd.org> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: 93-138-123-63.adsl.net.t-com.hr User-Agent: Mozilla/5.0 (X11; U; FreeBSD amd64; en-US; rv:1.9.1.9) Gecko/20100620 Thunderbird/3.0.4 In-Reply-To: Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 30 Sep 2010 18:24:30 -0000 On 09/30/10 20:01, Alan Cox wrote: > On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann wrote: > >> On 30.09.2010 18:37, Andre Oppermann wrote: >> >>> Just for the kick of it I decided to take a closer look at the use of >>> splay trees (inherited from Mach if I read the history correctly) in >>> the FreeBSD VM system suspecting an interesting journey. >>> >> >> Correcting myself regarding the history: The splay tree for vmmap was >> done about 8 years ago by alc@ to replace a simple linked list and was >> a huge improvement. The change in vmpage from a hash to the same splay >> tree as in vmmap was committed by dillon@ about 7.5 years ago with some >> involvement of alc@. >> ss > Yes, and there is a substantial difference in the degree of locality of > access to these different structures, and thus the effectiveness of a splay > tree. When I did the last round of changes to the locking on the vm map, I > made some measurements of the splay tree's performance on a JVM running a > moderately large bioinformatics application. The upshot was that the > average number of map entries visited on an access to the vm map's splay > tree was less than the expected depth of a node in a perfectly balanced > tree. Sorry, I'm not sure how to parse that - are you saying that the splaying helped, making the number of nodes visited during tree search lesser than the average node depth in a balanced tree? Even if so, wouldn't the excessive bandwidth lost in the splaying ops (and worse - write bandwidth) make it unsuitable today?