Date: Sat, 25 Oct 2003 12:31:58 -0700 From: David Schultz <das@FreeBSD.ORG> To: Q <q@onthenet.com.au> Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: Some mmap observations compared to Linux 2.6/OpenBSD Message-ID: <20031025193158.GA18230@VARK.homeunix.com> In-Reply-To: <1066789354.21430.39.camel@boxster.onthenet.com.au> References: <1066789354.21430.39.camel@boxster.onthenet.com.au>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20031025193158.GA18230>