Examining the VM splay tree effectiveness

[Ivan Voras]

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

I see two possible problems with this:

1: the validity of this heuristics, since the splay is not meant to help
the current lookup but future lookups, and if you "now" require e.g.
5-deep traversal, (barring external information about the structures -
meybe some inner relationship of the nodes can be exploitet) it is I
think about the same probability that the next lookup will hit that
rotated node or the former root node.

2: rotating only on the N'th lookup would have to go like this:

   1. take a read-only lock
   2. make the lookup, count the depth
   3. if depth > N:
          1. relock for write (lock upgrade will not always work)
          2. recheck if the tree is still the same; bail if it isn't
          3. do the splay
   4. unlock

i.e. suspiciously complicated. That is, if you want to take advantage of
read paralelism; if the tree is write-locked all the time it's simpler
but only inefficient.

Of course, real-world measurements trump theory :)