Examining the VM splay tree effectiveness
andre at freebsd.org
Thu Sep 30 21:10:38 UTC 2010
On 30.09.2010 20:38, Alfred Perlstein wrote:
> Your observations on the effectiveness of the splay tree
> mirror the concerns I have with it when I read about it.
> I have always wondered though if the splay-tree algorithm
> was modified to only perform rotations when a lookup required
> more than "N" traversals to reach a node.
> This would self-balance the tree and maintain cache without
> the expense of writes for nearly all lookups.
This would break the underlying assumption of the splay tree.
A splay tree is not a balanced tree. With this approach you
can easily get stuck in a sub-optimal situation with many
lookups traversing N-1 nodes and not getting the cache benefit.
When N nodes are traversed for an outlier, and the rotate happens,
you rotate again on the next lookup or you get stuck in another
sub-optimal situation. In effect you get the worst of an splay
tree while not being able to gain on the amortization effect
when the root node hit rate is high.
> I'm wondering if you have the time/interest in rerunning
> your tests, but modifying the algorithm to only rebalance
> the splay if a lookup requires more than let's say 3, 5, 7
> or 10 traversals.
As the assumption of the algorithm is broken I don't think it's
useful to spend time on this. I'd rather try and add a last-match
pointer to the RB tree to take home the locality effect in vmmap.
More information about the freebsd-hackers