Date: Fri, 13 Aug 2004 08:06:34 +0000 (UTC) From: Alan Cox <alc@FreeBSD.org> To: src-committers@FreeBSD.org, cvs-src@FreeBSD.org, cvs-all@FreeBSD.org Subject: cvs commit: src/sys/vm vm_map.c vm_map.h Message-ID: <200408130806.i7D86YJZ075107@repoman.freebsd.org>
next in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200408130806.i7D86YJZ075107>