Memory used during GC

Calum Grant writes:
> [list of objects pending marking]
> the reserved memory is of no use at any other time.

Well, in Baker's treadmill, the (doubly-linked) list is used all the
time -- but you're not doing that algorithm.

> So wouldn't it be better to reserve this memory when I need it, and
> return it to the system when finished GC. [...] The down-side is
> that the system might deny a memory request and then it all goes
> horribly wrong...

Exactly.  This is rarely acceptable.

> Does anybody else have experiences of this sort of thing, or are there
> approaches I have not thought of?

There's bit tables: maintain an external bit table with a bit for
every allocation grain.  (If the grains are a typical 8 bytes, the
overhead is small compared to the GC overhead in general, but you
still want to allocate the tables in suitable sections, say per page,
instead of trying set up one for the whole address space.)  You only
need to change the bit for the first grain of the object.

The stack-and-rescan strategy described by David Detlefs is faster,
except when it has to rescan.
-- 
Pekka P. Pirinen