Speeding up GC

[loewis at informatik dot hu-berlin dot de (Martin v. Löwis)]

While profiling cc1plus, I notice that a large amount of time is spent
in marking objects during GC. I suspect that, for each collection, the
same objects are marked over and over again.

It appears that speed-ups are possible by not traversing parts of the
graph that are known not to have changed since the previous
collection.

While it is, in general, not possible to determine whether an object
has changed, I believe that for certain objects (in particular DECL
nodes), there is a point in time when they are "frozen", meaning that
they won't change anymore. I suggest to record this fact in the
object (with the opportunity to unfreeze the object).

During GC traversal, GC should detect "immutable" objects. An object
can be marked immutable if it is frozen, and all contained objects are
immutable. Then, when marking objects, GC should not traverse into
immutable objects.

An exception probably needs to be made for identifiers: they are
always mutable, since the associated decls might change. However, it
is not necessary to traverse into identifiers from other tree nodes,
since all identifiers are GC roots, anyway.

In my specific application, 20% of the memory is consumed by
PARM_DECLs. I believe that those would be candidates for being marked
as immutable, and that the containers immediately storing them could
be marked as immutable as well (after the list of parameters for a
declaration has been built). All those PARM_DECLs indeed live up to
the end of the compilation; they are never collected, and never
changed. Thus, GC traversal could completely ignore them.

Does this approach have a chance of speeding up GC? What do you think?

Regards,
Martin