Reference counting

In computer science, reference counting is a garbage collection algorithm where each object contains 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 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 it incremented.

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.

The main advantage of reference counting over tracing 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. In real-time applications or systems with limited memory, this is important to maintain responsiveness. Some forms of referencing counting are also useful in distributed applications and applications with persistent object stores.

Dealing with inefficiency of updates

TODO

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. They are also sometimes ignored in systems with short lives and a small amount of cyclic garbage.

Another is to periodically use a tracing garbage collector to reclaim cycles. Since cycles typically constitute a relatively small amount of reclaimed space, the collection cycles can be spaced much farther apart than with an ordinary tracing garbage collector.

Talk here about special cycle-collecting reference-counting algorithms

Variants of reference counting

TODO

Weighted reference counting

TODO

External Links

• The Memory Manager Reference: Beginner's Guide: Recycling: Reference Counts
• Minimizing Reference Count Updating with Deferred and Anchored Pointers for Functional Data Structures, Henry G. Baker
• Concurrent Cycle Collection in Reference Counted Systems, David F. Bacon

---

This article (or an earlier version of it) contains material from FOLDOC, used with permission.