title: Feasibility of automatic cycle breaker for `std::shared_ptr`
body: <p>C++11 introduced reference-counted smart pointers, <code>std::shared_ptr</code>. Being reference counted, these pointers are unable to automatically reclaim cyclic data structures. However, automatic collection of reference cycles was shown to be possible, for example by <a href="http://arctrix.com/nas/python/gc/" rel="nofollow noreferrer">Python</a> and <a href="http://php.net/manual/en/features.gc.collecting-cycles.php" rel="nofollow noreferrer">PHP</a>. To distinguish this technique from garbage collection, the rest of the question will refer to it as <em>cycle breaking</em>.</p>
  
  <p>Given that there seem to be no proposals to add equivalent functionality to C++, is there a fundamental reason why a cycle breaker similar to the ones already deployed in other languages wouldn't work for <code>std::shared_ptr</code>?</p>
  
  <p>Note that this question doesn't boil down to "why isn't there a GC for C++", which <a href="https://stackoverflow.com/q/147130/1600898">has been asked before</a>. A C++ GC normally refers to a system that automatically manages <em>all</em> dynamically allocated objects, typically implemented using some form of Boehm's conservative collector. It has been <a href="https://stackoverflow.com/a/19466425/1600898">pointed out</a> that such a collector is not a good match for RAII. Since a garbage collector primarily manages memory, and might not even be called until there is a memory shortage, and C++ destructors manage other resources, relying on the GC to run destructors would introduce non-determinism at best and resource starvation at worst. It has also bee pointed out that a full-blown GC is largely unnecessary in the presence of the more explicit and predictable smart pointers.</p>
  
  <p>However, a library-based cycle breaker for smart pointers (analogous to the one used by reference-counted interpreters) would have important differences from a general-purpose GC:</p>
  
  <ul>
  <li>It only cares about objects managed through <code>shared_ptr</code>. Such objects <em>already</em> participate in shared ownership, and thus have to handle delayed destructor invocation, whose exact timing depends on ownership structure.</li>
  <li>Due to its limited scope, a cycle breaker is unconcerned with patterns that break or slow down Boehm GC, such as pointer masking or huge opaque heap blocks that contain an occasional pointer.</li>
  <li>It can be opt-in, like <code>std::enable_shared_from_this</code>. Objects that don't use it don't have to pay for the additional space in the control block to hold the cycle breaker metadata.</li>
  <li>A cycle breaker doesn't require a comprehensive list of "root" objects, which is hard to obtain in C++. Unlike a mark-sweep GC which finds all live objects and discards the rest, a cycle breaker only traverses objects that can form cycles. In existing implementations, the type needs to provide help in the form of a function that enumerates references (direct or indirect) to other objects that can participate in a cycle.</li>
  <li>It relies on regular "destroy when reference count drops to zero" semantics to destroy cyclic garbage. Once a cycle is identified, the objects that participate in it are requested to clear their strongly-held references, for example by calling <code>reset()</code>. This is enough to break the cycle and would automatically destroy the objects. Asking the objects to provide and clear its strongly-held references (on request) makes sure that the cycle breaker does not break encapsulation.</li>
  </ul>
  
  <p>Lack of proposals for automatic cycle breaking indicates that the idea was rejected for practical or philosophical reasons. I am curious as what the reasons are. For completeness, here are some possible objections:</p>
  
  <ul>
  <li><p>"It would introduce non-deterministic destruction of cyclic <code>shared_ptr</code> objects." If the programmer were in control of the cycle breaker's invocation, it would not be non-deterministic. Also, once invoked, the cycle breaker's behavior would be predictable - it would destroy all currently known cycles. This is akin to how <code>shared_ptr</code> destructor destroys the underlying object once its reference count drops to zero, despite the possibility of this causing a "non-deterministic" cascade of further destructions.</p></li>
  <li><p>"A cycle breaker, just like any other form of garbage collection, would introduce pauses in program execution." Experience with runtimes that implement this feature shows that the pauses are minimal because the GC only handles cyclic garbage, and all other objects are reclaimed by reference counting. If the cycle detector is never invoked automatically, the cycle breaker's "pause" could be a predictable consequence of running it, similar to how destroying a large <code>std::vector</code> might run a large number of destructors. (In Python, the cyclic gc is run automatically, but there is API to <a href="https://docs.python.org/2/library/gc.html#gc.disable" rel="nofollow noreferrer">disable it</a> temporarily in code sections where it is not needed. Re-enabling the GC later will pick up all cyclic garbage created in the meantime.)</p></li>
  <li><p>"A cycle breaker is unnecessary because cycles are not that frequent and they can be easily avoided using <code>std::weak_ptr</code>." Cycles in fact turn up easily in many simple data structures - e.g. a tree where children have a back-pointer to the parent, or a doubly-linked list. In some cases, cycles between heterogenous objects in complex systems are formed only occasionally with certain patterns of data and are hard to predict and avoid. In some cases it is far from obvious which pointer to replace with the weak variant.</p></li>
  </ul>