[gclist] Fast-allocating non-copying GC's

[boehm.PARC@xerox.com]

Geert Bosch wrote:

"   - Portability is not an issue: the allocator should
     work for a 32-bit computer with VM pages of 4 kB
     running the GNAT Ada compiler"

I strongly recommend against assuming a fixed page size.  A lot of
architectures have variants with different page sizes.  For example, Sun's
machines generally have either 4K or 8K VM pages, but they've switched back and
forth between those two numbers.  I believe Sun 4/110s had 8K pages.
UltraSPARCs again have 8K pages.  It's not very hard to handle that correctly.
(I would also argue that environments with 64-bit pointers are important.
Microsoft seems to disagree.)

"    4. Now we've 222208 bytes of living objects left,  taking up 35 MB of RAM"
Granted, you can end up in that situation.  On the other hand, you did have
something between 7 and 8 MB live at one point, so this is a somewhat
pessimistic way of looking at things.

There are a bunch of other important issues in the design of such a collector,
such as:

- You probably eventually want to use some black listing and stack cleaning
mechanism to avoid scanning bogus and dead pointers.

- The allocation strategy for the main storage pool matters.  You want
something that behaves a lot like best fit.

- How do you handle running out of memory?  This typically effects the way you
design the marker in fairly profound ways.

- Which incremental GC algorithm do you use?  How may page faults do you have
to handle?  Are they likely to occur in rapid succession?  Some operating
systems don't let you recover gracefully from page faults in system calls.  Can
you deal with that (or punt) gracefully?

- Do you detect and recycle completely empty pools?

- Does the collector run concurrently with the mutator in its own thread, or
does it run incrementally in the mutator thread?  In my experience, the latter
is more robust, but less pleasant to program.

Hans
Standard disclaimer ...