News for hackers. Stuff that matters.
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.