Date: Thu, 30 Sep 2010 23:44:13 +0200 From: Andre Oppermann <andre@freebsd.org> To: Roman Divacky <rdivacky@freebsd.org> Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <4CA504AD.8000102@freebsd.org> In-Reply-To: <20100930180417.GA39381@freebsd.org> References: <4CA4BCD2.4070303@freebsd.org> <20100930172439.GA34369@freebsd.org> <4CA4CCF8.1050300@freebsd.org> <20100930174900.GA37733@freebsd.org> <20100930180417.GA39381@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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 Extrapolating in a complete guesstimating way from the lookup function I'd say it may perform only slightly better in an ideal case than a RB tree but with the added overall expense of requiring external memory to store the index and branch nodes. This is probably a nasty disadvantage. -- Andre
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4CA504AD.8000102>