Re: garbage collection thoughts... again?!

["Wim Couwenberg" <w.couwenberg@...>]

I'm not sure if anything like the following was already mentioned in the
long and ongoing GC discussion.  (Or is it covered by some of the
"buzzwords" or does it just make no sense...?  ;-))

It should be possible to halt a M&S algorithm at (almost) any stage if you
divide collectible objects in "even" and "odd" generations.  Each GC cycle
only considers object of a single (current) generation.  Then switch the
parity that will be used for newly created objects at the beginning of each
GC cycle.  Marking must be an atomic operation and it flips the objects'
generation.  Only unmarked objects of the generation under consideration
will be collected in the sweep stage.  Then, after completing a GC cycle,
all remaining objects (both live and unreachable) belong to the same
generation.

Collectible objects are not relocatable (only the key/value data of tables
is) so GC can simply pick up its work where it left it after each break (if
it is implemented as a cooperative task.)  GC activities are under full
control of the Lua vm so it should be possible to apply a sensible
scheduler.  Somewhere in the main byte-code loop, possibly checking an
optional flag/gc_hook (to yield) every now and then?

Also, I'd definitely like to see "weakly referenced cycles" collected as
well (as discussed in some earlier threads about GC.)  So M&S should be
extended by recording an object's dependants in the mark stage.  (An object
A depends on object B if object A is the strongly referenced counterpart of
the weakly referenced object B in a weak table's key/value pair.)  Unlike
mentioned by Rici and Peter Hill (if I remember correctly) I would suggest
not to link the key/value pairs themselves, partly because of the storage
overhead, but mostly because key/value pairs _are_ relocatable.  On the
other hand this means that an extra GC admin (i.e. outside of the common
header) must be used for tracking sets of dependants.  But it's definitely
worth the extra effort in my view.

Anyway, just my 2 (euro) cents...

Bye,
Wim