Date: Thu, 30 Sep 2010 21:06:20 +0200 From: Ivan Voras <ivoras@freebsd.org> To: freebsd-hackers@freebsd.org Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <i82n3c$9q5$1@dough.gmane.org> In-Reply-To: <20100930183853.GX49807@elvis.mu.org> References: <4CA4BCD2.4070303@freebsd.org> <20100930183853.GX49807@elvis.mu.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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 :)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?i82n3c$9q5$1>