Editing Reference counting (section)

==Dealing with reference cycles==
Perhaps the most obvious way to handle reference cycles is to design the system to avoid creating them. A system may explicitly forbid reference cycles; file systems with [[hard link]]s often do this. Judicious use of [[weak reference|"weak" (non-counted) references]] may also help avoid retain cycles; the [[Cocoa (API)|Cocoa]] framework, for instance, recommends using "strong" references for parent-to-child relationships and "weak" references for child-to-parent relationships.<ref>{{cite web|url=https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/MemoryMgmt/Articles/mmObjectOwnership.html#//apple_ref/doc/uid/20000043-1044135-BCICCFAE |title=Mac Developer Library |publisher=Developer.apple.com |access-date=2015-12-17}}</ref>

Systems may also be designed to tolerate or correct the cycles they create in some way. Developers may design code to explicitly "tear down" the references in a data structure when it is no longer needed, though this has the cost of requiring them to manually track that data structure's lifetime. This technique can be automated by creating an "owner" object that does the tearing-down when it is destroyed; for instance, a [[Graph (abstract data type)|Graph]] object's destructor could delete the edges of its GraphNodes, breaking the reference cycles in the graph. Cycles may even be 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.

Computer scientists have also discovered ways to [[cycle detection (graph theory)|detect]] and collect reference cycles automatically, without requiring changes in the data structure design. One simple solution is to periodically use a [[tracing garbage collection|tracing garbage collector]] to reclaim cycles; since cycles typically constitute a relatively small amount of reclaimed space, the collector can be run much less often than with an ordinary tracing garbage collector.

Bacon describes a cycle-collection algorithm for reference counting with similarities to tracing collectors, including the same theoretical time bounds. It is based on the observation that a cycle can only be isolated when a reference count is decremented to a nonzero value. All objects which this occurs on are put on a ''roots'' list, and then periodically the program searches through the objects reachable from the roots for cycles. It knows it has found a cycle that can be collected when decrementing all the reference counts on a cycle of references brings them all down to zero.<ref>{{cite book|doi=10.1007/3-540-45337-7_12|chapter=Concurrent Cycle Collection in Reference Counted Systems|title=ECOOP 2001 — Object-Oriented Programming|volume=2072|pages=207–235|series=Lecture Notes in Computer Science|year=2001|last1=Bacon|first1=David F.|last2=Rajan|first2=V. T.|isbn=978-3-540-42206-8|chapter-url=http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf|archive-url=https://web.archive.org/web/20040723163601/http://www.research.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf|archive-date=23 July 2004}}</ref> An enhanced version of this algorithm by Paz et al.<ref>{{cite journal
| author = Harel Paz, David F. Bacon, Elliot K. Kolodner, [[Erez Petrank]], V. T. Rajan
| year = 2007
| title = An efficient on-the-fly cycle collection
| journal = [[ACM Transactions on Programming Languages and Systems]] 
| volume = 29
| issue = 4
| pages = 20–es
| doi = 10.1145/1255450.1255453
| citeseerx = 10.1.1.10.2777
| s2cid = 4550008
}}</ref> is able to run concurrently with other operations and improve its efficiency by using the update coalescing method of Levanoni and Petrank.<ref name="LevPet1" /><ref name="LevPet2" />