:...
:> 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
<[EMAIL PROTECTED]>
_______________________________________________
[EMAIL PROTECTED] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "[EMAIL PROTECTED]"
