From owner-freebsd-current@FreeBSD.ORG Thu Sep 30 22:50:07 2010 Return-Path: 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 002D71065675 for ; Thu, 30 Sep 2010 22:50:06 +0000 (UTC) (envelope-from fjwcash@gmail.com) Received: from mail-fx0-f54.google.com (mail-fx0-f54.google.com [209.85.161.54]) by mx1.freebsd.org (Postfix) with ESMTP id 872DB8FC1D for ; Thu, 30 Sep 2010 22:50:06 +0000 (UTC) Received: by fxm9 with SMTP id 9so2230533fxm.13 for ; Thu, 30 Sep 2010 15:50:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:content-type; bh=K3dfLwqdLa65PPQNghcdjtSproznHzGsNxfY/D4NpLg=; b=RTfMiZaYmu2u2X2r6ardIHGjD35ehTjqijGcByLQwDEhvn4xzM5f9uDUAmmpiNeVpV 8vSM9FMsq4CA6PFG3TYQYGxYLm4KHXZVg+owX45hzmHgqhLPBXiW4LZT/L2VHqkNtY8d VPNblmHUipJ5uLyqPqIOe8rfyHXcSHx0lKW/k= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; b=dK1n7dHGAV7j5iHactXBlAwAWAlLaSBElT8UzCIl7kZwbjswzU/nQTq9a68LNKh/qq M+7JbC55BsKtTWkCryzjiOIrP40PwZ8tuG+Y+qRa9pX6VyUwCofYUg8w5tmtlXmxlbEP 28JIdcw4rToGBjkT4ciHCF8ckNr/F3/IZcCEI= MIME-Version: 1.0 Received: by 10.223.115.19 with SMTP id g19mr4638044faq.70.1285887004937; Thu, 30 Sep 2010 15:50:04 -0700 (PDT) Received: by 10.223.110.197 with HTTP; Thu, 30 Sep 2010 15:50:04 -0700 (PDT) In-Reply-To: <4CA509FE.30303@freebsd.org> References: <4CA4BCD2.4070303@freebsd.org> <20100930172439.GA34369@freebsd.org> <4CA4CCF8.1050300@freebsd.org> <20100930174900.GA37733@freebsd.org> <20100930180417.GA39381@freebsd.org> <4CA504AD.8000102@freebsd.org> <4CA509FE.30303@freebsd.org> Date: Thu, 30 Sep 2010 15:50:04 -0700 Message-ID: From: Freddie Cash To: freebsd-current@freebsd.org Content-Type: text/plain; charset=UTF-8 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 30 Sep 2010 22:50:07 -0000 For the curious, DragonflyBSD went through this back in 2005. All the gory details are in the thread with Subject: "splay tree and red-black tree for vm_map entry lookups" [1] While things are most likely different now between the FreeBSD VM and the DragonflyBSD VM, it may be worthwhile checking out what they did, and why. They considered the FreeBSD splay-tree and compared it to red-black tree, and went with red-black. There's mention in that thread that NetBSD uses red-black trees. No idea if this is still correct. [1] http://leaf.dragonflybsd.org/mailarchive/kernel/2005-01/msg00121.html -- Freddie Cash fjwcash@gmail.com