From owner-cvs-all@FreeBSD.ORG Sun Aug 15 04:51:40 2004 Return-Path: Delivered-To: cvs-all@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 4AC8216A4CE; Sun, 15 Aug 2004 04:51:40 +0000 (GMT) Received: from smtp.des.no (flood.des.no [217.116.83.31]) by mx1.FreeBSD.org (Postfix) with ESMTP id AD7C543D58; Sun, 15 Aug 2004 04:51:39 +0000 (GMT) (envelope-from des@des.no) Received: by smtp.des.no (Pony Express, from userid 666) id 4F1C1530C; Sun, 15 Aug 2004 06:51:38 +0200 (CEST) Received: from dwp.des.no (des.no [80.203.228.37]) by smtp.des.no (Pony Express) with ESMTP id 6CAE95308; Sun, 15 Aug 2004 06:51:31 +0200 (CEST) Received: by dwp.des.no (Postfix, from userid 2602) id 19DE7B872; Sun, 15 Aug 2004 06:51:31 +0200 (CEST) To: Alan Cox References: <200408130806.i7D86YJZ075107@repoman.freebsd.org> From: des@des.no (=?iso-8859-1?q?Dag-Erling_Sm=F8rgrav?=) Date: Sun, 15 Aug 2004 06:51:31 +0200 In-Reply-To: <200408130806.i7D86YJZ075107@repoman.freebsd.org> (Alan Cox's message of "Fri, 13 Aug 2004 08:06:34 +0000 (UTC)") Message-ID: User-Agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3 (berkeley-unix) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on flood.des.no X-Spam-Level: X-Spam-Status: No, hits=0.0 required=5.0 tests=AWL autolearn=no version=2.63 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-all@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: CVS commit messages for the entire tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 15 Aug 2004 04:51:40 -0000 Alan Cox writes: > 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. Great! I've been meaning to do this for a while, but the complexity was a bit beyond me. This should greatly increase pipe performance, by the way, because pipe buffers are allocated from a single vm_map, which accumulates many more entries and much more fragmentation than (probably) most other maps in the kernel. DES --=20 Dag-Erling Sm=F8rgrav - des@des.no