From owner-freebsd-hackers@FreeBSD.ORG Sat Oct 25 12:32:24 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 AC29316A4BF for ; Sat, 25 Oct 2003 12:32:24 -0700 (PDT) Received: from VARK.homeunix.com (adsl-68-123-140-7.dsl.pltn13.pacbell.net [68.123.140.7]) by mx1.FreeBSD.org (Postfix) with ESMTP id E048E43F75 for ; Sat, 25 Oct 2003 12:32:23 -0700 (PDT) (envelope-from das@FreeBSD.ORG) Received: from VARK.homeunix.com (localhost [127.0.0.1]) by VARK.homeunix.com (8.12.9/8.12.9) with ESMTP id h9PJVxen018296; Sat, 25 Oct 2003 12:31:59 -0700 (PDT) (envelope-from das@FreeBSD.ORG) Received: (from das@localhost) by VARK.homeunix.com (8.12.9/8.12.9/Submit) id h9PJVwdj018295; Sat, 25 Oct 2003 12:31:58 -0700 (PDT) (envelope-from das@FreeBSD.ORG) Date: Sat, 25 Oct 2003 12:31:58 -0700 From: David Schultz To: Q Message-ID: <20031025193158.GA18230@VARK.homeunix.com> Mail-Followup-To: Q , freebsd-hackers@FreeBSD.ORG References: <1066789354.21430.39.camel@boxster.onthenet.com.au> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1066789354.21430.39.camel@boxster.onthenet.com.au> cc: freebsd-hackers@FreeBSD.ORG 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: Sat, 25 Oct 2003 19:32:24 -0000 On Wed, Oct 22, 2003, Q wrote: > As an effort to get more acquainted with the FreeBSD kernel, I have been > looking through how mmap works. I don't yet understand how it all fits > together, or of the exact implications things may have in the wild, but > I have noticed under some synthetic conditions, ie. mmaping small > non-contiguous pages of a file, mmap allocation scales much more poorly > on FreeBSD than on OpenBSD and Linux 2.6. > > After investigating this further I have observed that vm_map_findspace() > traverses a linked list to find the next region (O(n) cost), whereas > OpenBSD and Linux 2.6 both use Red-Black trees for the same purpose > (O(log n) cost). Profiling the FreeBSD kernel appears to confirm this. > > Can someone comment on whether this is something that has been done > intentionally, or avoided in favour of some other yet to be implemented > solution? Or is it still on someones todo list. This is not, to my knowledge, on anyone's todo list. Using red-black trees for VM space allocation is likely to be slower for the common case where there aren't very many mappings in the first place, so it's not clear that this ``optimization'' should be a priority. I have never seen any real applications that are mmap-bound as a result of mmapping thousands of tiny regions. However, if some exist, I'm sure there would be interest in patches to improve scalability in this area.