Some mmap observations compared to Linux 2.6/OpenBSD

[Matthew Dillon]

:...
:> 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 at backplane.com>