Tracing garbage collection

For example: The problem of precisely identifying semantic garbage can easily be shown to be partially decidable: a program that allocates an object

The garbage collector can reclaim only objects that have no references pointing to them either directly or indirectly from the root set.

[3] A softly referenced object is only eligible for reclamation if the garbage collector decides that the program is low on memory.

Special behavior takes place when either the key or value or both become garbage: the hash table entry is spontaneously deleted.

The use of a regular hash table for such a purpose could lead to a "logical memory leak": the accumulation of reachable data which the program does not need and will not use.

In the naive mark-and-sweep method, each object in memory has a flag (typically a single bit) reserved for garbage collection use only.

This method has several disadvantages, the most notable being that the entire system must be suspended during collection; no mutation of the working set can be allowed.

The tri-color method has an important advantage – it can be performed "on-the-fly", without halting the system for significant periods of time.

[5] Not only do collectors differ in whether they are moving or non-moving, they can also be categorized by how they treat the white, grey and black object sets during a collection cycle.

This approach is very simple, but since only one semi space is used for allocating objects, the memory usage is twice as high compared to other algorithms.

As the reference tree is traversed during a collection cycle (the "mark" phase), these bits are manipulated by the collector.

It has been empirically observed that in many programs, the most recently created objects are also those most likely to become unreachable quickly (known as infant mortality or the generational hypothesis).

When the garbage collector runs, it may be able to use this knowledge to prove that some objects in the initial white set are unreachable without having to traverse the entire reference tree.

If the generational hypothesis holds, this results in much faster collection cycles while still reclaiming most unreachable objects.

In order to implement this concept, many generational garbage collectors use separate memory regions for different ages of objects.

It may therefore occasionally be necessary to perform a full mark and sweep or copying garbage collection to reclaim all available space.

This has the disadvantage that the program can perform no useful work while a collection cycle is running (sometimes called the "embarrassing pause"[6]).

Incremental and concurrent garbage collectors are designed to reduce this disruption by interleaving their work with activity from the main program.

Careful design is necessary with these techniques to ensure that the main program does not interfere with the garbage collector and vice versa; for example, when the program needs to allocate a new object, the runtime system may either need to suspend it until the collection cycle is complete, or somehow notify the garbage collector that there exists a new, reachable object.

Conservative collectors may produce false positives, where unused memory is not released because of improper pointer identification.

Performance of tracing garbage collectors – both latency and throughput – depends significantly on the implementation, workload, and environment.

In terms of latency, simple stop-the-world garbage collectors pause program execution for garbage collection, which can happen at arbitrary times and take arbitrarily long, making them unusable for real-time computing, notably embedded systems, and a poor fit for interactive use, or any other situation where low latency is a priority.

However, incremental garbage collectors can provide hard real-time guarantees, and on systems with frequent idle time and sufficient free memory, such as personal computers, garbage collection can be scheduled for idle times and have minimal impact on interactive performance.

Manual memory management (as in C++) and reference counting have a similar issue of arbitrarily long pauses in case of deallocating a large data structure and all its children, though these only occur at fixed times, not depending on garbage collection.

However, this size segregation usually cause a large degree of external fragmentation, which can have an adverse impact on cache behaviour.

In some situations, most notably embedded systems, it is possible to avoid both garbage collection and heap management overhead by preallocating pools of memory and using a custom, lightweight scheme for allocation/deallocation.

Generational collection techniques are used with both stop-the-world and incremental collectors to increase performance; the trade-off is that some garbage is not detected as such for longer than normal.

A real-time garbage collector should guarantee that even in the worst case it will dedicate a certain number of computational resources to mutator threads.

For work based analysis, MMU (minimal mutator utilization)[9] is usually used as a real-time constraint for the garbage collection algorithm.

A study of algorithms that allow non-blocking real-time concurrent garbage collection appears in a paper by Pizlo et al. in Microsoft Research.