Re: 'Change the vm_map lookup algorithm'

[Venkatesh Srinivas <me@xxxxxxxxxxxxxxxxxxx>]

Hi,

This is a data point of some kind. I ran zsh on FreeBSD 6.3-PRERELEASE, 
collected the VM map. This particular instance of FreeBSD was running our 
nmalloc, so the malloc slab structures would look like our's, rather than 
phkmalloc's. The VM map had 29 entries; many were densely packed dynamic 
libraries.

I ran 45 lookups in the VM map against the rb tree; the lookups were 
mostly in rw sections of libc, the zsh code, and the malloc slabs. I 
captured the number of rb tree levels hit -- the average depth was 3.8 
levels, with a range from 1 to 6 levels hit. Unfortunately, libc's text 
and data sections were 6-levels deep...

I ran 16 lookups that'd miss as well -- the mean depth for missed lookups 
was 5.4 levels, with a range of 3 to 7 levels hit.

-- vs