From owner-freebsd-hackers@FreeBSD.ORG Thu Sep 30 19:06:33 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 818D6106564A for ; Thu, 30 Sep 2010 19:06:33 +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 06EEE8FC0C for ; Thu, 30 Sep 2010 19:06:32 +0000 (UTC) Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1P1OSc-0007Di-TD for freebsd-hackers@freebsd.org; Thu, 30 Sep 2010 21:06:30 +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 21:06:30 +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 21:06:30 +0200 X-Injected-Via-Gmane: http://gmane.org/ To: freebsd-hackers@freebsd.org From: Ivan Voras Date: Thu, 30 Sep 2010 21:06:20 +0200 Lines: 42 Message-ID: References: <4CA4BCD2.4070303@freebsd.org> <20100930183853.GX49807@elvis.mu.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: <20100930183853.GX49807@elvis.mu.org> 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 19:06:33 -0000 On 09/30/10 20:38, Alfred Perlstein wrote: > Andre, > > Your observations on the effectiveness of the splay tree > mirror the concerns I have with it when I read about it. > > I have always wondered though if the splay-tree algorithm > was modified to only perform rotations when a lookup required > more than "N" traversals to reach a node. > > This would self-balance the tree and maintain cache without > the expense of writes for nearly all lookups. > > I'm wondering if you have the time/interest in rerunning > your tests, but modifying the algorithm to only rebalance > the splay if a lookup requires more than let's say 3, 5, 7 > or 10 traversals. I see two possible problems with this: 1: the validity of this heuristics, since the splay is not meant to help the current lookup but future lookups, and if you "now" require e.g. 5-deep traversal, (barring external information about the structures - meybe some inner relationship of the nodes can be exploitet) it is I think about the same probability that the next lookup will hit that rotated node or the former root node. 2: rotating only on the N'th lookup would have to go like this: 1. take a read-only lock 2. make the lookup, count the depth 3. if depth > N: 1. relock for write (lock upgrade will not always work) 2. recheck if the tree is still the same; bail if it isn't 3. do the splay 4. unlock i.e. suspiciously complicated. That is, if you want to take advantage of read paralelism; if the tree is write-locked all the time it's simpler but only inefficient. Of course, real-world measurements trump theory :)