Re: Examining the VM splay tree effectiveness

On 30.09.2010 20:01, Alan Cox wrote:
> On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann<andre_at_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_at_ 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_at_ about 7.5 years ago with some
>> involvement of alc_at_.
>> 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_at_ 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