600564 - Partly-moving collection

Status: RESOLVED WONTFIX

(Tamarin Graveyard :: Garbage Collection (mmGC), defect)

Description

[Lars T Hansen]

This bug is about discussing approaches to copying objects so as to improve locality, reduce fragmentation, and make pointer-bumping allocators more effective.

Here are some notes:

In the current work on partly exact tracing there is a per-object bit (or set of bits) that determines whether the object is traced exactly or not.  This is not quite enough to build on if we want to compact or move objects efficiently: in that case we want to determine if an object was reached only through exactly traced pointers; if it was, then we can move it and update all pointers to it.  If exactly traced and conservatively traced pointers are interleaved during garbage collection however, we won't know until the collection is over whether an object can be moved (that's when we know whether it was reached through any conservative pointer); performing any moving at that point means that we have to update all pointers to the object, which means we have to re-scan the heap.

Suppose that additionally, objects that contain only exactly tracable pointers (which is not quite the same as objects that are exactly traced, but almost) are segregated at allocation time from the other objects.  If we assume a nonincremental collection for a moment, then suppose the "other" objects are traced first.  Any pointer from the "other" object set into the "exact" object set effectively pins the exact object and prevents its movement (this is as above) but because the "other" objects are all traced first, when we scan the exact objects we can move any unpinned object the first time we reach it - we know it won't be pinned, because we've already looked at all the objects that contain conservative pointers.

However, it's not obvious to me (yet) how to adapt that to incremental collection.

In general, on-line object movement during incremental collection will require read barriers anyway, and maybe that dooms it and restricts us to after-the-fact compaction.

A complementary idea is examined in bug #577118 where a bit says "this object can only be reached through precise pointers"; if that could be implemented safely it would immediately aid copying because all such objects could be copied.

Comment 1

[Sylvestre Ledru [:Sylvestre]]

Tamarin is a dead project now. Mass WONTFIX.

Comment 2

[Sylvestre Ledru [:Sylvestre]]

Tamarin isn't maintained anymore. WONTFIX remaining bugs.