Date: Thu, 30 Sep 2010 13:01:50 -0500 From: Alan Cox <alan.l.cox@gmail.com> To: Andre Oppermann <andre@freebsd.org> Cc: freebsd-hackers <freebsd-hackers@freebsd.org>, freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <AANLkTikboxBKY=sGbdr-CYN7XuhsLSK8rThAJQRoqhP5@mail.gmail.com> In-Reply-To: <4CA4CAE6.2090108@freebsd.org> References: <4CA4BCD2.4070303@freebsd.org> <4CA4CAE6.2090108@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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. I teach class shortly. I'll provide more details later. Regards, Alan
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?AANLkTikboxBKY=sGbdr-CYN7XuhsLSK8rThAJQRoqhP5>