OTOH both freezing and creating the graph of live objects during DOD are basically the same. The problem currently is that chaining objects together is done independently and on demand, with the complication that incremental's chain creation is done in the "background".
Well, here is an idea:
Prelims:
a) The mark phase of the garbage collection creates the graph of *all* life (reachable) objects[1].
b) Freezing a PMC creates the graph of reachables from that PMC on (e.g. all array items, and subitems if an item is another array...)
c) The graph of objects created during b) is a subgraph of a), *if* both schemes either use depth-first or breadth-first.
Thus the basic idea now is: we just keep that graph (that hangs off the next_for_GC pointer). Freezing then just means: walk that graph and spit out tokens (object ids and other stuff like values) and be done with it.
A serializable continuation is the same as freezing the interpreter[2] i.e. take the full object chain created in a) and freeze it. Easy.
The problem is of course the mutator: that is the user program that permanently changes the graph of objects.
A small side-step: generational GC.
- A refcount GC system is doing work proportional O(w+d), w being the normal mutator work and d are dead objects.
- A marking scheme has O(live) or O(live+dead). With sweep the latter is true.
To reduce GC overhead, we have to skip some objects. E.g. at program start you create some big arrays (or hashes) and these objects are more or less unchanged. Mark has to go through these objects item per item on every single DOD run. That's really time consuming.
The idea of generational GC is now: put such objects into an old generation and just skip this generation. So the overall work can decrease by a huge amount. This is based on the "weak generational hypothesis", which asserts that most objects die early.
When we keep the chain of objects for freezing, we can as well set a bit in the aggregate header ("old_generation") and skip the whole chain of objects that belongs to that aggregate during marking.
Back to the mutator:
Incremental GC needs write barriers[3]. Whenever a white object is stored into a black[4] one, the write barrier notifies the garbage collector to update its object graph. The collector can either rescan the aggregate or mark the new (white) object.
Generational GC needs a write barrier too, to track inter-generational store operations. That's basically the same as above, when we just have two generations as most of these schemes have.
I think it should be doable to keep the graph of objects accurate most of the time. Instead of rebuilding the graph in each DOD cycle, we should be able to reuse the graph of the old generation and rebuild parts of the graph only after changes triggered by the write barrier.
Comments welcome, leo
[1] buffer headers may be different or not
[2] modulo some bits of meta tokens ("I'm a stack frame ...")
[3] I don't consider read barriers, doable but too expensive.
[4] WRT object colors: perldoc -F src/gc_ims.c and:
[5] Real-Time Non-Copying Garbage Collection, Paul R. Wilson and Mark S. Johnstone
