| Reference Counting |
Article Index for Reference |
Website Links For Reference |
Information AboutReference Counting |
| CATEGORIES ABOUT REFERENCE COUNTING | |
| garbage collection computer science | |
|
USE IN GARBAGE COLLECTION Reference counting is often known as a Garbage Collection algorithm where each object contains a count of the number of Reference s to it held by other objects. If an object's reference count reaches zero, the object has become inaccessible, and it is destroyed. Simple reference counts require frequent updates. Whenever a reference is destroyed or overwritten, the reference count of the object it references is decremented, and whenever one is created or copied, the reference count of the object it references is incremented. Reference counting is also used in disk operating systems and distributed systems. There doing a full tracing garbage collection would be far too time consuming. ADVANTAGES AND DISADVANTAGES The main advantage of reference counting over Tracing Garbage Collection is that objects are reclaimed as soon as they can no longer be referenced, and in an incremental fashion, without long pauses for collection cycles and with clearly defined lifetime of every object. In real-time applications or systems with limited memory, this is important to maintain responsiveness. Reference counting is also among the simplest forms of garbage collection to implement. It also allows for effective management of non-memory resources such as operating system objects, which are often much scarcer than memory (tracing GC systems use finalizers for this, but the delayed reclamation may cause problems). Weighted Reference Counts are a good solution for garbage collecting a distributed system. Reference counting in naïve form has two main disadvantages over the Tracing Garbage Collection , both of which require additional mechanisms to ameliorate:
GRAPH INTERPRETATION When dealing with garbage collection schemes, it's often helpful to think of the reference graph, which is a Directed Graph where the Vertices are objects and there is an edge from an object A to an object B if A holds a reference to B. We also have a special vertex or vertices representing the local variables and references held by the runtime system, and no edges ever go to these nodes, although edges can go from them to other nodes. In this context, the simple reference count of an object is the In Degree of its vertex. Deleting a vertex is like collecting an object. It can only be done when the vertex has no incoming edges, so it does not affect the out degree of any other vertices, but it can affect the in degree of other vertices, causing their corresponding objects to be collected as well. In the graph interpretation, reference cycles are Cycle s. The connected component containing the special vertex contains the objects that can't be collected, while other connected components of the graph only contain garbage. By the nature of reference counting, each of these garbage components must contain at least one cycle. DEALING WITH INEFFICIENCY OF UPDATES Incrementing and decrementing reference counts every time a reference is created or destroyed can significantly impede performance. Not only do the operations take time, but they damage Cache performance and can lead to Pipeline Bubble s. Even read-only operations like calculating the length of a list require a large number of reads and writes for reference updates with naïve reference counting. One simple technique is for the compiler to combine a number of nearby reference updates into one. This is especially effective for references which are created and quickly destroyed. Care must be taken, however, to put the combined update at the right position so that a premature free is avoided. The Deustch-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 data structures, but before an object with reference count zero can be deleted, the system must verify with a scan of the stack and registers that no other reference to it still exists. Another technique devised by Henry Baker involves deferred increments, in which references which are stored in local variables do not immediately increment the corresponding reference count, but instead defer this until it is necessary. If such a reference is destroyed quickly, then there is no need to update the counter. This eliminates a large number of updates associated with short-lived references. However, if such a reference is copied into a data structure, then the deferred increment must be performed at that time. It is also critical to perform the deferred increment before the object's count drops to zero, resulting in a premature free. See the paper for more. A dramatic decrease in the overhead on counter updates was obtained by Levanoni and Petrank . They showed how to eliminate more than 99% of the counter updates for typical Java benchmarks. Furthermore, they present an enhanced algorithm that may run concurrently with multithreaded applications employing only fine synchronization. See the paper for more. Blackburn and McKinley's |
|
|