What are the “exact” garbage collection algorithms?

Question

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

The only thing that comes to my mind is link counting with an added search loop every time the link count is reduced to a non-zero value.

Are there any other interesting collection algorithms that can achieve this? (Note that I only ask about curiosity, I know that all such collectors are likely to be incredibly inefficient)

Answer 1

Although this is not a garbage collection algorithm, escape analysis allows you to talk about the lifetime of objects. Thus, if efficiency is a problem, and objects should not be collected in all, but in the “obvious” cases, this can be convenient. The main idea is to perform a static analysis of the program (during compilation or during loading, if it was compiled for a virtual machine) and find out whether the newly created object can avoid the execution of the procedure in which it was created (hence the name of the analysis), If the object is not transferred anywhere, is not stored in global memory, is not returned from this procedure, etc., it can be freed before returning from this procedure or even earlier, in the place of its last use.

Objects that do not live longer than the associated method call can be allocated on the stack rather than on the heap so that they can be removed from the garbage collection cycle during compilation, thereby reducing pressure on the overall GC.

Answer 2

Such a mechanism would be called "heap management" rather than garbage collection.

By definition, garbage collection is separate from heap management. This is due to the fact that in some environments / applications it is more efficient to skip the "free" operation and keep track of what is being used. Instead, from time to time, just back, and collect all unaccounted nodes and put them in a free list.

== Addition ==

I'm being underestimated for trying to fix the heap management terminology with garbage collection. Wikipedia article is consistent with my use and what I learned at the university, although that was several decades ago. Languages ​​such as Lisp and Snobol have come up with the need for garbage collection. Languages ​​such as C do not provide such a complex runtime; instead rely on the programmer to control the cleaning of unused bits of memory and resources.