Date: Sun, 03 Oct 2010 21:42:29 +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: <i8amb6$dl1$1@dough.gmane.org> In-Reply-To: <20101001182856.GF87427@hoeg.nl> References: <4CA4BCD2.4070303@freebsd.org> <20101001182856.GF87427@hoeg.nl>
next in thread | previous in thread | raw e-mail | index | archive | help
On 10/01/10 20:28, Ed Schouten wrote: > Andre, > > * Andre Oppermann <andre@freebsd.org> wrote: >> A splay tree is an interesting binary search tree with insertion, >> lookup and removal performed in O(log n) *amortized* time. With >> the *amortized* time being the crucial difference to other binary trees. >> On every access *including* lookup it rotates the tree to make the >> just found element the new root node. For all gory details see: >> http://en.wikipedia.org/wiki/Splay_tree > > Even though a red-black tree is quite good since it guarantees a $2 \log > n$ upperbound, the problem is that it's quite computationally intensive. > > Maybe it would be worth looking at other types of balanced trees? For > example, another type of tree which has only $O(\log n)$ amortized > insertion/removal/lookup time, but could already be a lot better in > practice, is a Treap. How many elements are held in vm_map trees? From the source it looks like one tree with all pages in the system and then one per-process? Trees have very varied real-time characteristics, e.g.: http://attractivechaos.awardspace.com/udb.html http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.6795&rep=rep1&type=pdf
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?i8amb6$dl1$1>