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 :)
_______________________________________________
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"
