Topic: memory management by reference counting

operating system > Group: memory management

memory management
disk allocation
heap memory management
memory management by garbage collection
register allocation by usage counts

topics f-m


Reference counting is an efficient technique for managing memory. When memory is allocated or referenced, its reference count is incremented. When a reference goes out of scope, the corresponding reference count is decremented. When the reference count is zero, the memory is deallocated.

Reference counting can avoid deep copies, with a copy only occuring on write. Reference counting is useful for garbage collection. (cbb 12/07)

Subtopic: safe reference counting up

Quote: simple, fast, and safe manual memory management for type-safe languages; DanglingReferenceException on dereference of a deleted object; 64-bit address space [kediP6_2017]

Subtopic: group reference counting up

Quote: methods for group reference counting; used in memory management for reentrant structures [bobrDG7_1980]
Quote: manage memory for reentrant structures by a reference count for the group as a whole; internal references not counted [bobrDG7_1980]
Quote: a fast, cyclic reference counting algorithm based on partial traces and sub-graphs; total execution time is similar [linCY3_2007]

Subtopic: multithreaded reference counting up

Quote: lock-free reference counting (LFRC) of dynamic-sized concurrent data structures; requires double compare-and-swap, no cycles, sequentially-consistent shared memory, and read access to deleted objects [detlDL12_2002]
Quote: efficient, reference-counting memory allocation without synchronization at write barrier; adds log pointer to each object [levaY1_2006]
Quote: read-copy-update is reference-counting without memory allocation, bulk updates, and extensions; with per-thread RCU read-side critical sections, a shared object is available after context switches by all CPUs [mckePE7_2013]

Subtopic: distributed reference counting up

Quote: each message in a timely dataflow graph has a logical timestamp; an event notification fires when all messages for a timestamp have appeared at a node; implemented as distributed reference counting [murrDG10_2016]

Subtopic: hazard pointers up

Quote: instead of reference counters, record a pointer to that data element in a per-thread list of hazard pointers; defer free operations until no hazard pointers in any thread; better performance and scalability [mckePE7_2013]

Subtopic: phantom links up

Quote: concurrent, parallel garbage collection in linear time; phantomizing a link transfers a reference count to the target; strong pointers without cycles; weak pointers close cycles and link arbitrarily [branSR6_2014]

Subtopic: reference counting of files up

Quote: segment freed in the backing store server when its reference count becomes zero; counts Inames in indices [birrAD9_1980]

Subtopic: reference count as deep copy up

Quote: increment reference count instead of sending deep copies over a channel; requires immutable objects [kumaS6_2001]

Subtopic: owned objects up

Quote: use single-bit reference count for owned objects; e.g., most list cells in Lisp [abduSE9_1998]

Subtopic: object-oriented reference counting up

Quote: reclaim dead, object-oriented data as early as possible with reference-counting; use data-flow and liveness analysis [joisPG3_2008]
Quote: liveness analysis with exceptions needs additional reference-counting updates for dead-data [joisPG3_2008]

Subtopic: per-line live object counts up

Quote: RCImmix is a reference-counting collector with per-line live object counts and reference copying of heap objects; faster than generational collector [shahR10_2013]

Subtopic: pointer rotations up

Quote: pointer rotation preserves the number of pointers to a record; reference counts are preserved [suzuN_1980]
Quote: linear lists and trees have reference counts of one; pointer rotation preserves this; prevents circularity or shared cells [suzuN_1980]
Quote: if a computation preserves reference counts and number of reachable records, then is implemented solely by pointer rotations [suzuN_1980]

Subtopic: reference counting with garbage collecting up

Quote: memory management is integrated with Dis; all data items are typed; reference counting plus real-time coloring collector [wintP8_1997]
Quote: faster reference counting with similar performance as a well tuned mark-sweep collector [shahR6_2012]
Quote: tracing and reference counting are algorithmic duals for garbage collection; live vs. dead objects, anti-operations [bacoDF10_2004]
Quote: tracing and reference counting are duals -- tracing the object graph, scanning an object [bacoDF10_2004]
Quote: garbage collect if a reference count becomes negative; indicates an allocation cycle [birrAD9_1980]
Quote: manage memory with reference counting and a sweep algorithm for circular structures; provides benefits of garbage collection at low cost [dorwSM1_1997]
Quote: use reference counting and local mark-scan to detect cyclic structures [abduSE9_1998]
Quote: Recycler multiprocessor garbage collector with low pause times; loosely synchronized, concurrent reference counting; local, concurrent cycle detection [bacoDF6_2001]

Subtopic: reuse dead objects up

Quote: reuse dead objects, from the same allocation site, that were previously cached and currently unreachable; needs reference count and method invocation information [xuG10_2013]

Subtopic: deferred reference counting up

Quote: RCImmix performs deferred reference counting and occasional backup cycle tracing; allocates new objects as dead without reference counting [shahR10_2013]
Quote: RCImmix counts live objects per line with opportunistic, proactive copying to reduce fragmentation [shahR10_2013]

Subtopic: reference counting vs. optimization up

Quote: Python JIT compiler ignores reference counting during most of the optimization phases; adds reference counting later; avoids fragmentation of basic blocks for better data-flow analysis [castJ10_2012]

Subtopic: performance of reference counting up

Quote: faster reference counting with limited counts, lazy mod-buf insertion, and allocate as dead; 24% faster [shahR6_2012]
Quote: multiprocessor, reference counting without synchronized operations; 100x reduction in maximal response time for garbage collection [levaY10_2001]

Subtopic: implementation up

Quote: almost all reference counts are less than five; many reference counts are to new objects [shahR10_2013]
Quote: a 2-bit reference-count suffices for 95% of the objects [levaY1_2006]

Subtopic: inconsistent increment-decrement path pair up

Quote: static discovery of reference count bugs due to inconsistent increment-decrement path pairs; uncovered 90 bugs in the latest Linux kernel [maoJ4_2016]

Subtopic: examples up

Quote: in ESP, memory safety is a local property of each process; reference counting of link/unlink; communicates immutable, acyclic objects; easily verified by SPIN [kumaS6_2001]
Quote: Smalltalk-80 uses reference-counting for garbage collection [krasG8_1981]
Quote: Oberon's modules only released by explicit command; imported modules released by reference counting (no reference cycles) [wirtN9_1989]
Quote: Euclid allocates storage from collections with optional reference counting for automatic deallocation; may specify storage management module [shawM3_1980]

Subtopic: problems with real-time up

Quote: worst-case reference-counting space overhead is highly atypical, but must be considered for real-time embedded applications; maximum pause time worse than tracing collectors [boehHJ1_2004]

Subtopic: avoid reference-counting up

Quote: can eliminate reference-counting for stack-based allocations [abduSE9_1998]
Quote: most high-performance, general-purpose systems use tracing garbage collectors instead of reference counting [wilsPR9_1992]
Quote: reference counting is expensive, especially with cache memory [blacSM6_2004]

Related up

Topic: disk allocation
Topic: heap memory management
Topic: memory management by garbage collection
Topic: register allocation by usage counts

Subtopics up

avoid reference-counting
deferred reference counting
distributed reference counting
group reference counting
hazard pointers
inconsistent increment-decrement path pair
multithreaded reference counting
object-oriented reference counting
owned objects
per-line live object counts
performance of reference counting
phantom links
pointer rotations
problems with real-time
reference count as deep copy
reference counting of files
reference counting vs. optimization
reference counting with garbage collecting
reuse dead objects
safe reference counting

Updated barberCB 3/06
Copyright © 2002-2023 by C.B. Barber
Thesa, Avev, and thid-... are trademarks of C.B. Barber