CODEWITHSUNDEEP
algorithmgarbage-collection
Yttrill
Yttrill

Reputation: 4921

Gc using type information

Does anyone know of a GC algorithm which utilises type information to allow incremental collection, optimised collection, parallel collection, or some other nice feature?

By type information, I mean real semantics. Let me give an example: suppose we have an OO style class with methods to maintain a list which hide the representation. When the object becomes unreachable, the collector can just run down the list deleting all the nodes. It knows they're all unreachable now, because of encapsulation. It also knows there's no need to do a general scan of the nodes for pointers, because it knows all the nodes are the same type.

Obviously, this is a special case and easily handled with destructors in C++. The real question is whether there is way to analyse types used in a program, and direct the collector to use the resulting information to advantage. I guess you'd call this a type directed garbage collector.

Upvotes: 4

Views: 109

Answers (2)

EmeryBerger
EmeryBerger

Reputation: 3966

The idea of at least exploiting containers for garbage collection in some way is not new, though in Java, you cannot generally assume that a container holds the only reference to objects within it, so your approach will not work in that context.

Here are a couple of references. One is for leak detection, and the other (from my research group) is about improving cache locality.

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4814126 http://www.cs.umass.edu/~emery/pubs/06-06.pdf

You might want to visit Richard Jones's extensive garbage collection bibliography for more references, or ask the folks on gc-list.

Upvotes: 5

Matthieu M.
Matthieu M.

Reputation: 300029

I don't think it has anything to do with a specific algorithm.

When the GC computes the graph of objects relationship, the information that a Collection object is sole responsible for those elements of the list is implicitly present in the graph if the compiler was good enough to extract it.

Whatever the GC algorithm chosen: the information depends more on how the compiler/runtime will extract this information.

Also, I would avoid C and C++ with GC. Because of pointer arithmetic, aliasing and the possibility to point within an object (reference on a data member or in an array), it's incredibly hard to perform accurate garbage collection in these languages. They have not been crafted for it.

Upvotes: 0

Related Questions