Date: Mon, 27 Oct 2003 10:12:41 -0800 (PST) From: Matthew Dillon <dillon@apollo.backplane.com> To: David Schultz <das@freebsd.org> Cc: Lowell Gilbert <lowell@world.std.com> Subject: Re: Some mmap observations compared to Linux 2.6/OpenBSD Message-ID: <200310271812.h9RICfN0044116@apollo.backplane.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> <20031026052854.GA20701@VARK.homeunix.com> <20031027170859.GA30164@VARK.homeunix.com>
next in thread | previous in thread | raw e-mail | index | archive | help
:...
:> 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.]
:
:Erm, did you read the paper I referred to? If you have, say, 32
:power-of-two buckets, you can use a bitmask representing which
:buckets are non-empty to locate spcae in constant time. The
:caveat (also in the paper) is that the price of the constant time
:operation is that your allocation may be up to twice as large as
:necessary. A tree lacks this disadvantage, but also carries with
:it some additional overhead.
The swap bitmap code I wrote uses a radix tree with size hinting for
allocations, and while I haven't formally tested its scaleability I've
never heard any complaints so I think I implemented it properly.
While the swap radix tree could not be used directly (since it represents
a preallocated fixed address space and a vm_map's VM space is too big,
especially on a 64 bit system), the size hinting concept could
certainly be used on top of a dynamic radix tree and might possibly
be useable on the splay trees being used in current now. I say 'might'
because splay trees manipulate nodes so much it might not be possible
to maintain consistency in the hint information.
In anycase, I suggest those interested in mmap performance play around
with adding size hinting to the existing splay tree code for vm_map_entry.
It could turn out to be the easy way out.
-Matt
Matthew Dillon
<dillon@backplane.com>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200310271812.h9RICfN0044116>