80

I recently watched a great talk by Herb Sutter about "Leak Free C++..." at CppCon 2016 where he talked about using smart pointers to implement RAII (Resource acquisition is initialization) - Concepts and how they solve most of the memory leaks issues.

Now I was wondering. If I strictly follow RAII rules, which seems to be a good thing, why would that be any different from having a garbage collector in C++? I know that with RAII the programmer is in full control of when the resources are freed again, but is that in any case beneficial to just having a garbage collector? Would it really be less efficient? I even heard that having a garbage collector can be more efficient, as it can free larger chunks of memory at a time instead of freeing small memory pieces all over the code.

Jiddoo
  • 1,091
  • 2
  • 9
  • 14
  • 27
    Deterministic resource management is critical in all sorts of cases, especially when you're dealing with unmanaged resources (e.g., file handles, databases, etc.). Besides that, garbage collection always has some sort of overhead, whereas RAII has no more overhead than writing the code correctly in the first place. "Freeing small memory pieces all over the code" is generally quite a bit more efficient, because it is much less disruptive to the running of the application. – Cody Gray - on strike Jun 02 '17 at 09:18
  • 3
    "why would that be any different from having a garbage collector in C++?" I remember Stroustrup saying in one of his talks (not literally): "C++ is garbage collected, because it has RAII". – 463035818_is_not_an_ai Jun 02 '17 at 09:21
  • 4
    @CodyGray While "Freeing small memory pieces all over the code" might be more efficient from a runtime-perfomance perspective, it isn't from a memory efficiency perspective as it leads to more fragmentation. – Some programmer dude Jun 02 '17 at 09:21
  • 2
    There are plenty of memory-management strategies that minimize fragmentation without requiring garbage collection. – Cody Gray - on strike Jun 02 '17 at 09:23
  • 1
    Strongly related question: https://stackoverflow.com/questions/147130/why-doesnt-c-have-a-garbage-collector – Cody Gray - on strike Jun 02 '17 at 09:24
  • 35
    Note: You talk about _resources_, but there is more than one kind of resource. A garbage collector gets called when it's time to free up some memory, but it will not be called when it's time to close files. – Solomon Slow Jun 02 '17 at 13:05
  • 24
    anything is better than garbage collection – GuidoG Jun 02 '17 at 15:39
  • 2
    RAII can help avoid leaks, but it doesn't in itself prevent use-after-free, which a GC generally can. – Veedrac Jun 02 '17 at 17:27
  • 3
    RAII due to it's deterministic nature allows you to use destructors, OTOH with GC there is no point in it since you don't know *when* it happens – Xeverous Jun 02 '17 at 17:45
  • 1
    Herb Sutter's own [`deferred_ptr`](https://github.com/hsutter/gcpp) uses smart pointers to provide a convenient interface to garbage collection. It's called `deferred_ptr` because destructors are deferred until you ask for a collection (so they still happen at a predictable time). – Jeffrey Bosboom Jun 02 '17 at 19:30
  • 3
    @CodyGray a GC can actually be more efficient. Instead having to free small bits of memory and looking up which small bits can be allocated again (memory fragmentation) a GC can simply copy the few live objects and mark a huge amount of memory as free at once. Since most of times programs make many small short-lived objects, this can be very beneficial. – Patrick Huizinga Jun 02 '17 at 23:12
  • 1
    @Xeverous you can still have destructors with a GC. In fact C# has them. But they're only supposed to be a stopgap in the case a resource was not properly closed. As you said, it's not deterministic, but that doesn't make it useless. – Patrick Huizinga Jun 02 '17 at 23:15
  • 4
    @PatrickHuizinga Java programs certainly allocate many small short-lived objects (simply because it's hard to do much of anything in Java without allocating), but I'm not sure C++ programs do the same, because C++ allows allocating on the stack instead (including `boost::container::small_vector` and similar). I'd be interested to see a source, if you have one. – Jeffrey Bosboom Jun 03 '17 at 01:08
  • 12
    @Veedrac If you're fully committed to RAII and use smart pointers everywhere, you shouldn't have use-after-free errors either. But even if GC (or ref-counted smart pointers) would have saved you from use-after-free errors, it could be masking a scenario where you've unwittingly kept references to resources longer than you expected. – jamesdlin Jun 03 '17 at 01:14
  • 4
    @PatrickHuizinga: I call BS on this [like I did at someone else who said the same thing I debunked on CS.SE](https://cs.stackexchange.com/questions/71979#comment154244_71979). If you have a legit example to prove that, show it. As far as I can tell, it's an urban myth that just won't die, because people so desperately *want* it to be true. – user541686 Jun 03 '17 at 09:12
  • 2
    Different meanings of efficiency. I specifically argued that the RAII style is "less disruptive to the running of the application". Garbage collection has to stop the program's execution in order to do all of that marking and freeing at once, which is very disruptive. Now, I suppose you can claim that concurrent garbage collectors exist, but they aren't very popular in the wild, and also significantly limit the throughput. I'm open to someone actually showing a benchmark that proves deterministic destruction is less efficient than GC, but I haven't seen one yet. Quite the opposite. @patrick – Cody Gray - on strike Jun 03 '17 at 10:56
  • 2
    You just don't have problems like [this](https://stackoverflow.com/questions/2484079/how-can-i-avoid-garbage-collection-delays-in-java-games-best-practices) in languages that implement RAII without garbage collection. Naturally there are workarounds, as there are for any problem, but you're going to have a hard time telling that guy that garbage collection increased the efficiency of his app. Or of his workflow, in having to work around it by basically *not creating objects*. And this myth about GC being the only way to avoid fragmentation needs to die, too. Write a better memory manager. – Cody Gray - on strike Jun 03 '17 at 11:02
  • 1
    @jamesdlin Doesn't help squat with non-owning references. – Veedrac Jun 03 '17 at 11:38
  • 1
    @Mehrdad It's pretty easy to show that GCs have higher throughput than `malloc`/`free`; allocate a bunch of things on the heap and throw them away. What's harder is showing a case where that matters. GC'd languages tend to allocate pathologically large amounts of stuff, which is why they need a GC, but lower-level languages don't, so the throughput of allocations doesn't matter that much to them. – Veedrac Jun 03 '17 at 11:46
  • 3
    @Veedrac: Uh, no. If you just alloc/dealloc a bunch, then all you measure is how good your heap implementation is at dealing with an unrealistically dumb allocation pattern, not anything indicating the actual difference between manual & GC. **But** I just tried that on my computer (Windows) and MSVC took 1328 and 675 ms to do allocate and deallocate, VC# took 2375 and 0 ms, & GCC took 2421 and 2032 ms. If we *could* draw a conclusion from this, you'd *still* be wrong. So, again: show me **code** (not English) that *legitly* (i.e. scientifically) demonstrates the *strongest* claim you can make. – user541686 Jun 03 '17 at 12:14
  • 1
    @Mehrdad https://gist.github.com/Veedrac/a3f0d6a0b1a2a64a28ac6da4637ae59d – Veedrac Jun 03 '17 at 13:14
  • 3
    @Veedrac about use-after-free: a GC trades an immediate crash in debug mode for a silent memory leak and phantom objects. One symptom may be better than the other depending on the case, but still the bug isn't solved. – Quentin Jun 03 '17 at 14:37
  • 1
    @Quentin Use-after-frees break your code when you destroy an object *before* the last use. Leaks cause transient inefficiency when you destroy an object too long *after* the last use. These are disjoint problems, and fixing one doesn't introduce the other. Also note that RAII doesn't actually fix leaks, it just tidies them up a little. If a GC is holding onto an object for too long, other than just the GC collection latency, the equivalent owning RAII pointer would *also* still be holding onto that object. Also note that use-after-frees in C++ rarely cause clean crashes, even in debug. – Veedrac Jun 03 '17 at 15:03
  • 1
    @Veedrac That was unclear, my bad. I'm talking about the class of bugs where an object A references and use an object B when it shouldn't anymore, because B is supposed to be dead. RAII (or manual management for that matter) will kill B and leave A with a clearly invalid pointer that can be detected on its next use (either via segfault, or with tools such as valgrind). A GC will keep B alive as long as A lives. In most cases the only symptom apart from the leak is that A retrieves outdated data from B, which might be really hard to pin down. – Quentin Jun 03 '17 at 15:13
  • 1
    @Veedrac (cont.) so choosing the symptom that will be the easiest to debug makes sense, but neither RAII nor a GC can fix the underlying bug, which is a progam logic issue (correctly notifying A that B should be dead now). – Quentin Jun 03 '17 at 15:15
  • 1
    @Quentin That seems like a really odd way of viewing things. Something is supposed to be alive if you're going to use it, not the other way around. Whilst exceptions exist, I would posit that they're a small minority. – Veedrac Jun 03 '17 at 15:17
  • 3
    @Veedrac It's really just another way to formulate the logic you need to implement. "At this point B must die, period" is a perfectly sane design requirement. It comes up all the time in game development: for example B is an enemy you've just killed, and A is a homing missile still in flight towards B. Let's say that you forget to notify A, that's a bug. If you forcefully kill B, the game will crash on the next frame. If B is kept alive by a GC, the missile will now orbit around an invisible, intangible enemy because no one else than A knows that it's actually still alive. – Quentin Jun 03 '17 at 15:28
  • 1
    @Quentin A (sensible) game won't implement such logic with destructors because everything will be in arrays referencing other arrays. Trying to "forcefully kill" B through memory management simply doesn't scale, and even if it was possible it certainly wouldn't give you a clean crash. You have to handle this stuff when you're iterating through the array of missiles, and that means you need to set some kind of killed flag on `B`, which if anything means `B` needs to still be valid memory! – Veedrac Jun 03 '17 at 15:38
  • 2
    @Veedrac That's just an example of when an immediate object death is required. There are plenty ways to implement this behaviour, and direct notifying might actually be interesting in some cases (live-flags and two-pass destruction are another popular implementation indeed). But my point is: if you use an object after its intended lifetime, then either you've written a bug(forgetting to notify A), or you underestimated the lifetime requirements when designing (wait, B must live one more frame for everyone to witness its death). A GC won't solve that, it will just change the symptom. – Quentin Jun 03 '17 at 16:20
  • 1
    @Quentin *Or*, most likely, you just destroyed it too early. Trivially easy to do in C++. – Veedrac Jun 03 '17 at 17:35
  • 1
    @Veedrac Weak pointers help squat with non-owning references. – jamesdlin Jun 03 '17 at 18:00
  • 1
    @jamesdlin There are a whole bunch of problems with using weak pointers this way. Not only is it ungodly slow, but it's semantically completely wrong. Weak pointers provide for the case where the referenced data disappears; they make you handle the case where you get a sudden use-after-free, but they don't stop the use-after-free happening. (Even if they did, C++ uses non-owning references far too liberally for that to help.) To fix that in an RAII system you need something like Rust's borrow checker, though that comes with its own downsides. – Veedrac Jun 03 '17 at 18:09
  • 1
    @Veedrac: OK, this is better (Java is 10x "faster"). But again: it's still awful. Again, same issue: you're benchmarking the heap implementation, not GC vs. manual memory management. For example, I tried running your code with a simple heap that recycles nodes instead of de-allocating and re-allocating them (just make a vector and overload `Tree::operator {new,delete}`), and Java went from 10x faster to 3x faster. I'm not going to waste time on the rest of the bottleneck, but it's clearly in the allocation functions, which I can optimize too. (cont'd) – user541686 Jun 03 '17 at 22:03
  • 1
    @Veedrac: And before you jump on me and say I cheated, note that Java is not even deallocating anything at all, so your comparison is already unfair, and I'm only making it more fair. (I tell it `System.gc()` before making the timing measurements, but I don't see the memory returned to the system at all.) That said, even if it *did* return the memory at that point, this would only prove their heap implementation is well-tuned for the case where the GC doesn't even need to run. It hardly says anything like e.g. allowing a GC to coalesce deallocations makes it faster than manual deallocations. – user541686 Jun 03 '17 at 22:05
  • @Mehrdad You're arguing against a point I didn't make. There's nothing unfair about the comparison I made as long as you don't assume I said something I didn't. – Veedrac Jun 03 '17 at 22:13
  • 7
    @Veedrac: Of *course* it's unfair. You gave me two programs to compare, one that frees memory, one that doesn't. To do a fair comparison you need to run a realistic workload that actually requires the GC to, you know, kick in. Not sit idling. And you need to have a dynamic and realistic memory allocation pattern, not FIFO or LIFO or some variation of that. It's not exactly mindblowing to claim that a program that never deallocates memory is faster than one that does, or that a heap tuned for LIFO deallocations will be faster than one that isn't. Well, duh, of course it would be. – user541686 Jun 03 '17 at 22:16
  • @Mehrdad Your criticisms make no sense. Running `System.gc(); System.runFinalization();` takes almost no time (obvious if you understand how GCs work) and frees all the junk "allocation". GCs are even better at freeing memory fast than they are at allocating memory fast. A "realistic" but equally heavy allocation pattern is just going to exacerbate this issue (also obvious if you understand how GCs work) because compacting GCs handle fragmentation *far* better than `malloc`/`free`, and their tiered deallocations are designed precisely for such workloads. – Veedrac Jun 03 '17 at 23:02
  • @Mehrdad You asked for evidence of my claim and I showed you evidence. You're being needlessly defensive of your preconceptions rather than just accepting this point and moving on to something more productive, like, you know, an argument that matters. – Veedrac Jun 03 '17 at 23:03
  • 1
    @Veedrac: "Instead of just accepting" *what point*? The point that a program with a GC that *never even runs* (equivalently, a program with a *disabled GC*) will be faster than one that manually frees its memory? Yeah, it is. A system that doesn't even need to do its job *will* be faster than one that does. Definitely a very valid argument, and you *totally blew my mind* right there by just how elegantly you proved GCs can be faster than manual memory management. Very scientific, brilliant, realistic, and all-around well-done indeed. – user541686 Jun 03 '17 at 23:28
  • @Mehrdad Again, you're not disagreeing with the point I made. I wasn't intending on blowing your mind, I was just trying to justify a fairly obvious, uncontroversial claim that basically everyone agrees with. Why is this a problem? – Veedrac Jun 03 '17 at 23:29
  • 1
    @Veedrac: "Why is this a problem"? The discussion is about GC vs. manual memory management, you show me a program where the GC doesn't even *free any memory*, and you're asking me "why is this a problem"? Well if that's your game, then stop freeing the memory in the manual version too, and *then* compare. Why is this a problem?! – user541686 Jun 03 '17 at 23:32
  • @Mehrdad I showed you exactly how to make sure a GC routine runs before the program ends. It (obviously) makes almost *zero* difference to the results. – Veedrac Jun 03 '17 at 23:33
  • 1
    @Veedrac: [And *I* already told you **exactly**](https://stackoverflow.com/questions/44325085/raii-vs-garbage-collector?noredirect=1#comment75700354_44325085) that the GC **refused** to free any memory even though I ran it. You just don't read apparently. But hell, even if it that *did* trigger it, it would be freeing **all** the memory it allocated in 1 shot, i.e. the objects wold all be dying in the first generation, i.e. the garbage collection is artificially at 100% efficiency, i.e. a totally unrealistic scenario except maybe in *your* world. Yeah, you're totally compelling. – user541686 Jun 03 '17 at 23:42
  • @Mehrdad That's just you not understanding how memory works. Allocators don't return memory to the system, they return it to their free pools. `malloc`/`free` normally work *exactly* the same. You should be using `Runtime runtime = Runtime.getRuntime(); System.out.println("Used Memory:" + (runtime.totalMemory() - runtime.freeMemory()));` or somesuch to measure actual memory use. – Veedrac Jun 03 '17 at 23:44
  • @Veedrac: No, it's more like *you* not understanding how memory works. `malloc`/`free` most definitely do NOT work exactly the same. Check your task manager. They're doing a **hell** of a lot more work than merely making the memory available to the *program*; they're returning the freed memory to the entire rest of the *operating system*. If you make an apples-to-apples comparison for that like I did above via node recycling, you'll get proportionally better performance, like I already said above. If comparing apples to oranges is your way though then I don't know what to tell you. – user541686 Jun 03 '17 at 23:46
  • @Mehrdad I'm done here. – Veedrac Jun 03 '17 at 23:46
  • @Veedrac I don't see how you're guessing that a use-after-free bug is "most likely" an object that died early and not a reference kept for too long, since both classes of bugs exist. But I've made my point, so I won't clutter this comment thread further. – Quentin Jun 04 '17 at 14:18
  • 1
    @Quentin My default assumption is that if I use a pointer it's because I want what that pointer points to, not that I use a pointer because I have it. – Veedrac Jun 04 '17 at 16:00

12 Answers12

67

If I strictly follow RAII rules, which seems to be a good thing, why would that be any different from having a garbage collector in C++?

While both deal with allocations, they do so in completely different manners. If you are reffering to a GC like the one in Java, that adds its own overhead, removes some of the determinism from the resource release process and handles circular references.

You can implement GC though for particular cases, with much different performance characteristics. I implemented one once for closing socket connections, in a high-performance/high-throughput server (just calling the socket close API took too long and borked the throughput performance). This involved no memory, but network connections, and no cyclic dependency handling.

I know that with RAII the programmer is in full control of when the resources are freed again, but is that in any case beneficial to just having a garbage collector?

This determinism is a feature that GC simply doesn't allow. Sometimes you want to be able to know that after some point, a cleanup operation has been performed (deleting a temporary file, closing a network connection, etc).

In such cases GC doesn't cut it which is the reason in C# (for example) you have the IDisposable interface.

I even heard that having a garbage collector can be more efficient, as it can free larger chunks of memory at a time instead of freeing small memory pieces all over the code.

Can be ... depends on the implementation.

Daniel Kamil Kozar
  • 18,476
  • 5
  • 50
  • 64
utnapistim
  • 26,809
  • 3
  • 46
  • 82
  • 8
    Note that there are also algorithms that rely on a GC and cannot implemented using RAII. For example some concurrent lock-free algorithms where you have multiple threads racing to publish some data. E.g. there is for the best of my knowledge no C++ implementation of [Cliff's non-blocking hashmap](https://github.com/boundary/high-scale-lib). – Voo Jun 02 '17 at 13:31
  • 3
    *adds it's own overhead* - otoh you're not paying costs for malloc and free. you're basically trading free list management and reference counting for liveness scanning. – the8472 Jun 02 '17 at 14:14
  • Also, you could use a combination of both. In such a case, you could use RAII smart pointer to return the memory to your memory pool rather than delete it altogether. The flexibility with RAII smart pointers is that you can really choose what works best for you rather than being forced to use or the other. – Andrew Jun 02 '17 at 16:52
  • 1
    Yeah "adds its own overhead" can be highly misleading. If your RAII-based program allocates lots of small short-lived objects and/or uses a lot of `shared_ptr` equivalents, a modern GC will utterly trounce it unless you do a *lot* of work replacing the default allocation strategies. (That's time you could be spending doing something useful.) RAII is only going to win for performance *if* you actually write in a way that benefits from it. – Alex Celeste Jun 02 '17 at 18:25
  • 1
    Minor quibble: `IDisposable` is .NET, not C# – Mathieu Guindon Jun 02 '17 at 19:11
  • 6
    GC in Java and .NET is *only* about releasing the memory still allocated by unreachable objects. This is not fully deterministic, however, resources such as file handles and network connections are closed through a completely different mechanism (in Java, the `java.io.Closeable` interface and "try-with-resources" blocks), which *is* fully deterministic. So, the part of the answer about the determinism of a "cleanup operation" is wrong. – Rogério Jun 02 '17 at 19:26
  • Side note, although it isnt perfect, garbage collection management can be forced, as with [object].dispose() and gc.collect() in .Net, although its poor practice to use this when Idisposable is available. – kingfrito_5005 Jun 02 '17 at 20:33
  • 3
    @Voo in that case you could argue it's not actually lock-free because the garbage collector is doing the locking for you. – user253751 Jun 02 '17 at 23:31
  • @immibis I see where you're coming from, but if we went with that definition no algorithm would be lock free on modern OSes since there's at least the thread scheduler lock. – Voo Jun 02 '17 at 23:44
  • 2
    @Voo Does your algorithm *rely* on the thread scheduler using a lock? – user253751 Jun 03 '17 at 03:30
  • 1
    I like how people are saying if you assign a variable value 0 in RAII, it's value will be 0. – Abhinav Gauniyal Jun 03 '17 at 04:43
  • Garbage Collection can be both cheaper and more expensive than RAII. RAII has the advantage of knowing which resource is going out of scope, garbage collection must potentially examine many used references to be able to collect a few unused. If you have an application where you have no state, or you have an application with long lived state, garbage collection algorithms are usually good at this. If your application have state that mutates gradually, depending e.g. 10000 users interacting, you can get a large number of "potential garbage references", and they can be very expensive. – Jesper Madsen Jun 03 '17 at 08:35
  • @immibis As much as it relies on the GC being lock-free (which is absolutely not the same as "having a lock"). Thinking on that level just doesn't give us useful information about algorithms. Hell there are lock-free GC algorithms out there if you really wanted. – Voo Jun 04 '17 at 10:20
  • What's worth mentioning is that, depending on the GC implementation, the time needed for cleanup is not deterministic. If I have to develop a high performance low latency application (e.g. a game with 16 ms per frame), a random collection cycle that stops execution of my code for 100+ ms is not acceptable. Manual memory management (whether through RAII or not) lets me have much more control over this. – hoffmale Jun 04 '17 at 16:34
  • @Voo Well then combining a lock-free GC into your lock-free GC-relying hashtable should give you a lock-free hashtable that doesn't rely on external GC. Whether anyone would bother to do that is a different story. – user253751 Jun 05 '17 at 11:07
  • @immibis And then it would still not be lock free thanks to the scheduler lock which is why that is just not a very useful level to think about for most algorithms. We just rely on the ambition that both scheduler and GC don't acquire any other locks (no deadlocks) and that the latency they introduce is acceptable. The second assumption does not hold on all cases in which case one needs to rethink the choice of language and possibly OS. – Voo Jun 05 '17 at 17:41
  • You can always (at least theoretically) run your code on a system without a scheduler, but if it relies on the GC, you can't just run it on a system without a GC unless it also has infinite memory. – user253751 Jun 06 '17 at 08:22
39

Garbage collection solves certain classes of resource problems that RAII cannot solve. Basically, it boils down to circular dependencies where you do not identify the cycle before hand.

This gives it two advantages. First, there are going to be certain types of problem that RAII cannot solve. These are, in my experience, rare.

The bigger one is that it lets the programmer be lazy and not care about memory resource lifetimes and certain other resources you don't mind delayed cleanup on. When you don't have to care about certain kinds of problems, you can care more about other problems. This lets you focus on the parts of your problem you want to focus on.

The downside is that without RAII, managing resources whose lifetime you want constrained is hard. GC languages basically reduce you to either having extremely simple scope-bound lifetimes or require you to do resource management manually, like in C, with manually stating you are done with a resource. Their object lifetime system is strongly tied to GC, and doesn't work well for tight lifetime management of large complex (yet cycle-free) systems.

To be fair, resource management in C++ takes a lot of work to do properly in such large complex (yet cycle-free) systems. C# and similar languages just make it a touch harder, in exchange they make the easy case easy.

Most GC implementations also forces non-locality full fledged classes; creating contiguous buffers of general objects, or composing general objects into one larger object, is not something that most GC implementations make easy. On the other hand, C# permits you to create value type structs with somewhat limited capabilities. In the current era of CPU architecture, cache friendliness is key, and the lack of locality GC forces is a heavy burden. As these languages have a bytecode runtime for the most part, in theory the JIT environment could move commonly used data together, but more often than not you just get a uniform performance loss due to frequent cache misses compared to C++.

The last problem with GC is that deallocation is indeterminate, and can sometimes cause performance problems. Modern GCs make this less of a problem than it has been in the past.

Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • 2
    I'm not sure I understand your argument about locality. Most of modern GCs in mature environments (Java, .Net) perform compaction and create new objects from a continuous chunks of memory assigned to each thread. So I expect that objects created around the same time will be relatively local. AFAIK there is nothing like this in standard `malloc` implementations. Such logic might result in a false sharing which is an issue for multithread environment but it is a different story. In C you can do explicit tricks to improve locality but if you don't do that I expect GC to be better. What do I miss? – SergGr Jun 02 '17 at 19:21
  • 8
    @SergGr I can create a contiguous array of non-plain-old-data objects in C++ and iterate them in order. I can move them around explicitly so they are next to each other. When I iterate over a contigous container of values, they are guaranteed to be located sequentially in memrory. Node base containers lack this guarantee, and gc langauges uniformly support only node based containers (at best, you have a contiguous buffer of reference, not of objects). With some work in C++, I can even do this with runtime polymorphic values (virtual methods etc). – Yakk - Adam Nevraumont Jun 02 '17 at 19:40
  • 2
    Yakk, it looks like you are saying that non-GC world _allows_ you to fight for locality and achieve better results than GC world. But this is only a half of the story because by default you probably will get worse results than in GC world. It is actually `malloc` that forces non-locality that you have to fight against rather than GC and thus I think that claim in your answer that "_Most GC implementations also forces non-locality_" is not really true. – SergGr Jun 02 '17 at 19:43
  • "Their object lifetime system is strongly tied to GC": if this refers to resources such as file handles and network connections, it's plain wrong. Said resources are not managed through GC in languages like Java and C#, but through perfectly predictable and "tight lifetime" "Closeable" mechanisms. Also the part about non-contiguous memory is wrong - GC in Java, at least, is very smart, and there are Java APIs for direct memory allocation. – Rogério Jun 02 '17 at 19:46
  • One more thing, claim that "_gc langauges uniformly support only node based containers (at best, you have a contiguous buffer of reference, not of objects)_" is also not true. For example, in .Net/C# you can create a continuous buffer of `struct` i.e. of [value type](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/value-types) – SergGr Jun 02 '17 at 19:47
  • 2
    @Rogério Yes, that is what I call restricted scope based or C-style object lifetime management. Where you are manually defining when your object lifetime ends, or doing so with a simple scope case. – Yakk - Adam Nevraumont Jun 02 '17 at 19:48
  • @SergGr Sorry, only node based containers of non-data type. I'll fix that. – Yakk - Adam Nevraumont Jun 02 '17 at 19:49
  • @Yakk, again I don't get your point. `struct` in .Net is a valid data type. And array of `struct` is allocated in memory as a continuous chunk of all fields of `struct` rather than just pointers. – SergGr Jun 02 '17 at 19:51
  • Languages using GCs *can* support array-of-structs too. Golang does for example. Java is planning to. So this is more of a language limitation than a limitation of GCed environments. – the8472 Jun 03 '17 at 03:21
  • 4
    Sorry, but no, a programmer cannot be "lazy" and "not care" about memory resource lifetimes. If you have a `FooWidgetManager` that manages your `Foo` objects, it very likely stores registered `Foo`'s in an indefinitely growing _data structure_. Such a "registered `Foo`" object is beyond the reach of your GC, because `FooWidgetManager`'s internal list or whatever _holds a reference to it_. To release this memory, you need to ask `FooWidgetManager` to unregister that object. If you forget, this is essentially "new without delete"; only the names have changed... and the GC _can't fix it_. – H Walters Jun 03 '17 at 07:52
  • @HWalters: In the common scenario where an immutable object is used as a proxy for the data contained therein (e.g. the string "Fred"), and where code would have no reason to know or care when the last reference to a particular object goes away or gets overwritten, the cost of having an object track all references that exist to it may significantly exceed the cost of periodically identifying all objects to which any direct or indirect references exist. Note that in some relocating collectors, references may be the only evidence of objects' existence. If 5,000 objects are created... – supercat Jun 04 '17 at 21:15
  • ...on the young-object heap before it gets full, but by the time the GC is triggered references exist to only 100 of them, the system may copy the 100 referenced objects to a new location and then treat the young-object heap as empty space without having to perform any action whatsoever on the 4,900 objects that had ceased to exist. – supercat Jun 04 '17 at 21:18
  • @HWalters that sounds like a reason *not* to have `FooWidgetManager`, or at least not have it hold references to `Foo`s – Caleth May 23 '18 at 08:16
14

Notice that RAII is a programming idiom, while GC is a memory management technique. So we are comparing apples with oranges.

But we can restrict RAII to its memory management aspects only and compare that to GC techniques.

The main difference between so called RAII based memory management techniques (which really means reference counting, at least when you consider memory resources and ignore the other ones such as files) and genuine garbage collection techniques is the handling of circular references (for cyclic graphs).

With reference counting, you need to code specially for them (using weak references or other stuff).

In many useful cases (think of std::vector<std::map<std::string,int>>) the reference counting is implicit (since it can only be 0 or 1) and is practically omitted, but the contructor and destructor functions (essential to RAII) behave as if there was a reference counting bit (which is practically absent). In std::shared_ptr there is a genuine reference counter. But memory is still implicitly manually managed (with new and delete triggered inside constructors and destructors), but that "implicit" delete (in destructors) gives the illusion of automatic memory management. However, calls to new and delete still happen (and they cost time).

BTW the GC implementation may (and often does) handle circularity in some special way, but you leave that burden to the GC (e.g. read about the Cheney's algorithm).

Some GC algorithms (notably generational copying garbage collector) don't bother releasing memory for individual objects, it is release en masse after the copy. In practice the Ocaml GC (or the SBCL one) can be faster than a genuine C++ RAII programming style (for some, not all, kind of algorithms).

Some GC provide finalization (mostly used to manage non-memory external resources like files), but you'll rarely use it (since most values consume only memory resources). The disadvantage is that finalization does not offer any timing guarantee. Practically speaking, a program using finalization is using it as a last resort (e.g. closing of files should still happen more or less explicitly outside of finalization, and also with them).

You still can have memory leaks with GC (and also with RAII, at least when used improperly), e.g. when a value is kept in some variable or some field but will never be used in the future. They just happen less often.

I recommend reading the garbage collection handbook.

In your C++ code, you might use Boehm's GC or Ravenbrook's MPS or code your own tracing garbage collector. Of course using a GC is a tradeoff (there are some inconvenience, e.g. non-determinism, lack of timing guarantees, etc...).

I don't think that RAII is the ultimate way of dealing with memory in all cases. In several occasions, coding your program in a genuinely and efficiently GC implementations (think of Ocaml or SBCL) can be simpler (to develop) and faster (to execute) than coding it with fancy RAII style in C++17. In other cases it is not. YMMV.

As an example, if you code a Scheme interpreter in C++17 with the fanciest RAII style, you would still need to code (or use) a explicit GC inside it (because a Scheme heap has circularities). And most proof assistants are coded in GC-ed languages, often functional ones, (the only one I know which is coded in C++ is Lean) for good reasons.

BTW, I'm interested in finding such a C++17 implementation of Scheme (but less interested in coding it myself), preferably with some multi-threading ability.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
  • 16
    RAII doesn't mean reference counting, that's just std::shared_ptr. In C++ the compiler inserts calls to the destructor when it has proof that variables can no longer be reached, ie. when the variable goes out of scope. – csiz Jun 02 '17 at 11:35
  • But that mechanism is precisely the basis of reference counting in C++ – Basile Starynkevitch Jun 02 '17 at 12:10
  • 6
    @BasileStarynkevitch most RAII doesn't reference count, because the count would only ever be 1 – Caleth Jun 02 '17 at 12:51
  • Yes, but when you have cyclic pointers you need to do something special – Basile Starynkevitch Jun 02 '17 at 12:51
  • 4
    RAII is absolutely not reference counting. – Jack Aidley Jun 02 '17 at 16:28
  • 1
    @csiz, @JackAidley, I think you misunderstood Basile's point. What he says is that any reference-counting-like implementation (even such a simple as `shared_ptr` which doesn't have an explicit counter) will have troubles with handling scenarios that involve circular references. If you are talking only about simple cases where a resource is used only inside single method, you don't need even `shared_ptr` but this is only very limited subspace for which GC-based world also uses similar means such as C# `using` or Java `try-with-resources`. But the real world has also more complicated scenarios. – SergGr Jun 02 '17 at 19:31
  • @SergGr: The OP is asking about RAII, not about "any reference-counting-like implementation". Basile Starynkevitch claims that the former implies the latter, and his entire answer is contingent on that claim. csiz and Jack Aidley's objection is therefore completely on-point. (You may agree with Basile and disagree with csiz and Jack, but I think it's clear that they *understand* perfectly.) – ruakh Jun 02 '17 at 21:02
  • @ruakh, I (and probably Basile) say that in scenarios more complicated than resource in the scope of a single function RAII does in practice imply reference counting and thus all the issues with circular references. If you don't agree, I'd be very interested to find more details about other possible implementation of RAII that works beyond single function (i.e. stack-based) scope. For example, something that would work in asynchronous scenarios. P.S. explicit mentioning of "smart pointers" in the OP question implies that he treats RAII as something more than just stack-based case. – SergGr Jun 02 '17 at 21:29
  • 1
    @SergGr: If you disagree with someone, I think it's more productive to say so outright, rather than to say that they must simply be misunderstanding the point. As for the rest of your comment . . . `unique_ptr` is a "smart pointer", and is an "implementation of RAII that works beyond single function (i.e. stack-based) scope". C++ programmers generally consider it a best practice for resources to have clear and unique owners, and therefore to use `unique_ptr` rather than `shared_ptr`. – ruakh Jun 02 '17 at 22:32
  • @ruakh, I disagree with you ☺ that from csiz and Jack comments it is clear that they didn't misread the question and the answer. OP's question clearly uses term "RAII" in a broader sense than just "stack-based RAII". As for `unique_ptr`, could you tell me how it is better than `shared_ptr` in terms of dealing with complex object graphs that involve circular references? I definitely can't see it. Assume I'm designing ORM that should support bidirectional parent-child relationships. How could I use `unique_ptr` to let me own objects graph by holding a pointer to either parent or child object? – SergGr Jun 02 '17 at 23:13
  • 3
    @SergGr: Who ever said that `unique_ptr` handles circular references? This answer explicitly claims that "so called RAII techniques" "really means reference counting". We can (and I do) reject that claim -- and therefore dispute much of this answer (both in terms of accuracy and in terms of relevance) -- without necessarily rejecting every single claim in this answer. (Incidentally, there exist real-world garbage collectors that don't handle circular references, either.) – ruakh Jun 02 '17 at 23:37
  • 1
    @ruakh, personally I can't see why you treat `unique_ptr` as non-reference-counting approach. To me it is exactly reference counting with an additional API-enforced limitation that reference count is always either 1 or 0 and this is the reason it inherits all the limitations of reference counting. – SergGr Jun 03 '17 at 09:45
  • @SergGr: this question asks, among other things, about efficiency. Saying that RAII == reference counting implies that RAII always pays the full efficiency price of reference counting, which is not true. – ninjalj Jun 04 '17 at 11:13
14

RAII and GC solve problems in completely different directions. They are completely different, despite what some would say.

Both address the issue that managing resources is hard. Garbage Collection solves it by making it so that the developer doesn't need to pay as much attention to managing those resources. RAII solves it by making it easier for developers to pay attention to their resource management. Anyone who says they do the same thing has something to sell you.

If you look at recent trends in languages, you're seeing both approaches being used in the same language because, frankly, you really need both sides of the puzzle. You're seeing lots of languages which use garbage collection of sorts so that you don't have to pay attention to most objects, and those languages also offer RAII solutions (such as python's with operator) for the times you really want to pay attention to them.

  • C++ offers RAII through constructors/destructors and GC through shared_ptr (If I may make the argument that refcounting and GC are in the same class of solutions because they're both designed to help you not need to pay attention to lifespan)
  • Python offers RAII through with and GC through a refcounting system plus a garbage collector
  • C# offers RAII through IDisposable and using and GC through a generational garbage collector

The patterns are cropping up in every language.

Cort Ammon
  • 10,221
  • 31
  • 45
11

One of the problem about garbage collectors is that it's hard to predict program performance.

With RAII you know that in exact time resource will go out of scope you will clear some memory and it will take some time. But if you are not a master of garbage collector settings you cannot predict when cleanup will happen.

For example: cleaning a bunch of small objects can be done more effectively with GC because it can free large chunk, but it will be not fast operation, and it's hard to predict when in will occur and because of "large chunk cleanup" it will take some processor time and can affect your program performance.

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
tty6
  • 1,203
  • 11
  • 30
  • 3
    I am not sure that it is possible to predict program performance even with the strongest RAII approaches. Herb Sutter gave some interesting videos about how CPU cache matters and makes performance surprisingly unpredictable. – Basile Starynkevitch Jun 02 '17 at 09:42
  • 9
    @BasileStarynkevitch GC stalls are orders of magnitude larger than cache misses. – Dan Is Fiddling By Firelight Jun 02 '17 at 14:16
  • 2
    There's no such thing as "large chunk cleanup". Actually, GC is a misnomer as most implementations are "Non-Garbage Collectors". They determine the survivors, move them elsewhere, update the pointers and what remains is free memory. It works best when most objects die before the GC kicks in. Usually, it's pretty efficient, but avoiding long pauses is hard. – maaartinus Jun 02 '17 at 19:12
  • 1
    Note that [concurrent and real-time garbage collectors](https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)#Real-time_systems) do exist so predictable performance is attainable. Though, typically, the "default" GC for any given language is designed for efficiency over consistency. – 8bittree Jun 02 '17 at 19:37
  • 5
    Reference counted object graphs can have very long deallocation times too when the last RC holding the graph alive reaches zero and all the deconstructors run. – the8472 Jun 03 '17 at 03:23
10

Roughly speaking. The RAII idiom may be better for the latency and jitter. A garbage collector may be better for the system's throughput.

JFMR
  • 23,265
  • 4
  • 52
  • 76
5

"Efficient" is a very broad term, in sense of development efforts RAII is typically less efficient than GC, but in terms of performance GC is typically less efficient than RAII. However it is possible to provide contr-examples for both cases. Dealing with generic GC when you have very clear resource (de)allocation patters in managed languages can be rather troublesome, just like the code using RAII can be surprisingly inefficient when shared_ptr is used for everything for no reason.

user7860670
  • 35,849
  • 4
  • 58
  • 84
  • 6
    *"in sense of development efforts RAII is typically less efficient than GC"* Having programmed in both C# and C++, where you get a pretty good sampling of both strategies, I have to strongly disagree with that claim. When people find C++'s RAII model to be less efficient, it's more than likely because they are not using it correctly. Which isn't, strictly speaking, a fault of the model. More often than not, it's a sign of people programming in C++ as if it were Java or C#. It is no harder to create a temporary object and let it be automatically freed by scoping than by waiting for GC. – Cody Gray - on strike Jun 03 '17 at 11:09
5

The main part of the question about whether one or the other is "beneficial" or more "efficient" cannot be answered without giving lots of context and arguing about the definitions of these terms.

Beyond that, you can basically feel the tension of the ancient "Is Java or C++ the better language?" flamewar crackling in the comments. I wonder what an "acceptable" answer to this question could look like, and am curious to see it eventually.

But one point about a possibly important conceptual difference has not yet been pointed out: With RAII, you are tied to the thread that calls the destructor. If your application is single threaded (and even though it was Herb Sutter who stated that The Free Lunch Is Over: Most software today effectively still is single-threaded), then a single core may be busy with handling the cleanups of objects that are no longer relevant for the actual program...

In contrast to that, the garbage collector usually runs in its own thread, or even multiple threads, and is thus (to some extent) decoupled from the execution of the other parts.

(Note: Some answers already tried to point out application patterns with different characteristics, mentioned efficiency, performance, latency and throughput - but this specific point was not mentioned yet)

SongWithoutWords
  • 471
  • 5
  • 12
Marco13
  • 53,703
  • 9
  • 80
  • 159
  • 4
    well if you are constraining the environment, if your machine runs on single core or uses multitasking extensively, your main as well as GC threads are bound to run on same core and believe me, context switching will have much more overhead than cleaning up your resources :) – Abhinav Gauniyal Jun 03 '17 at 04:48
  • @AbhinavGauniyal As I tried to emphasize: This is a *conceptual* difference. Others already pointed out the *responsibilities*, but focussed this on a user's point of view (~"the *user* is responsible for cleaning up"). My point was that this also makes an important *technical* difference: Whether the main program is responsible for cleaning up, or whether there is an (independent) part of the infrastructure for this. However, I just thought that this might be worth mentioning, in view of the increasing number of cores (that often lie dormant in single-threaded programs). – Marco13 Jun 03 '17 at 12:45
  • yes, I've upvoted you for the same. I was just presenting the other side of your point as well. – Abhinav Gauniyal Jun 04 '17 at 04:47
  • @Marco13: also, the cost of cleanup is totally different between RAII and GC. RAII in the worst case implies traversing through a just-freed complex reference-counted data structure. GC in the worst case implies traversing thorugh all live objects, which is kind of the reverse thing. – ninjalj Jun 04 '17 at 11:18
  • @ninjalj I'm not an expert with the details - garbage collection is literally an own research branch. In order to argue about the cost, one would probably have to pin down the keywords to one specific implementation (for RAII there's not much room for different options, but at least I know that there are quite some GC implementations, with vastly different strategies). – Marco13 Jun 04 '17 at 20:10
5

Garbage collection and RAII each support one common construct for which the other is not really suitable.

In a garbage-collected system, code may efficiently treat references to immutable objects (such as strings) as proxies for the data contained therein; passing around such references is almost as cheap as passing around "dumb" pointers, and is faster than making a separate copy of the data for each owner, or trying to track ownership of a shared copy of the data. In addition, garbage-collected systems make it easy to create immutable object types by writing a class which creates a mutable object, populating it as desired, and providing accessor methods, all while refraining from leaking references to anything that might mutate it once the constructor finishes. In cases where references to immutable objects need to be widely copied but the objects themselves don't, GC beats RAII hands down.

On the other hand, RAII is excellent at handling situations where an object needs to acquire exclusive services from outside entities. While many GC systems allow objects to define "Finalize" methods and request notification when they are found to be abandoned, and such methods may sometimes manage to release outside services that are no longer needed, they are seldom reliable enough to provide a satisfactory way of ensuring timely release of outside services. For management of non-fungible outside resources, RAII beats GC hands down.

The key difference between the cases where GC wins versus those where RAII wins is that GC is good at managing fungible memory that can be freed on an as-needed basis, but poor at handling non-fungible resources. RAII is good at handling objects with clear ownership, but bad at handling ownerless immutable data holders which have no real identity apart from the data they contain.

Because neither GC nor RAII handles all scenarios well, it would be helpful for languages to provide good support for both of them. Unfortunately, languages which focus on one tend to treat the other as an afterthought.

supercat
  • 77,689
  • 9
  • 166
  • 211
4

RAII uniformly deals with anything that is describable as a resource. Dynamic allocations are one such resource, but they are by no means the only one, and arguably not the most important one. Files, sockets, database connections, gui feedback and more are all things that can be managed deterministically with RAII.

GCs only deal with dynamic allocations, relieving the programmer of worrying about the total volume of allocated objects over the lifetime of the program (they only have to care about the peak concurrent allocation volume fitting)

Caleth
  • 52,200
  • 2
  • 44
  • 75
1

RAII and garbage collection are intended to solve different problems.

When you use RAII you leave an object on the stack which sole purpose is to clean up whatever it is you want managed (sockets, memory, files, etc.) on leaving the scope of the method. This is for exception-safety, not just garbage collection, which is why you get responses about closing sockets and freeing mutexes and the like. (Okay, so no one mentioned mutexes besides me.) If an exception is thrown, stack-unwinding naturally cleans up the resources used by a method.

Garbage collection is the programmatic management of memory, though you could "garbage-collect" other scarce resources if you'd like. Explicitly freeing them makes more sense 99% of the time. The only reason to use RAII for something like a file or socket is you expect the use of the resource to be complete when the method returns.

Garbage collection also deals with objects that are heap-allocated, when for instance a factory constructs an instance of an object and returns it. Having persistent objects in situations where control must leave a scope is what makes garbage collection attractive. But you could use RAII in the factory so if an exception is thrown before you return, you don't leak resources.

cahuson
  • 826
  • 4
  • 10
0

I even heard that having a garbage collector can be more efficient, as it can free larger chunks of memory at a time instead of freeing small memory pieces all over the code.

That's perfectly doable - and, in fact, is actually done - with RAII (or with plain malloc/free). You see, you don't necessarily always use the default allocator, which deallocates piecemeal only. In certain contexts you use custom allocators with different kinds of functionality. Some allocators have the in-built ability of freeing everything in some allocator region, all at once, without having to iterate individual allocated elements.

Of course, you then get into the question of when to deallocate everything - whether the use of those allocators (or the slab of memory with which they're associated has to be RAIIed or not, and how.

einpoklum
  • 118,144
  • 57
  • 340
  • 684