From owner-freebsd-current@FreeBSD.ORG Thu Sep 30 22:06:56 2010 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 19FCE106566C for ; Thu, 30 Sep 2010 22:06:56 +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 7D9D08FC19 for ; Thu, 30 Sep 2010 22:06:55 +0000 (UTC) Received: (qmail 22777 invoked from network); 30 Sep 2010 21:58:50 -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:58:50 -0000 Message-ID: <4CA509FE.30303@freebsd.org> Date: Fri, 01 Oct 2010 00:06:54 +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: Roman Divacky References: <4CA4BCD2.4070303@freebsd.org> <20100930172439.GA34369@freebsd.org> <4CA4CCF8.1050300@freebsd.org> <20100930174900.GA37733@freebsd.org> <20100930180417.GA39381@freebsd.org> <4CA504AD.8000102@freebsd.org> In-Reply-To: <4CA504AD.8000102@freebsd.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 30 Sep 2010 22:06:56 -0000 On 30.09.2010 23:44, Andre Oppermann wrote: > On 30.09.2010 20:04, Roman Divacky wrote: >> On Thu, Sep 30, 2010 at 07:49:00PM +0200, Roman Divacky wrote: >>> On Thu, Sep 30, 2010 at 07:46:32PM +0200, Andre Oppermann wrote: >>>> On 30.09.2010 19:24, Roman Divacky wrote: >>>>> are you aware of Summer of Code 2008 project by Mayur Shardul? >>>> >>>> I remember that there was this project but I never saw any numbers >>>> or other outcome of it. Haven't checked p4 to look at the code >>>> though. >>> >>> there's a little something: >>> >>> http://wiki.freebsd.org/MayurShardul/VM_Algorithm_Improvement >> >> and the actual patch + userspace implementation + benchmarking suite >> is here: >> >> http://code.google.com/p/google-summer-of-code-2008-freebsd/downloads/detail?name=Mayur_Shardul.tar.gz&can=2&q= >> >> >> it looks like a solid work with solid results to me > > I just took a look (not in-depth though) at the patch and can't follow > your conclusion. It is not ready to go into svn in its current state. > > Even though it is called a radix trie it doesn't look like one. On first > impression it looks much more like an AA tree. A radix trie, which we > already have in our network routing table code, is a variable length > (mask) tree that does path compression. See net/radix.[ch] and > http://en.wikipedia.org/wiki/Radix_tree Thinking more about this I can't see any advantage of the radix trie becoming useful for the vmmap. The index of the vmmap is the address range and can't be expressed in a path compressable power of 2 quantity and is non-overlapping. The key for the trie, a pointer, has a fixed small size and can't be optimized away. And it is not a balanced tree. Many keys in the same region lead to long node traversals. In short: VMmap and a radix trie have an impedance mismatch and are unfit for each other imho. -- Andre