Date: Thu, 30 Sep 2010 20:24:19 +0200 From: Ivan Voras <ivoras@freebsd.org> To: freebsd-hackers@freebsd.org Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <i82kkj$os4$1@dough.gmane.org> In-Reply-To: <AANLkTikboxBKY=sGbdr-CYN7XuhsLSK8rThAJQRoqhP5@mail.gmail.com> References: <4CA4BCD2.4070303@freebsd.org> <4CA4CAE6.2090108@freebsd.org> <AANLkTikboxBKY=sGbdr-CYN7XuhsLSK8rThAJQRoqhP5@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On 09/30/10 20:01, Alan Cox wrote: > On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann <andre@freebsd.org> 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?
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?i82kkj$os4$1>