Reclaiming C++ Data Structures with Cycles

https://www.justsoftwaresolutions.co.uk/cplusplus/reclaiming-data-structures-with-cycles.html

by criddell • 10 years ago

55 92 10 years ago

justsoftwaresolutions.co.uk

ingenter6• 10 years ago

I recently watched Herb Sutter's talk "Leak-Freedom in C++", described in the article [1], and I can't help but notice that C++ community has a strong bias against garbage collection. ... And then he describes the very problem you can't solve without GC: memory management for graphs with cycles. Solving this problem is equivalent to implementing GC. Of course, having your own specialized GC may help, but you may also benefit from your own memory allocation.

Why can't you acknowledge that there are problems that have GC as the only and best solution?

(Note: it's possible to mix memory management approaches, e.g only pointers to graph nodes are being garbage collected and everything else has a nice hierarchical ownership.)

[1] https://www.youtube.com/watch?v=JfmTagWcqoE

dmitrygr2• 10 years ago

Because GC wastes cycles on the user's machines instead of just hiring a competent developer who can manage memory properly. As we move to a more mobile world, wasted cycles matter more. So no. While GC is the definite answer to "how do I allow my dog to make a 'press this button for fart sound' app?" Is it most certainly not the definitive answer (though perhaps a passable one) to "how do I write good fast stable software?"

ingenter6• 10 years ago

You haven't answered my question. Please re-read it carefully.

johncolanduoni4• 10 years ago

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.

CJefferson• 10 years ago

My usual argument is as follows:

There are indeed cases where you have to use GC on some part of your program (as you say, some graph with cycles). However, such things are still only a small part of a program, and most of your memory allocations can still be handled without a GC.

No program language I am aware of (and I don't claim to know all) are good at saying "GC this 5%, I'll explicitly handle everything else". In C++ the "GC" bit is painful, in most other languages the "I'll do everything else" bit is painful.

Of course, there is an argument that just GCing everything is as efficient as bothering with manual memory management, so why bother at all? I'm still to be convinced about that, particularly because GC systems tend to want to use quite a bit more memory, so they have room to breathe.

ingenter6• 10 years ago

No program language I am aware of (and I don't claim to know all) are good at saying "GC this 5%, I'll explicitly handle everything else"

I haven't used rust in production, but I think it allows you to do precisely this, using the following crate: https://github.com/Manishearth/rust-gc.

Of course, there is an argument that just GCing everything is as efficient as bothering with manual memory management

I specifically said that it should be possible to mix GC with other types of memory management.

The problem is that I often hear from C++ crowd "GC is bad, mmkay!", without mentioning that there are specific cases where you have to use/implement GC.

pjmlp8• 10 years ago

Where to place a record (struct) in Modula-3:

    VAR
      stackOrGlobalMem: RECORD ... END;

      heapGC : REF RECORD ... END;

      somewhereManual : UNTRACED REF TO RECORD ... END;

      rawMem : ADDRESS;

Also valid for any other data type in the language.

So one can take advantage of GC productivity, while making use of C++ like features for manual allocation when required.

I remember reading a paper with a generics module for using smart references as well.

There are other not so well know GC enabled system programming languages with similar feature sets.

EDIT: like was missing

nadam• 10 years ago

You choose C++ to be able to control performance more than in lots of other languages. In a game engine or other very performance intensive software, people tend to think a lot about memory management. Whether in very rare cases, for a part of a system the optimal solution is something similar to a garbage collector: this might be possible, but quite irrelevant, because the important thing is not the final solution, but the fact that you can (sometimes quite creatively) control and constantly fine tune things, so that you can come up with an optimal solution.

winter_blue• 10 years ago

I don't know if I would acknowledge that there are problems that have GC as the only and best solution. Perhaps there are certain specific memory management problems for which a GC is the best solution. But what if you avoid that entire class of problems by adopting certain programming paradigms, or by the design of your programming language? For instance, Rust ensures memory safety without a GC. And while I write C++, I rarely find myself directly call new -- most of my objects are allocated by STL containers and via stack building.

johncolanduoni4• 10 years ago

Rust is horrifically bad at dealing with non-trivial cyclical structures for a number of reasons, not having a GC being one of them.

saucetenuto• 10 years ago

Right, but then you also shouldn't be using the techniques described in the article, right? To put it another way, there's no case where deferred collection with smart pointers is better than real GC.

jasode2• 10 years ago

I can't help but notice that C++ community has a strong bias against garbage collection. [...]
Why can't you acknowledge that there are problems that have GC as the only and best solution?

Your prelude and the followup question is not well-formed.

C++ programmers do not have a bias against GC as a specific problem-solving technique. In fact, expert C++ programmers can embrace GC so much that they can write an entire virtual machine[1] with GC and a DSL[2] for that vm that takes advantage of memory safety. Both the CLR vm and the (original) C# compiler were written by C++ programmers.

What the C++ community doesn't want is GC in the C++ base language itself or the standard runtime. That's a very different concept from a generalized "C++ bias against GC".

In other words, the following is unacceptable:

  std::string x = "Hello, " + fullname; // cpu cycles spent on GC

Those cpu cycles spent on constantly checking if "x" is no longer reachable is cpu power that's taken away from rendering frames of a 60fps game, or computing numeric equations or high speed quantitative trading. C++ programmers don't want GC as a global runtime that you can't opt out of. Also, global GC often requires 2x-3x the memory footprint of working memory which is extremely wasteful for the resource constrained domains that C++ is often used in.

Herb Sutter's presentation is compatible with "pseudo-GC-when-you-need-it" without adding GC to the entire C++ standard runtime.

[1]https://en.wikipedia.org/wiki/Common_Language_Runtime

[2]https://en.wikipedia.org/wiki/C_Sharp_(programming_language)

ingenter6• 10 years ago

Your prelude and the followup question is not well-formed.

Thank you for your feedback, I appreciate it.

C++ programmers do not have a bias against GC as a specific problem-solving technique. Expert C++ programmers can embrace GC

Please watch this portion of the video, and the way the speaker is pronouncing the word "collect":

https://www.youtube.com/watch?v=JfmTagWcqoE#t=1h5m25s

Regarding general-purpose GC:

I don't support using GC for everything. If there is a problem that can only be solved with GC, it doesn't mean that we should express our entire running programs in terms of dynamic cyclic graphs. I believe we can do much better, with much fewer resources.

adrianratnapala2• 10 years ago

There is an advantage to universal GC: it can simplify interfaces.

For example, in C every time a `const char *` appears in an API there has to be an implicit contract about who owns the string and how to free it. A language like Rust improves on this by enforcing such contracts, but the contracts still complicate every interface.

In a GC'd language you can just forget about these issues and just treat strings (and other immutable objects) almost as if they were ordinary fixed-sized values.

chrisseaton2• 10 years ago

I agree with you, but in this

std::string x = "Hello, " + fullname; // cpu cycles spent on GC

you are already spending cycles on memory management (if C++ allocates character data on the heap which I think it does). You are searching for free space in the heap, possibly synchronising to do that, and so on.

With a GC you may even use less cycles here! For example a copying GC could mean that you can allocate with a simple thread local bump pointer.

So in your statement you are already paying an unknown cycle cost for memory management. Why do you care if it's GC?

Your answer is probably the variance in the number of cycles - the noticeable pauses - which is a reasonable concern.

pjmlp8• 10 years ago

A GC API definition is already in the standard. It was added in C++11.

T-zex2• 10 years ago

Another aspect against GC is system determinism. Unmanaged runtime is more deterministic and is often faivored in real time applications.

pkolaczk3• 10 years ago

"Also, global GC often requires 2x-3x the memory footprint of working memory which is extremely wasteful for the resource constrained domains that C++ is often used in."

Memory fragmentation in manual memory management often comes at a similar or higher cost, which is often "forgotten" and neglected, because it is hidden:

https://bugzilla.mozilla.org/show_bug.cgi?id=666058#c31

And fragmentation may grow over time much more than the typical GC overhead. Then you have to do a "forced GC" that is restarting the application. Often happens to my phone or browser. I'm not sure if it is more due to fragmentation or more due too plain old memory leaks.

mannykannot• 10 years ago

I am not doubting that you are right, but this argument does not quite amount to a proof. That is because you would have to show that there are cases where the lifetimes of the graph's elements cannot be determined from consideration of the semantics of the problem.

wyldfire• 10 years ago

C++ community has a strong bias against garbage collection

Well, it's a bit of a selection bias on your part IMO. The people who use C++ have seen the benefits of Java, python, C# and all the rest. And many of them(us) use Java, python, C# and stuff for meta-productivity build tools and the like. GC is great for some enormous set of problem domains. But for problems that cannot endure high or unstable latencies, GC is a bad solution. I'm writing C++ because it hits a sweet spot in the intersection of (low/deterministic latency + ubiquity among developers).

Why can't you acknowledge that there are problems that have GC as the only and best solution?

There are, but I probably wouldn't have used C++ for them. In some rare cases I would but only because of momentum on an existing legacy solution.

kabdib• 10 years ago

I write C++. I write a lot of it, I've been using it since 1987.

I love LISP and Smalltalk, but I'll never ship a product in those languages. I've written a ton of C# and Java and somewhat less Javascript; those environments are fine (though I found myself paying much closer attention to object lifetime than I wanted).

I'm dead set against garbage collecting C++ because the semantics just don't fit well with the available runtimes. A few times I've written garbage collected heaps for specific types of objects; crossing the boundary between the hand-allocation world of C++ and the dynamic world of a GC environment is not a happy or particularly efficient experience, especially in the presence of threads.

vmarsy• 10 years ago

I think the reason the C++ community has a strong bias against garbage collection as you say is because it has a bias against all sort of unpredictable/unwanted behavior. That's the essence of c++: pay only for what you need/want/use. Garbage collection wouldn't be appropriate in some situations.

So re-implementing your own GC algorithm in the special case where you need it is seen as acceptable. That deffered pointer could be part of the standard library as long as those who don't need to use it don't pay any performance overhead

haberman2• 10 years ago

Why can't you acknowledge that there are problems that have GC as the only and best solution?

GC is traditionally bundled into a language runtime in a way that imposes global costs, and cannot be opted out of. The GC interrupts your program in a way you have no direct control over and scans the global heap of all objects you have ever created.

C++'s philosophy is zero-cost, opt-in abstractions. So naturally anything that you can't opt out of is going to rub C++ programmers the wrong way.

Implementing GC within the language, in a way that is entirely opt-in, is fine. Any muttering under the breath when discussing this is, IMO, just acknowledging that most of our experiences are of "bad" GC, to the point that we almost don't want to use the same word when referring to "good" GC.

titzer6• 10 years ago

C++'s philosophy is zero-cost, opt-in abstractions.

It's a nice philosophy, but unfortunately C++ itself often fails to deliver unless the programmer is an absolute expert on the underlying semantics. E.g. forget to pass a vector by reference or as a pointer, and you get a complete O(n) copy underneath. With other data structures, one can implement efficient copy constructors to make this pretty cheap. When an abstraction leaks details of the underlying implementation that then lead to huge non-obvious costs, that is not an abstraction.

Another example is that C++ heap allocation relies on an underlying allocator, which has overhead in managed chunks of memory, size classes, etc. The underlying allocator's alloc() and free() operations are not constant time. In fact, they are almost always outperformed by the allocation performance of GC'd languages, where bump-pointer allocation and generational collection make these overheads very, very cheap.

pjmlp8• 10 years ago

Having been part of the community, but with experience in many other languages another common trait seem to be ignoring that many other languages also have features for writing cache friendly code just like C++, while being safer.

A good example is Modula-3, a systems programing language that while it does have GC by default, also allows for global and stack allocation, value types, bit and structure packing and if really necessary naked pointers (only allowed in unsafe modules).

Or Mesa/Cedar at Xerox PARC with its mix of RC/GC, which is basically the same as C++ _ptr<>() + deferred_ptr<>() just implemented at the language level.

Same applies to RAII, yes it was a very good invention in C++, but many other languages do offer good ways of doing resource management, for example bracket in Haskell or withResource in others.

72deluxe• 10 years ago

Really fascinating article. I'm yet to look at the library and Herb's library too but great to have both.

The cppcon YouTube channel is full of videos that will take up my evenings, to my wife's disgust (doubt she wants to watch Bjarne talk).

radarsat12• 10 years ago

Such effort would be better spent on figuring out best practices for avoiding data structures with cycles in the first place.

putzdown3• 10 years ago

I think you've misunderstood the article. It's talking about the object dependency (pointer) graph, not data structures in a more general sense. The object dependency graph is intrinsically cyclical in the way the OP describes. There's no avoiding it.

radarsat12• 10 years ago

No need to be condescending.

The article talks duly about the data structure in question and is perfectly interesting. What it doesn't address is when this data structure comes up in practice and whether it can be handled in different ways.

In many cases, it might be desirable to search for alternative memory representations, since this data structure obviously complicates things considerably (for C++).

For example, a graph is isomorphic to a sparse array, which could avoid embedding bidirectional pointers directly into the graph nodes.

iainmerrick2• 10 years ago

The author's "internal_ptr" template seems exactly equivalent to Objective-C (and I assume Swift)'s weak references.

And that's great! Automatic reference counting is my single favourite thing about Obj-C. Once you get the hang of using weak refs for parent objects, ARC is very easy to use, with consistent speed, low memory usage, and immediate deallocation of dead objects.

I'd go as far as to say that Objective-C is a big reason why iOS has historically been faster and smoother than Android. It's not the world's fastest language, but there are no big GC pauses and it doesn't waste a lot of memory.

So I bet this is a good memory management style for C++ too.

putzdown3• 10 years ago

No, Obj-C/Swift use something more akin to C++'s `shared_ptr` and `weak_ptr`, as evidenced by the fact that cyclic references may result in memory leaks in each system. This is precisely the problem that `internal_ptr` seeks to resolve.

iainmerrick2• 10 years ago

Ahh, rereading more carefully, I think I see. You could have a chain of objects connected by internal pointers, and they'd all be kept alive as long as the first object is strongly referenced, but that wouldn't work for weak pointers.

putzdown3• 10 years ago

This is a very promising solution. If it has a fatal problem (I'm not sure it does), it would be the cost of searching back through the referrer chain to look for a root pointer. Am I wrong in thinking that that will be at least O(n), if not O(n^2)? And n could be extremely large—as large as the number of objects in your program.

To say it another way: what we (C++ programmers, stereotypically) don't like about GC is that it incurs long search costs at unpredictable intervals. That long search cost is not dissimilar in nature (i.e. in algorithm) to the cost of this search. So it's not clear to me that the performance characteristics of `internal_ptr` would be much different from those of GC. I'd like to see the performance characteristics of the solution filled out with more detail.

Reclaiming C++ Data Structures with Cycles

Related Stories