Reference-counting garbage collection
This is the most naive garbage collection algorithm. This algorithm reduces the definition of “an object is not needed anymore” to “an object has no other objects referencing it”. An object is considered garbage collectible if there are zero references pointing at this object.
There is a limitation when it comes to cycles. In the following example, two objects are created and reference one another, thus creating a cycle. They will go out of scope after the function call, so they are effectively useless and could be freed. However, the reference-counting algorithm considers that since each of the two objects is referenced at least once, neither can be garbage-collected.
Mark-and-sweep algorithm(widely used)
This algorithm reduces the definition of “an object is not needed anymore” to “an object is unreachable”.
- Local variables and parameters of the current function.
- Variables and parameters for other functions on the current chain of nested calls.
- Global variables.
- (there are some other, internal ones as well)
These values are called roots.
Periodically, the garbage-collector will start from these roots, find all objects that are referenced from these roots, then all objects referenced from these, etc. Starting from the roots, the garbage collector will thus find all reachable objects and collect all non-reachable objects.
This algorithm is better than the previous one since “an object has zero references” leads to this object being unreachable. The opposite is not true as we have seen with cycles.