What "time precise" garbage collection algorithms do exist?

6
votes

Which garbage collection algorithms can recognize garbage objects as soon as they become garbage?

The only thing which comes to my mind is reference counting with an added cycle-search every time a reference count is decremented to a non-zero value.

Are there any other interesting collection algorithms which can achieve that? (Note that I'm asking out of curiosity only; I'm aware that all such collectors would probably be incredibly inefficient)

2
language-agnosticgarbage-collection
There was a posting today on Hacker News about realtime GC. (I did not read it) - leppie
You could run the mark-and-sweep GC after each reference change. Though that would be extremely inefficient. - svick
@svick: You're right. Now i feel stupid :) - Askaga
@leppie Real-time GC means that the code whose memory allocation is governed by the GC can be real-time, for example by guaranteeing a certain percentage of CPU utilization over a sliding time window. It has nothing to do with promptness of deallocation. In fact, this goal (like many other goals) is in conflict with it.. - user395760
There is none, efficiently determining if an object is garbage is like np-hard. Detecting garbage cycles sounds easy but is in reality incredibly hard to do. In the worst case, the work is equivalent to doing a full mark phase in a mark&sweep collector. - Björn Lindqvist

2 Answers

0
votes

Though not being a garbage collection algorithm, escape analysis allows reasoning about life-time of objects. So, if efficiency is a concern and objects should be collected not in all but in "obvious" cases, it can be handy. The basic idea is to perform static analysis of the program (at compile time or at load time if compiled for a VM) and to figure out if a newly created object may escape a routine it is created in (hence the name of the analysis). If the object is not passed anywhere else, not stored in global memory, not returned from the given routine, etc., it can be released before returning from this routine or even earlier, at the place of its last use.

The objects that do not live longer than the associated method call can be allocated on the stack rather than in the heap so they can be removed from the garbage collection cycle at compile time thus lowering pressure on the general GC.

-4
votes

Such a mechanism would be called "heap management", not garbage collection.

By definition, garbage collection is decoupled from heap management. This is because in some environments/applications it is more efficient to skip doing a "free" operation and keeping track of what is in use. Instead, every once in a while, just ago around and gather all the unreferenced nodes and put them back on the free list.

== Addendum ==

I am being downvoted for attempting to correct the terminology of heap management with garbage collection. The Wikipedia article agrees with my usage, and what I learned at university, even though that was several decades ago. Languages such as Lisp and Snobol invented the need for garbage collection. Languages such as C don't provide such a heavy duty runtime environment; instead the rely on the programmer to manage cleanup of unused bits of memory and resources.