News for hackers. Stuff that matters.
Re:Reclaiming C++ Data Structures with Cycles by johncolanduoni on Thursday October 13, 2016 @08:53AM (#12700386)
How does a "good programmer" properly manage cyclical graphs without very specific, static guarantees about how they're used (e.g. All cycles are parent/child)? Because I'd love to know a way to do this without using/implementing the equivalent of a GC.
Re:Reclaiming C++ Data Structures with Cycles by gpderetta on Thursday October 13, 2016 @09:35AM (#12700634)
In addition to what adrianratnapala said, it is perfectly fine to have specialized GCs for specific problems, and I suspect that any moderately complex C++ program in fact does (and no, that's not Greenspuring). The problem is using GC as the general memory management solution when 95% of the allocated objects have a single reference or a simple lifetime patter.

A not well known fact is that even the linux kernel as a GC implementation, used to collect file descriptors, but any suggestion to GCing all memory in the linux kernel wouldn't be well received.

Re:Reclaiming C++ Data Structures with Cycles by johncolanduoni on Thursday October 13, 2016 @09:38AM (#12700656)
I completely agree, but the OP has been pretty clear in this thread that a GC is never the best solution and I'd like to know his alternative.
Re:Reclaiming C++ Data Structures with Cycles by adrianratnapala on Thursday October 13, 2016 @09:01AM (#12700431)
In most of the graph problems I have ever dealt with, the graph is constructed piecemeal but destroyed as a whole after you are finished with it.

It is true there are specific problems (e.g git repos) where you want a mutable graph over the long term -- but I have never actually had to deal with those cases, unless it was a special case with a obvious solution (like a doubly-linked list or tree).

Re:Reclaiming C++ Data Structures with Cycles by nanolith on Thursday October 13, 2016 @11:44AM (#12701504)
Even in the case of a mutable graph, one can use copy-on-write semantics to create a DAG of graph revisions that can be managed or compacted. I believe this was the strategy used by Subversion.

Compaction and collection can both be trivially performed on such a structure by making a deep copy of the latest revision of the graph to a new memory arena, just as is commonly done with a Cheney collector. Old locations are back-patched with pointers to the new locations, which solves the cycle problem.

Re:Reclaiming C++ Data Structures with Cycles by gpderetta on Thursday October 13, 2016 @12:09PM (#12701728)
hey, that's a generational GC :)
Re:Reclaiming C++ Data Structures with Cycles by nanolith on Thursday October 13, 2016 @12:35PM (#12701996)
Well, it's a Cheney GC. To be generational, there would need to be more than two heaps. But, that's hair splitting. Heh.

I doubt one would find many C++ folks who would disagree that GC is useful some of the time. It's all about controlling when and where GC is used, which sort of hits home with Sutter's point.

Re:Reclaiming C++ Data Structures with Cycles by toast0 on Thursday October 13, 2016 @11:15AM (#12701267)
What are people using cyclical graphs for? Most of my daily work is in a sad language which has GC and structurally prohibits cyclical references[1], so what am I missing out on?

[1] unless you cheat...