From owner-freebsd-current@FreeBSD.ORG  Fri Oct  1 18:28:58 2010
Return-Path: <owner-freebsd-current@FreeBSD.ORG>
Delivered-To: freebsd-current@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 137A8106566C;
	Fri,  1 Oct 2010 18:28:58 +0000 (UTC) (envelope-from ed@hoeg.nl)
Received: from mx0.hoeg.nl (unknown [IPv6:2a01:4f8:101:5343::aa])
	by mx1.freebsd.org (Postfix) with ESMTP id 97E668FC0A;
	Fri,  1 Oct 2010 18:28:57 +0000 (UTC)
Received: by mx0.hoeg.nl (Postfix, from userid 1000)
	id 553072A28D80; Fri,  1 Oct 2010 20:28:56 +0200 (CEST)
Date: Fri, 1 Oct 2010 20:28:56 +0200
From: Ed Schouten <ed@80386.nl>
To: Andre Oppermann <andre@freebsd.org>
Message-ID: <20101001182856.GF87427@hoeg.nl>
References: <4CA4BCD2.4070303@freebsd.org>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="bNOIqPvWVsuhXMpy"
Content-Disposition: inline
In-Reply-To: <4CA4BCD2.4070303@freebsd.org>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: freebsd-hackers <freebsd-hackers@freebsd.org>, freebsd-current@freebsd.org
Subject: Re: Examining the VM splay tree effectiveness
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Discussions about the use of FreeBSD-current
	<freebsd-current.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>, 
	<mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-current>,
	<mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 01 Oct 2010 18:28:58 -0000


--bNOIqPvWVsuhXMpy
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

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.

Greetings,
--=20
 Ed Schouten <ed@80386.nl>
 WWW: http://80386.nl/

--bNOIqPvWVsuhXMpy
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.16 (FreeBSD)

iEYEARECAAYFAkymKGgACgkQ52SDGA2eCwVl5wCdHzG4YpvaU5cPp4uU0BB5fUM8
rd4An2KVKMItdIuTQVBkEopnKVc8/X+B
=WSCh
-----END PGP SIGNATURE-----

--bNOIqPvWVsuhXMpy--