3 ms·

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)?

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.

adrianratnapala 10y ago
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).
- nanolith 10y ago
  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.
  - gpderetta 10y ago
    hey, that's a generational GC :)
    - nanolith 10y ago
      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.
gpderetta 10y ago
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.
- johncolanduoni 10y ago
  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.
toast0 10y ago
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...

adrianratnapala 10y ago

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).

nanolith 10y ago
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.
- gpderetta 10y ago
  hey, that's a generational GC :)
  - nanolith 10y ago
    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.

gpderetta 10y ago

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.

johncolanduoni 10y ago
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.

toast0 10y ago

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...