Reference Counting

Reference counting approach is super simple. It is based on the idea of counting the number of pointer references to each allocated object. It’s a direct method that also happens to be naturally incremental as it distributes the memory management overhead throughout the program.

Other than memory management, reference counting is also broadly used as a resource management mechanism in operating systems for managing system resources like files, sockets etc.

# new() allocates a new object. For brevity, we've ignored the object types and
# assumed that all objects are of same type and size.
def new():
	obj = allocate_memory()
	obj.set_reference_count(1)
	return obj
# delete() is invoked when an object is no longer required by the client program
def delete(obj):
	obj.decrement_reference_count()
	if obj.get_reference_count() == 0:
		for child in children(obj):
			delete(child)
		release_memory(obj)
# update() is the only blessed way to perform pointer assignments in the system.
def update(source, target):
	# We increment before deleting, this correctly deals with source == target case.
	target.increment_reference_count()
	delete(source)
	source = target

After delete(A) and delete(C) we ended up with an unreachable but connected component of an object sub-graph that isn't accessible from any of the roots but we are unable to reclaim its nodes because of non-zero references.

Luckily, all other garbage collection techniques (mark-sweep, mark-compact, copying etc.) can handle cyclic structures without breaking a sweat. That's why it isn't uncommon for systems that use reference counting as the primary garbage collection mechanism to leverage to a tracing collection algorithm once the heap is exhausted.

Responsiveness: The memory management overhead is distributed across the program and it generally results in a much smoother and responsive system compared to tracing collectors. Note that the processing overhead correlates with the size of the sub-graph pointed by the last pointer and it might be non-trivial in some cases.
Cache Performance: The spatial locality of a reference counting system is generally no worse than that of the actual client program and is typically better than the tracing GCs that need to trace through all the live objects.
Immediate Memory Re-use: Unlike tracing collectors, where unreachable memory remains unallocated until the collector executes (generally on heap exhaustion); the reference counting approach allows immediate re-use of the discarded memory. This immediate re-use results in better temporal locality for caches that translates into fewer page-faults. It also simplifies resource cleanup as finalizers can be invoked right away resulting in quicker release of system resources. Immediate re-use of space also enables optimizations like in-place updates for data-structures.
Ease of Implementation: Reference counting based collection is the simplest garbage collection mechanism as far as implementation details are concerned. The implementation is particularly easy if the language runtime doesn't allow pointer manipulation and/or the programmers can't determine/manipulate the object roots.
Control vs Correctness vs : A reference counting system can provide the programmer with complete control over the object's allocation and de-allocation. It can allow a programmer to optimize away the reference counting overhead where its deemed safe. This does pose a correctness challenge and requires higher coding discipline. Even in the absence of clever optimizations, there's tight coupling between a client program's interface and the reference counting scheme. It requires clients to correctly invoke the operations that increment/decrement the reference counts.
Space Overhead: Each object carries the space overhead of the reference-count field. Theoretically, this could amount to 50% overhead for very small objects. This overhead needs to be weighed in against the immediate-reuse of memory cells and the fact that reference counting doesn't rely on heap-space during collection. A reference counting system could reduce the space overhead by using a single byte for ref-count instead of using a full-word. Such systems augment reference-counting with a fall-back tracing scheme (like mark-sweep) to collect objects with maxed out reference counts (and circular references).
Pointer Update Overhead: Unlike tracing schemes, where pointer updates are free, reference counting imposes significant overhead as each pointer update requires updating two reference counts to maintain program's correctness.
Cyclic Structures: As we discussed earlier, the biggest drawback of reference counting is its inability to reclaim cyclic storage. Under simple reference counting approach, cyclic data-structures like doubly linked lists or non-simple graphs cannot be efficiently reclaimed and will leak memory.

__default