cvs commit: src/sys/vm vm_map.c vm_map.h

[Christian S.J. Peron]

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 at FreeBSD.ORG
FreeBSD Committer