From owner-freebsd-hackers@FreeBSD.ORG Sun Oct 3 19:42:45 2010 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 4BE41106566B for ; Sun, 3 Oct 2010 19:42:45 +0000 (UTC) (envelope-from freebsd-hackers@m.gmane.org) Received: from lo.gmane.org (lo.gmane.org [80.91.229.12]) by mx1.freebsd.org (Postfix) with ESMTP id 0443F8FC16 for ; Sun, 3 Oct 2010 19:42:44 +0000 (UTC) Received: from list by lo.gmane.org with local (Exim 4.69) (envelope-from ) id 1P2USF-0008K5-Ra for freebsd-hackers@freebsd.org; Sun, 03 Oct 2010 21:42:39 +0200 Received: from 93-141-115-47.adsl.net.t-com.hr ([93.141.115.47]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 03 Oct 2010 21:42:39 +0200 Received: from ivoras by 93-141-115-47.adsl.net.t-com.hr with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Sun, 03 Oct 2010 21:42:39 +0200 X-Injected-Via-Gmane: http://gmane.org/ To: freebsd-hackers@freebsd.org From: Ivan Voras Date: Sun, 03 Oct 2010 21:42:29 +0200 Lines: 27 Message-ID: References: <4CA4BCD2.4070303@freebsd.org> <20101001182856.GF87427@hoeg.nl> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Complaints-To: usenet@dough.gmane.org X-Gmane-NNTP-Posting-Host: 93-141-115-47.adsl.net.t-com.hr User-Agent: Mozilla/5.0 (X11; U; FreeBSD amd64; en-US; rv:1.9.1.9) Gecko/20100620 Thunderbird/3.0.4 In-Reply-To: <20101001182856.GF87427@hoeg.nl> Cc: freebsd-current@freebsd.org Subject: Re: Examining the VM splay tree effectiveness X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 03 Oct 2010 19:42:45 -0000 On 10/01/10 20:28, Ed Schouten wrote: > Andre, > > * Andre Oppermann 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