Date: Thu, 30 Sep 2010 22:56:56 +0200 From: Andre Oppermann <andre@freebsd.org> To: alc@freebsd.org Cc: freebsd-hackers <freebsd-hackers@freebsd.org>, Alan Cox <alan.l.cox@gmail.com>, freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <4CA4F998.5000908@freebsd.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 30.09.2010 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. This is indeed an expected property of the splay tree. For the vmmap the root node hit rate, that is the least recently accessed node, is very high. Other nodes that are frequently accessed as well should be high up too. Nonetheless the churn rate on the nodes in tree rotations is considerable. The question now is whether we can get the same positive effect but with less negative side effects. Of particular concern is the CPU cache dirtying and thrashing by the splay rotations. Especially with today's and tomorrows many core, many socket, many threads/processes machines. Another concern is worst case behavior when the root node hit rate is low. Currently this is the case in vmpage for certain. It may also become a concern in vmmap with the use of memguard (fragmenting the address space) or an adversary trying to exploit worst case behavior on a shared host by mapping only every other page. This concern is validated when accepting the measurement by the 2008 SoC student Mayur (thanks to rdivacky@ for digging up his page): http://wiki.freebsd.org/MayurShardul/VM_Algorithm_Improvement In the measurements of his alternative radix trie implementation the lookup time is *230 times less* than for the splay tree (as measured by with the TSC). The description of the performed benchmark is extremely sparse and it is not clear what access pattern he simulated. Probably a random lookup pattern which is of course very bad for the splay tree. Any balanced tree will be better for random lookups. Whether his measured improvement is due to using a radix trie or if it would perform equally to a normal balanced binary tree I can't say (yet). > I teach class shortly. I'll provide more details later. -- Andre
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4CA4F998.5000908>