From owner-freebsd-hackers@FreeBSD.ORG Thu Sep 30 21:10:38 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 6E5FB1065679 for ; Thu, 30 Sep 2010 21:10:38 +0000 (UTC) (envelope-from andre@freebsd.org) Received: from c00l3r.networx.ch (c00l3r.networx.ch [62.48.2.2]) by mx1.freebsd.org (Postfix) with ESMTP id D91088FC1B for ; Thu, 30 Sep 2010 21:10:37 +0000 (UTC) Received: (qmail 22456 invoked from network); 30 Sep 2010 21:02:33 -0000 Received: from localhost (HELO [127.0.0.1]) ([127.0.0.1]) (envelope-sender ) by c00l3r.networx.ch (qmail-ldap-1.03) with SMTP for ; 30 Sep 2010 21:02:33 -0000 Message-ID: <4CA4FCD1.6010709@freebsd.org> Date: Thu, 30 Sep 2010 23:10:41 +0200 From: Andre Oppermann User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.9) Gecko/20100825 Thunderbird/3.1.3 MIME-Version: 1.0 To: Alfred Perlstein References: <4CA4BCD2.4070303@freebsd.org> <20100930183853.GX49807@elvis.mu.org> In-Reply-To: <20100930183853.GX49807@elvis.mu.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-hackers , 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 21:10:38 -0000 On 30.09.2010 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. This would break the underlying assumption of the splay tree. A splay tree is not a balanced tree. With this approach you can easily get stuck in a sub-optimal situation with many lookups traversing N-1 nodes and not getting the cache benefit. When N nodes are traversed for an outlier, and the rotate happens, you rotate again on the next lookup or you get stuck in another sub-optimal situation. In effect you get the worst of an splay tree while not being able to gain on the amortization effect when the root node hit rate is high. > 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. As the assumption of the algorithm is broken I don't think it's useful to spend time on this. I'd rather try and add a last-match pointer to the RB tree to take home the locality effect in vmmap. -- Andre