From owner-freebsd-hackers@FreeBSD.ORG Mon Oct 27 10:12:42 2003 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id A8D9416A4B3; Mon, 27 Oct 2003 10:12:42 -0800 (PST) Received: from apollo.backplane.com (apollo.backplane.com [216.240.41.2]) by mx1.FreeBSD.org (Postfix) with ESMTP id D444043FE0; Mon, 27 Oct 2003 10:12:41 -0800 (PST) (envelope-from dillon@apollo.backplane.com) Received: from apollo.backplane.com (localhost [127.0.0.1]) h9RICfiF044117; Mon, 27 Oct 2003 10:12:41 -0800 (PST) (envelope-from dillon@apollo.backplane.com) Received: (from dillon@localhost) by apollo.backplane.com (8.12.9p2/8.12.9/Submit) id h9RICfN0044116; Mon, 27 Oct 2003 10:12:41 -0800 (PST) (envelope-from dillon) Date: Mon, 27 Oct 2003 10:12:41 -0800 (PST) From: Matthew Dillon Message-Id: <200310271812.h9RICfN0044116@apollo.backplane.com> To: David Schultz References: <1066789354.21430.39.camel@boxster.onthenet.com.au> <20031022082953.GA69506@rot13.obsecurity.org> <1066816287.25609.34.camel@boxster.onthenet.com.au> <20031022095754.GA70026@rot13.obsecurity.org> <1066820436.25609.93.camel@boxster.onthenet.com.au> <20031026052854.GA20701@VARK.homeunix.com> <20031027170859.GA30164@VARK.homeunix.com> cc: freebsd-hackers@freebsd.org cc: Lowell Gilbert Subject: Re: Some mmap observations compared to Linux 2.6/OpenBSD X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 27 Oct 2003 18:12:42 -0000 :... :> A hash probably isn't the right data structure for either dimension :> (DES didn't say it was, I notice). Finding the next-largest available :> entry is a useful operation, here, so a list would be better than a :> hash. [Or a tree; the point is that exact-match isn't the only kind :> of search you need.] : :Erm, did you read the paper I referred to? If you have, say, 32 :power-of-two buckets, you can use a bitmask representing which :buckets are non-empty to locate spcae in constant time. The :caveat (also in the paper) is that the price of the constant time :operation is that your allocation may be up to twice as large as :necessary. A tree lacks this disadvantage, but also carries with :it some additional overhead. The swap bitmap code I wrote uses a radix tree with size hinting for allocations, and while I haven't formally tested its scaleability I've never heard any complaints so I think I implemented it properly. While the swap radix tree could not be used directly (since it represents a preallocated fixed address space and a vm_map's VM space is too big, especially on a 64 bit system), the size hinting concept could certainly be used on top of a dynamic radix tree and might possibly be useable on the splay trees being used in current now. I say 'might' because splay trees manipulate nodes so much it might not be possible to maintain consistency in the hint information. In anycase, I suggest those interested in mmap performance play around with adding size hinting to the existing splay tree code for vm_map_entry. It could turn out to be the easy way out. -Matt Matthew Dillon