Reference counting

related topics
{math, number, function}
{system, computer, user}
{rate, high, increase}
{work, book, publish}
{build, building, house}

In computer science, reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object, block of memory, disk space or other resource. It may also refer, more specifically, to a garbage collection algorithm that uses these reference counts to deallocate objects which are no longer referenced.

Contents

Use in garbage collection

As a garbage collection algorithm, reference counting tracks for each object a count of the number of references to it held by other objects. If an object's reference count reaches zero, the object has become inaccessible, and can be destroyed.

When an object is destroyed, any objects referenced by that object also have their reference counts decreased. Because of this, removing a single reference can potentially lead to a large number of objects being freed. A common modification allows reference counting to be made incremental: instead of destroying an object as soon as its reference count becomes zero, it is added to a list of unreferenced objects, and periodically (or as needed) one or more items from this list are 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, where full non-incremental tracing garbage collection is too time consuming because of the size of the object graph and slow access speed.

Full article ▸

related documents
Dylan (programming language)
Control flow
Busy beaver
Structured programming
AWK
Communication complexity
Relational database
Object-oriented programming
P = NP problem
Riemannian manifold
Imaginary unit
Multiplication
Finite set
Semidirect product
Exponentiation by squaring
Quadratic equation
Exponential function
Monoid
General linear group
Interpolation
Category theory
Operator
Hamming code
Set (mathematics)
Exception handling
Metric space
Wikipedia:Searching
Dirac delta function
Lie algebra
Taylor's theorem