Date: Thu, 30 Sep 2010 23:10:41 +0200 From: Andre Oppermann <andre@freebsd.org> To: Alfred Perlstein <alfred@freebsd.org> Cc: freebsd-hackers <freebsd-hackers@freebsd.org>, freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness Message-ID: <4CA4FCD1.6010709@freebsd.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 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4CA4FCD1.6010709>