Date: 26 Oct 2003 07:43:33 -0500 From: Lowell Gilbert <lowell@world.std.com> To: <freebsd-hackers@FreeBSD.ORG> Subject: Re: Some mmap observations compared to Linux 2.6/OpenBSD Message-ID: <44he1wi2yy.fsf@be-well.ilk.org> In-Reply-To: <20031026052854.GA20701@VARK.homeunix.com> References: <1066789354.21430.39.camel@boxster.onthenet.com.au> <20031022082953.GA69506@rot13.obsecurity.org> <1066816287.25609.34.camel@boxster.onthenet.com.au> <20031022095754.GA70026@rot13.obsecurity.org> <1066820436.25609.93.camel@boxster.onthenet.com.au> <xzpk76sc425.fsf@dwp.des.no> <20031026052854.GA20701@VARK.homeunix.com>
next in thread | previous in thread | raw e-mail | index | archive | help
David Schultz <das@FreeBSD.ORG> writes: > On Sun, Oct 26, 2003, Dag-Erling Smrgrav wrote: > > Q <q_dolan@yahoo.com.au> writes: > > > Yes, it would appear this is a legacy thing that existed in the original > > > 1994 import of the BSD 4.4 Lite source. Both FreeBSD and NetBSD still > > > use this technique, but OpenBSD changed to using Red-Black trees back in > > > Feb 2002. > > > [...] > > > I am wondering if there is a compelling reason why the technique used by > > > OpenBSD could not be adapted to FreeBSD's VM system. > > > > Adapting OpenBSD's red-balck patches would require quite a bit of work > > as FreeBSD and OpenBSD have diverged quite a bit in this area. Though > > it is a good idea to change the list into a tree, I think you'd get > > more mileage by addressing the fundamental problem, which is the lack > > of a free list. The current code (in both FreeBSD and OpenBSD) > > searches a list or tree of allocated extents, sorted by location, > > looking for a pair that have sufficient space between them for the > > extent you want to create. We should instead keep track of free > > extents in a structure that makes it easy to locate one of the correct > > size. We probably need a dual structure, though, because we need to > > keep the free extents sorted both by size (to quickly find what we > > need) and by location (to facilitate aggregation of adjacent extents, > > without which we'd suffer horribly from address space fragmentation). > > > > I have no idea how much this means for real-life workloads though. > > Your idea of using a size-hashed freelist as well as a > location-sorted list is appealing in its simplicity. Though it > can cause a bit of fragmentation, it gives you constant time > lookup. Bonwick's vmem allocator ([1], section 4.4.2 and > following), apparently works quite well using this principle. A hash probably isn't the right data structure for either dimension (DES didn't say it was, I notice). Finding the next-largest available entry is a useful operation, here, so a list would be better than a hash. [Or a tree; the point is that exact-match isn't the only kind of search you need.] > But regardless of the approach, someone has yet to demonstrate > that this is actually a performance problem in the real world. ;-) Yes. Wouldn't be easy to test even if you wanted to, either...
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?44he1wi2yy.fsf>