On 30.09.2010 20:38, Alfred Perlstein wrote:
Andre,
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.
--
Andre
_______________________________________________
freebsd-hackers@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "freebsd-hackers-unsubscr...@freebsd.org"
