Content deleted Content added
added more general introduction, reference counting is not just about garbage collection |
fix sections, remove some redundant text |
||
Line 1:
==
In [[computer science]], '''reference counting''' is a technique of storing the number of references, pointers or handles to a resource such as an object or block of memory.
▲In [[computer science]], '''reference counting''' is a technique of storing the number of references, pointers or handles to a resource such as an object or block of memory. Reference counting forms the basis of a software design pattern used frequently for [[computer memory garbage collection|garbage collection]] algorithms, with which it is most commonly associated.
== Use in garbage collection==
Reference counting is often known as a [[computer memory garbage collection|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.
Line 10 ⟶ 8:
== Advantages and disadvantages ==
Reference counting has two main disadvantages over the more common [[tracing garbage collection]], both of which require additional mechanisms to ameliorate. One is that the frequent updates it involves are a source of inefficency. The other is that the naive algorithm described above can't handle reference cycles, where an object refers indirectly to itself; cycles of objects are never collected. It also has the more minor problem that every object must reserve space for a reference count.
Line 16 ⟶ 13:
== 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.
Line 24 ⟶ 20:
== 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 bubbles. Even read-only operations like calculating the length of a list require a large number of reads and writes for reference updates with naive reference counting.
Line 34 ⟶ 29:
== Dealing with reference cycles ==
There are a variety of ways of handling the problem of collecting reference cycles. One is that a system may explicitly forbid reference cycles. In some systems like filesystems this is a common solution. Cycles are also sometimes ignored in systems with short lives and a small amount of cyclic garbage, particularly when the system was developed using a methodology of avoiding cyclic data structures wherever possible, typically at the expense of efficiency.
Line 42 ⟶ 36:
== Variants of reference counting ==
Although it's possible to augment simple reference counts in a variety of ways, often a better solution can be found by performing reference counting in a fundamentally different way. Here we describe some of the variants on reference counting and their benefits and drawbacks.
=== Weighted reference counting ===
In weighted reference counting, we assign each reference a <i>weight</i>, and each object tracks not the number of references referring to it, but the total weight of the references referring to it. The initial reference to a newly-created object has a large weight, such as 2<sup>16</sup>. Whenever this reference is copied, half of the weight goes to the new reference, and half of the weight stays with the old reference. Because the total weight does not change, the object's reference count does not need to be updated.
Line 58 ⟶ 50:
== External links ==
* [http://www.memorymanagement.org/articles/recycle.html#reference The Memory Manager Reference: Beginner's Guide: Recycling: Reference Counts]
* [http://citeseer.nj.nec.com/baker94minimizing.html ''Minimizing Reference Count Updating with Deferred and Anchored Pointers for Functional Data Structures'', Henry G. Baker]
| |||