From owner-cvs-src@FreeBSD.ORG  Fri Aug 13 08:06:35 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 1D8B216A4CE; Fri, 13 Aug 2004 08:06:35 +0000 (GMT)
Received: from repoman.freebsd.org (repoman.freebsd.org [216.136.204.115])
	by mx1.FreeBSD.org (Postfix) with ESMTP
	id 1240043D41; Fri, 13 Aug 2004 08:06:35 +0000 (GMT)
	(envelope-from alc@FreeBSD.org)
Received: from repoman.freebsd.org (localhost [127.0.0.1])
	by repoman.freebsd.org (8.12.11/8.12.11) with ESMTP id i7D86YbZ075108;
	Fri, 13 Aug 2004 08:06:34 GMT
	(envelope-from alc@repoman.freebsd.org)
Received: (from alc@localhost)
	by repoman.freebsd.org (8.12.11/8.12.11/Submit) id i7D86YJZ075107;
	Fri, 13 Aug 2004 08:06:34 GMT
	(envelope-from alc)
Message-Id: <200408130806.i7D86YJZ075107@repoman.freebsd.org>
From: Alan Cox <alc@FreeBSD.org>
Date: Fri, 13 Aug 2004 08:06:34 +0000 (UTC)
To: src-committers@FreeBSD.org, cvs-src@FreeBSD.org,
	cvs-all@FreeBSD.org
X-FreeBSD-CVS-Branch: HEAD
Subject: 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 08:06:35 -0000

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