Editing Garbage collection (computer science) (section)

== Strategies ==
=== Tracing ===
{{Main|Tracing garbage collection}}

[[Tracing garbage collection]] is the most common type of garbage collection, so much so that "garbage collection" often refers to tracing garbage collection, rather than other methods such as [[reference counting]]. The overall strategy consists of determining which objects should be garbage collected by tracing which objects are ''reachable'' by a chain of references from certain root objects, and considering the rest as garbage and collecting them. However, there are a large number of algorithms used in implementation, with widely varying complexity and performance characteristics.

=== Reference counting ===
{{Main|Reference counting}}
Reference counting garbage collection is where each object has a count of the number of references to it. Garbage is identified by having a reference count of zero. An object's reference count is incremented when a reference to it is created and decremented when a reference is destroyed. When the count reaches zero, the object's memory is reclaimed.<ref name="MS_2009"/>

As with manual memory management, and unlike tracing garbage collection, reference counting guarantees that objects are destroyed as soon as their last reference is destroyed, and usually only accesses memory which is either in [[CPU cache]]s, in objects to be freed, or directly pointed to by those, and thus tends to not have significant negative side effects on CPU cache and [[virtual memory]] operation.

There are a number of disadvantages to reference counting; this can generally be solved or mitigated by more sophisticated algorithms:

; Cycles: If two or more objects refer to each other, they can create a cycle whereby neither will be collected as their mutual references never let their reference counts become zero. Some garbage collection systems using reference counting (like the one in [[CPython]]) use specific cycle-detecting algorithms to deal with this issue.<ref name="Python_2008"/> Another strategy is to use [[weak reference]]s for the "backpointers" which create cycles. Under reference counting, a weak reference is similar to a weak reference under a tracing garbage collector. It is a special reference object whose existence does not increment the reference count of the referent object. Furthermore, a weak reference is safe in that when the referent object becomes garbage, any weak reference to it ''lapses'', rather than being permitted to remain dangling, meaning that it turns into a predictable value, such as a null reference.

; Space overhead (reference count): Reference counting requires space to be allocated for each object to store its reference count. The count may be stored adjacent to the object's memory or in a side table somewhere else, but in either case, every single reference-counted object requires additional storage for its reference count. Memory space with the size of an unsigned pointer is commonly used for this task, meaning that 32 or 64 bits of reference count storage must be allocated for each object. On some systems, it may be possible to mitigate this overhead by using a [[tagged pointer]] to store the reference count in unused areas of the object's memory. Often, an architecture does not actually allow programs to access the full range of memory addresses that could be stored in its native pointer size; a certain number of high bits in the address is either ignored or required to be zero. If an object reliably has a pointer at a certain location, the reference count can be stored in the unused bits of the pointer. For example, each object in [[Objective-C]] has a pointer to its [[class (computer programming)|class]] at the beginning of its memory; on the [[ARM64]] architecture using [[iOS 7]], 19 unused bits of this class pointer are used to store the object's reference count.<ref name="Ash_2013"/><ref name="Sealie_2013"/>

; Speed overhead (increment/decrement): In naive implementations, each assignment of a reference and each reference falling out of scope often require modifications of one or more reference counters. However, in a common case when a reference is copied from an outer scope variable into an inner scope variable, such that the lifetime of the inner variable is bounded by the lifetime of the outer one, the reference incrementing can be eliminated. The outer variable "owns" the reference. In the programming language C++, this technique is readily implemented and demonstrated with the use of <code>const</code> references. Reference counting in C++ is usually implemented using "[[smart pointer]]s"<ref name="Pibinger_2005"/> whose constructors, destructors, and assignment operators manage the references. A smart pointer can be passed by reference to a function, which avoids the need to copy-construct a new smart pointer (which would increase the reference count on entry into the function and decrease it on exit). Instead, the function receives a reference to the smart pointer which is produced inexpensively. The Deutsch-Bobrow method of reference counting capitalizes on the fact that most reference count updates are in fact generated by references stored in local variables. It ignores these references, only counting references in the heap, but before an object with reference count zero can be deleted, the system must verify with a scan of the stack and register that no other reference to it still exists. A further substantial decrease in the overhead on counter updates can be obtained by update coalescing introduced by Levanoni and [[Erez Petrank|Petrank]].<ref name="Levanoni-Petrank_2001"/><ref name="Levanoni-Petrank_2006"/> Consider a pointer that in a given interval of the execution is updated several times. It first points to an object <code>O1</code>, then to an object <code>O2</code>, and so forth until at the end of the interval it points to some object <code>On</code>. A reference counting algorithm would typically execute <code>rc(O1)--</code>, <code>rc(O2)++</code>, <code>rc(O2)--</code>, <code>rc(O3)++</code>, <code>rc(O3)--</code>, ..., <code>rc(On)++</code>. But most of these updates are redundant. In order to have the reference count properly evaluated at the end of the interval it is enough to perform <code>rc(O1)--</code> and <code>rc(On)++</code>. Levanoni and Petrank measured an elimination of more than 99% of the counter updates in typical Java benchmarks.

; Requires atomicity: When used in a [[thread (computing)|multithreaded]] environment, these modifications (increment and decrement) may need to be [[atomic operation]]s such as [[compare-and-swap]], at least for any objects which are shared, or potentially shared among multiple threads. Atomic operations are expensive on a multiprocessor, and even more expensive if they have to be emulated with software algorithms. It is possible to avoid this issue by adding per-thread or per-CPU reference counts and only accessing the global reference count when the local reference counts become or are no longer zero (or, alternatively, using a binary tree of reference counts, or even giving up deterministic destruction in exchange for not having a global reference count at all), but this adds significant memory overhead and thus tends to be only useful in special cases (it is used, for example, in the reference counting of Linux kernel modules). Update coalescing by Levanoni and Petrank<ref name="Levanoni-Petrank_2001"/><ref name="Levanoni-Petrank_2006"/> can be used to eliminate all atomic operations from the write-barrier. Counters are never updated by the program threads in the course of program execution. They are only modified by the collector which executes as a single additional thread with no synchronization. This method can be used as a stop-the-world mechanism for parallel programs, and also with a concurrent reference counting collector.

; Not real-time: Naive implementations of reference counting do not generally provide real-time behavior, because any pointer assignment can potentially cause a number of objects bounded only by total allocated memory size to be recursively freed while the thread is unable to perform other work. It is possible to avoid this issue by delegating the freeing of unreferenced objects to other threads, at the cost of extra overhead.

=== Escape analysis ===
{{Main|Escape analysis}}
[[Escape analysis]] is a compile-time technique that can convert [[heap allocation]]s to [[stack allocation]]s, thereby reducing the amount of garbage collection to be done. This analysis determines whether an object allocated inside a function is accessible outside of it. If a function-local allocation is found to be accessible to another function or thread, the allocation is said to "escape" and cannot be done on the stack. Otherwise, the object may be allocated directly on the stack and released when the function returns, bypassing the heap and associated memory management costs.<ref name="Salagnac-Yovine-Garbervetsky_2005"/>