Dealing With Reference Cycles
There are a variety of ways of handling the problem of detecting and collecting reference cycles. One is that a system may explicitly forbid reference cycles. In some systems like filesystems this is a common solution. Another example is the Cocoa framework, which recommends avoiding reference cycles by using "strong" (counted) references for "parent-to-child" references, and "weak" (non-counted) references for "child-to-parent" references. Cycles are also sometimes 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.
Another solution 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.
Bacon describes a cycle-collection algorithm for reference counting systems with some similarities to tracing systems, including the same theoretical time bounds, but that takes advantage of reference count information to run much more quickly and with less cache damage. It's based on the observation that an object cannot appear in a cycle until its reference count is decremented to a nonzero value. All objects which this occurs to 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 when decrementing all the reference counts on a cycle of references brings them all down to zero. An enhanced version of this algorithm by Paz et al. is able to run concurrently with other operations and improve its efficiency by using the update coalescing method of Levanoni and Petrank. See the paper for more.
Read more about this topic: Reference Counting
Famous quotes containing the words dealing with, dealing, reference and/or cycles:
“They [women] can use their abilities to support each other, even as they develop more effective and appropriate ways of dealing with power.... Women do not need to diminish other women ... [they] need the power to advance their own development, but they do not “need” the power to limit the development of others.”
—Jean Baker Miller (20th century)
“In my dealing with my child, my Latin and Greek, my accomplishments and my money stead me nothing; but as much soul as I have avails. If I am wilful, he sets his will against mine, one for one, and leaves me, if I please, the degradation of beating him by my superiority of strength. But if I renounce my will, and act for the soul, setting that up as umpire between us two, out of his young eyes looks the same soul; he reveres and loves with me.”
—Ralph Waldo Emerson (1803–1882)
“If we define a sign as an exact reference, it must include symbol because a symbol is an exact reference too. The difference seems to be that a sign is an exact reference to something definite and a symbol an exact reference to something indefinite.”
—William York Tindall (1903–1981)
“The stars which shone over Babylon and the stable in Bethlehem still shine as brightly over the Empire State Building and your front yard today. They perform their cycles with the same mathematical precision, and they will continue to affect each thing on earth, including man, as long as the earth exists.”
—Linda Goodman (b. 1929)