[gclist] Fragmentation issues

[boehm.PARC@xerox.com]

"How does Cedar deal with this ? (does it compact memory from time to time
using
something akin to the mostly-copying GC or does fragmentation problems never
show up early enough to be noticed ?)"

As far as I can tell, fragmentation problems never get noticed.  When I have
seen them, they have been fairly minor, i.e. much less than a factor of 2
fragmentation overhead, and have been caused by the large block or page level
allocator.  In light of Paul Wilson's recent results, I conjecture that our
page level allocator could stand some improvement.  It's basically a next fit
allocator plus a tweak or two to avoid the silliest placement decisions
normally made by such an allocator.  It normally doesn't break up the largest
chunk to allocate a single page when there are smaller chunks available.  But I
don't think this is really enough.  It should be much closer to best fit.
(This is clearly fixable.  It is however a high risk fix because it interacts
with the black listing code in nontrivial ways.  That's why I haven't done it
yet.)

The fact that whole pages tend to be wasted and not touched does mean that you
waste mainly swap spaces wihtouyt losing paging performance.  We could also be
playing mmap games to get the pages back.

One problem with the Cedar anecdotes is that typical Cedar worlds are
relatively stingy about allocation.  I'm typing this from a Cedar world that
was started Jan 29, and has allocated 310 MB.  The heap size is 47 MB, out of
which a bit more than half appear to be currently live.  I have no idea what
the high water mark was.  I can allocate several 500KB chunks without growing
the heap, but a 1MB request did grow the heap.

Our allocator does have some fragmentation problems that don't appear in Cedar.
Most notably in its standard configuration, it does poorly for heaps with very
small amounts of live data, since a page is dedicated to a fixed object size.
It tends to need a heap of at least several hundred KB no matter what the
application.

Hans