Date: Fri, 13 Aug 2004 13:09:39 +0000 From: "Christian S.J. Peron" <csjp@freebsd.org> To: Alan Cox <alc@freebsd.org> Cc: cvs-all@freebsd.org Subject: Re: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <20040813130939.GA94895@freefall.freebsd.org> In-Reply-To: <200408130806.i7D86YJZ075107@repoman.freebsd.org> References: <200408130806.i7D86YJZ075107@repoman.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Neat! On 13 Aug 2004 Alan Cox wrote: > 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 -- Christian S.J. Peron csjp@FreeBSD.ORG FreeBSD Committer
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040813130939.GA94895>