From owner-cvs-src@FreeBSD.ORG  Fri Aug 13 13:09:39 2004
Return-Path: <owner-cvs-src@FreeBSD.ORG>
Delivered-To: cvs-src@freebsd.org
Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125])
	by hub.freebsd.org (Postfix) with ESMTP
	id D0CD516A4CE; Fri, 13 Aug 2004 13:09:39 +0000 (GMT)
Received: from freefall.freebsd.org (freefall.freebsd.org [216.136.204.21])
	by mx1.FreeBSD.org (Postfix) with ESMTP
	id C50A643D60; Fri, 13 Aug 2004 13:09:39 +0000 (GMT)
	(envelope-from csjp@freebsd.org)
Received: from freefall.freebsd.org (csjp@localhost [127.0.0.1])
	i7DD9dgh095132;	Fri, 13 Aug 2004 13:09:39 GMT
	(envelope-from csjp@freebsd.org)
Received: (from csjp@localhost)
	by freefall.freebsd.org (8.12.11/8.12.11/Submit) id i7DD9dsQ095131;
	Fri, 13 Aug 2004 13:09:39 GMT
	(envelope-from csjp@freebsd.org)
X-Authentication-Warning: freefall.freebsd.org: csjp set sender to
	csjp@freebsd.org using -f
Date: Fri, 13 Aug 2004 13:09:39 +0000
From: "Christian S.J. Peron" <csjp@freebsd.org>
To: Alan Cox <alc@freebsd.org>
Message-ID: <20040813130939.GA94895@freefall.freebsd.org>
References: <200408130806.i7D86YJZ075107@repoman.freebsd.org>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <200408130806.i7D86YJZ075107@repoman.freebsd.org>
User-Agent: Mutt/1.4.1i
cc: cvs-src@freebsd.org
cc: src-committers@freebsd.org
cc: cvs-all@freebsd.org
Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h
X-BeenThere: cvs-src@freebsd.org
X-Mailman-Version: 2.1.1
Precedence: list
List-Id: CVS commit messages for the src tree <cvs-src.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/cvs-src>,
	<mailto:cvs-src-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/cvs-src>
List-Post: <mailto:cvs-src@freebsd.org>
List-Help: <mailto:cvs-src-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/cvs-src>,
	<mailto:cvs-src-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Fri, 13 Aug 2004 13:09:40 -0000

Neat!
On 13 Aug 2004 Alan Cox wrote:
> alc         2004-08-13 08:06:34 UTC
> 
>   FreeBSD src repository
> 
>   Modified files:
>     sys/vm               vm_map.c vm_map.h 
>   Log:
>   Replace the linear search in vm_map_findspace() with an O(log n)
>   algorithm built into the map entry splay tree.  This replaces the
>   first_free hint in struct vm_map with two fields in vm_map_entry:
>   adj_free, the amount of free space following a map entry, and
>   max_free, the maximum amount of free space in the entry's subtree.
>   These fields make it possible to find a first-fit free region of a
>   given size in one pass down the tree, so O(log n) amortized using
>   splay trees.
>   
>   This significantly reduces the overhead in vm_map_findspace() for
>   applications that mmap() many hundreds or thousands of regions, and
>   has a negligible slowdown (0.1%) on buildworld.  See, for example, the
>   discussion of a micro-benchmark titled "Some mmap observations
>   compared to Linux 2.6/OpenBSD" on -hackers in late October 2003.
>   
>   OpenBSD adopted this approach in March 2002, and NetBSD added it in
>   November 2003, both with Red-Black trees.
>   
>   Submitted by: Mark W. Krentel
>   
>   Revision  Changes    Path
>   1.357     +212 -98   src/sys/vm/vm_map.c
>   1.116     +2 -1      src/sys/vm/vm_map.h

-- 
Christian S.J. Peron
csjp@FreeBSD.ORG
FreeBSD Committer