Examining the VM splay tree effectiveness

[Alan Cox]

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@ 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 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.

I teach class shortly.  I'll provide more details later.

Regards,
Alan