Examining the VM splay tree effectiveness

[Ivan Voras]

On 09/30/10 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@ 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.

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?