From owner-freebsd-current@FreeBSD.ORG Thu Sep 30 18:26:22 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 841DB1065672 for ; Thu, 30 Sep 2010 18:26:22 +0000 (UTC) (envelope-from alan.l.cox@gmail.com) Received: from mail-px0-f182.google.com (mail-px0-f182.google.com [209.85.212.182]) by mx1.freebsd.org (Postfix) with ESMTP id 56A728FC16 for ; Thu, 30 Sep 2010 18:26:21 +0000 (UTC) Received: by pxi17 with SMTP id 17so719862pxi.13 for ; Thu, 30 Sep 2010 11:26:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:reply-to :in-reply-to:references:date:message-id:subject:from:to:cc :content-type; bh=HTVWFQJCaDYink14UwYwO6xIP1kkrXGRUiGtf0IW+38=; b=CgQR2qnAc96UOZyvIxxeCC22+9f0GjursgxBQ/+AUSdbq4PQE3Gu+812LMA5mJ26ZI zatqciQ3sCW5yFTJklExlfpxJE0qtX7HDsOCt3whsDejUzEB/p4xhHhyX199vhGF/TYb e5Qv+19iZqzHe6F39eS25/Dl9jRIDefSm9xTk= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:reply-to:in-reply-to:references:date:message-id :subject:from:to:cc:content-type; b=V/thMLbt2DqFfUQ1853xpb3i8q45kSDAxQPA3xEwnx9oEAcEr0hPzqiTynDyBR0mww fwNtjnJglV7s3oCMchPolQAgbn0eIK6ijE9MkmVPbFqTluP92xlgdy3UU3V4hlWoFAhc VsOaXykt0CALR1OXdXCREKqqK+V2ogOiSQWu0= MIME-Version: 1.0 Received: by 10.114.95.12 with SMTP id s12mr4700695wab.217.1285869710947; Thu, 30 Sep 2010 11:01:50 -0700 (PDT) Received: by 10.42.170.136 with HTTP; Thu, 30 Sep 2010 11:01:50 -0700 (PDT) In-Reply-To: <4CA4CAE6.2090108@freebsd.org> References: <4CA4BCD2.4070303@freebsd.org> <4CA4CAE6.2090108@freebsd.org> Date: Thu, 30 Sep 2010 13:01:50 -0500 Message-ID: From: Alan Cox To: Andre Oppermann Content-Type: text/plain; charset=ISO-8859-1 X-Content-Filtered-By: Mailman/MimeDel 2.1.5 Cc: freebsd-hackers , 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 Reply-To: alc@freebsd.org 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 18:26:22 -0000 On Thu, Sep 30, 2010 at 12:37 PM, Andre Oppermann wrote: > On 30.09.2010 18:37, Andre Oppermann wrote: > >> Just for the kick of it I decided to take a closer look at the use of >> splay trees (inherited from Mach if I read the history correctly) in >> the FreeBSD VM system suspecting an interesting journey. >> > > Correcting myself regarding the history: The splay tree for vmmap was > done about 8 years ago by alc@ to replace a simple linked list and was > a huge improvement. The change in vmpage from a hash to the same splay > tree as in vmmap was committed by dillon@ about 7.5 years ago with some > involvement of alc@. > ss > Yes, and there is a substantial difference in the degree of locality of access to these different structures, and thus the effectiveness of a splay tree. When I did the last round of changes to the locking on the vm map, I made some measurements of the splay tree's performance on a JVM running a moderately large bioinformatics application. The upshot was that the average number of map entries visited on an access to the vm map's splay tree was less than the expected depth of a node in a perfectly balanced tree. I teach class shortly. I'll provide more details later. Regards, Alan