Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

These days, so many languages are garbage collected. It is even available for C++ by third parties. But C++ has RAII and smart pointers. So what's the point of using garbage collection? Is it doing something extra?

And in other languages like C#, if all the references are treated as smart pointers(keeping RAII aside), by specification and by implementation, will there still be any need of garbage collectors? If no, then why is this not so?

share|improve this question
1  
One thing I understood after asking this question- Smart pointers needs RAII to manage the automatic deallocation. –  Gulshan Dec 27 '10 at 12:45
4  
Smart pointers mean using RAII for GC ;) –  Dario Dec 27 '10 at 13:06
    
Heh, c# should have an option for handling all "garbage collection" with RAII. Circular references can be detected on application shutdown, all we need is see which allocations are still in memory after Program.cs-class has been deallocated. Then circular references can be replaced with some kind of week references. –  AareP Feb 24 '11 at 6:15
2  
add comment

9 Answers

up vote 28 down vote accepted

So, what's the point of using garbage collection?

I'm assuming you mean reference counted smart pointers and I'll note that they are a (rudimentary) form of garbage collection so I'll answer the question "what are the advantages of other forms of garbage collection over reference counted smart pointers" instead.

  • Accuracy. Reference counting alone leaks cycles so reference counted smart pointers will leak memory in general unless other techniques are added to catch cycles. Once those techniques are added, reference counting's benefit of simplicity has vanished. Also, note that scope-based reference counting and tracing GCs collect values at different times, sometimes reference counting collects earlier and sometimes tracing GCs collect earlier.

  • Throughput. Smart pointers are one of the least efficient forms of garbage collection, particularly in the context of multi-threaded applications when reference counts are bumped atomically. There are advanced reference counting techniques designed to alleviate this but tracing GCs are still the algorithm of choice in production environments.

  • Latency. Typical smart pointer implementations allow destructors to avalanche, resulting in unbounded pause times. Other forms of garbage collection are much more incremental and can even be real time, e.g. Baker's treadmill.

share|improve this answer
    
Good answer. +1 –  Konrad Rudolph Dec 27 '10 at 14:56
add comment

Garbage collection basically just means that your allocated objects are automatically released when they're not being referenced any more.

More accurately, they're released when they become unreachable for the program, as circularly referenced objects would never get released otherwise.

Smart pointers just refer to any structure that behaves like an ordinary pointer but has some extra functionality attached. These include but are not limited to deallocation, but also copy-on-write, bound checks, ...

Now, as you have stated, smart pointers can be used to implement a form of garbage collection.

But the train of thought goes the following way:

  1. Garbage collection is a cool thing to have, as it's convenient and I have to take care of fewer things
  2. Therefore: I want garbage collection in my language
  3. Now, how can get GC into my language?

Of course, you can design it like this from start. C# was designed to be garbage collected, so just new your object and it'll be released when the references fall out of scope. How this is done is up to the compiler.

But in C++, there was no garbage collection intended. If we allocate some pointer int* p = new int; and it falls out of scope, p itself is removed from the stack, but nobody takes care of the allocated memory.

Now the only thing you have from start are deterministic destructors. When an object leaves the scope it has been created in, its destructor is called. In combination with templates and operator overloading, you can design a wrapper object that behaves like a pointer, but uses destructor functionality to clean up resources attached to it (RAII). You call this one a smart pointer.

This is all highly C++ specific: Operator overloading, templates, destructors, ... In this particular language situation, you have developed smart pointers to provide you with the GC you want.

But if you design a language with GC from start, this is merely an implementation detail. You just say object will be cleaned up and the compiler will do this for you.

Smart pointers like in C++ wouldn't probably be even possible in languages like C#'s, which have no deterministic destruction at all (C# works around this by providing syntactic sugar for calling a .Dispose() on certain objects). Unreferenced resources will finally be reclaimed by the GC, but it undefined when exactly this will happen.

And this, in turn, can allow the GC to do its work more efficient. Being built in deeper into the language than smart pointers, which are set on top of it, the .NET GC can e.g. delay memory operations and perform them in blocks to make them cheaper or even move memory around for increasing efficiency based on how often objects are accessed.

share|improve this answer
1  
"Garbage collection basically just means that your allocated objects are automatically released when they're not being referenced any more." This is wrong. Objects are released when they are unreachable, but that doesn't mean they are unreferenced; it's not uncommon that circular references between unreachable objects exist. –  user281377 Dec 27 '10 at 12:29
    
@ammoQ: Of course you're right; I'll edit this one. –  Dario Dec 27 '10 at 12:39
    
C# does have a form of deterministic destruction via IDisposable and using. But it requires a little bit of programmer effort, which is why it's usually only used for very scarce resources such as database connection handles. –  JSBձոգչ Dec 27 '10 at 16:14
5  
@JSBangs: Exactly. Just as C++ builds smart pointers around RAII to get GC, C# goes the other way and builds "smart disposers" around the GC to get RAII ;) In fact, it's a shame that RAII is so difficult in C# as it's great for exception-safe resource handling. F# for example tries a simpler IDisposable syntax by just replacing conventional let ident = value by use ident = value ... –  Dario Dec 27 '10 at 16:24
    
@Dario: "C# goes the other way and builds 'smart disposers' around the GC to get RAII". RAII in C# with using has nothing to do with garbage collection at all, it just calls a function when a variable falls out of scope just like destructors in C++. –  Jon Harrop Dec 27 '10 at 17:53
show 4 more comments

Since no one has looked at it from this angle, I'll rephrase your question: why put something into the language if you can do it in a library? Ignoring specific implementation and syntactic details, GC/smart pointers is basically a special case of that question. Why define a garbage collector in the language itself if you can implement it in a library?

There are a couple of answers to that question. The most important first:

  1. You ensure that all code can use it to interoperate. This is, I think, the big reason why code reuse and code sharing didn't really take off until Java/C#/Python/Ruby. Libraries need to communicate, and the only reliable shared language they have is what's in the language spec itself (and, to a degree, its standard library). If you've ever tried to reuse libraries in C++, you've likely experienced the horrendous pain that no standard memory semantics causes. I want to pass a struct to some lib. Do I pass a reference? Pointer? scoped_ptr? smart_ptr? Am I passing ownership, or not? Is there a way to indicate that? What if the lib needs to allocate? Do I have to give it an allocator? By not making memory management part of the language, C++ forces each pair of libraries to have to negotiate their own specific strategy here, and it's really hard to get them all to agree. GC makes that a complete non-issue.

  2. You can design the syntax around it. Because C++ doesn't encapsulate memory-management itself, it has to provide a range of syntactic hooks to let user-level code express all of the details. You have pointers, references, const, dereferencing operators, indirection operators, address-of, etc. If you roll memory management into the language itself, the syntax can be designed around that. All of those operators disappear and the language gets cleaner and simpler.

  3. You get a high return on investment. The value any given piece of code generates is multiplied by the number of people using it. This means that the more users you have, the more you can afford to spend on a piece of software. When you move a feature into the language, all users of the language will be using it. This means you can allocate more effort to it than you could to a library only used by a subset of those users. This is why languages like Java and C# have absolutely first-rate VMs and fantastically high-quality garbage collectors: the cost of developing them is amortized across millions of users.

share|improve this answer
    
Fantastic answer! If only I could upvote more than once... –  Dean Harding Dec 28 '10 at 1:10
5  
It's worth noting that garbage collection is not actually implemented in the C# language itself, but in the .NET Framework, specifically the Common Language Runtime (CLR). –  Robert Harvey Jan 4 '11 at 2:37
1  
@RobertHarvey: It's not implemented by the language, but it wouldn't work without the cooperation of the language. For example, the compiler must include information specifying, at every point in the code, the location of every register or stack-frame offset that holds a reference to an unpinned object. That is an absolute no-exceptions-whatsoever invariant, which could not be upheld without language support. –  supercat Dec 24 '13 at 20:14
    
A major advantage of having GC support the language and required framework is that it ensures that no references will ever exist to memory that might be allocated for some other purpose. If one calls Dispose on an object which encapsulates a bitmap, any reference to that object will be a reference to a disposed bitmap object. If the object was deleted prematurely while other code still expects to use it, the bitmap class can ensure that the other code will fail in predictable fashion. By contrast, using a reference to freed memory is Undefined Behavior. –  supercat Dec 24 '13 at 20:18
add comment

Garbage collection can be more efficient - it basically 'batches up' the overhead of the memory management and does it all at once. In general this will result in less overall CPU being expended on memory de-allocation, but it means that you'll have a big burst of de-allocation activity at some point. If the GC isn't properly designed this can become visible to the user as a 'pause' while the GC tries to de-allocate memory. Most modern GCs are very good at keeping this invisible to the user except under the most adverse conditions.

Smart pointers (or any reference counting scheme) have the advantage that they happen exactly when you'd expect from looking at the code (smart pointer goes out of scope, thing gets deleted). You get little bursts of de-allocation here and there. You overall may use more CPU time on de-allocation, but since it's spread out over all of the things happening in your program, it's less likely (baring de-allocate of some monster data structure) to become visible to your user.

If you are doing something where responsiveness matters, I would suggest that smart pointers/ref counting let you know exactly when things are happening, so you can know while coding what's likely to become visible to your users. In a GC setting you have only the most ephemeral of control over the garbage collector and simply have to try to work around the thing.

On the other hand, if overall throughput is your goal, a GC based system may be a much better choice, as it minimizes the resources needed to do memory management.

Cycles: I do not consider the problem of cycles to be a significant one. In a system where you have smart pointers, you tend toward data structures that don't have cycles, or you are simply careful about how you let go of such things. If necessary, keeper objects that know how to break the cycles in the owned objects can be used in order to automatically insure proper destruction. In some realms of programming this may be important, but for most day-to-day work, it's irrelevant.

share|improve this answer
1  
"you'll have a big burst of de-allocation activity at some point". Baker's treadmill is an example of a beautifully incremental garbage collector. memorymanagement.org/glossary/t.html#treadmill –  Jon Harrop Dec 27 '10 at 18:25
add comment

It's about performance. Unallocating memory requires lot of administration. If the unallocation runs in the background, the performance of foreground process increases. Unfortunatelly, memory allocation can't be lazy (the objects allocated will be used at the holy next moment), but releasing objects can.

Try in C++ (w/o any GC) to allocate a big bunch of objects, print "hello", then delete them. You'll be surprised how long does it take to free objects.

Also, GNU libc provides more effective tools for unallocating memory, see obstacks. Must notice, I have no experience with obstacks, I never used them.

share|improve this answer
    
In principle you have a point but it should be noted that this is an issue that has a very simple solution: use a pool allocator or small object allocator to bundle deallocations. But this admittedly takes (slightly) more effort than having a GC run in background. –  Konrad Rudolph Dec 27 '10 at 14:29
    
Yep, sure, GC is much more comfortable. (Especially for beginners: there're no ownership problems, there's even no delete operator.) –  ern0 Dec 27 '10 at 14:46
3  
@ern0: no. The whole point of (reference counting) smart pointers is that there is no ownership problem and no delete operator. –  Konrad Rudolph Dec 27 '10 at 14:57
    
@Konrad: The only solves the performance problem in the context of single-threaded applications. –  Jon Harrop Dec 27 '10 at 15:29
2  
@Jon: which, honestly, is most of the time. If you willy-nilly share object state between different threads you will have completely different problems. I’ll admit that many people program that way but this is a consequence of the bad threading abstractions that have existed until recently and it’s not a good way to do multithreading. –  Konrad Rudolph Dec 27 '10 at 15:32
show 7 more comments

There are two big differences, to my mind, between garbage collection and smart pointers as used for memory management:

  1. Smart pointers can't collect cyclic garbage; garbage collection can
  2. Smart pointers do all the work at the moments of referencing, dereferencing, and deallocation, on the application thread; garbage collection need not

The former means that GC will collect garbage that smart pointers won't; if you're using smart pointers, you have to avoid creating this kind of garbage, or be prepared to deal with it manually.

The latter means that no matter how smart smart pointers are, their operation will slow down the working threads in your program. Garbage collection can defer work, and move it to other threads; that lets it be more efficient overall (indeed, the runtime cost of a modern GC is less than a normal malloc/free system, even without the extra overhead of smart pointers), and do what work it still needs to do without getting in the way of the application threads.

Now, note that smart pointers, being programmatic constructs, can be used to do all sorts of other interesting things - see Dario's answer - which are completely outside the scope of garbage collection. If you want to do those, you will need smart pointers.

However, for the purposes of memory management, i don't see any prospect of smart pointers replacing garbage collection. They simply aren't as good at it.

share|improve this answer
4  
@Tom: have a look at Dario’s answer for details about smart pointers. As for advantages of smart pointers – deterministic deallocation can be an enormous advantage when used to control resources (not only memory). In fact, this has proven so important that Microsoft has introduced the using block in subsequent versions of C#. Furthermore, the nondeterministic behaviour of GCs can be forbidding in real-time systems (which is why GCs aren’t used there). Also, let’s not forget that GCs are so complex to get right that most actually leak memory and are quite inefficient (e.g. Boehm …). –  Konrad Rudolph Dec 27 '10 at 13:26
3  
The nondeterminism of GCs is, i think, a bit of a red herring - there are GC systems which are suitable for realtime use (like IBM's Recycler), even though the ones you see in desktop and server VMs aren't. Plus, using smart pointers means using malloc/free, and conventional implementations of malloc are nondeterministic due to the need to search the free list. Moving GC systems have more deterministic allocation times than malloc/free systems, although of course less deterministic deallocation times. –  Tom Anderson Dec 27 '10 at 13:49
2  
As for complexity: yes, GCs are complex, but i'm not aware that "most actually leak memory and are quite inefficient", and would be interested to see some evidence otherwise. Boehm is not evidence, because it's a very primitive implementation, and it's built to serve a language, C, where accurate GC is fundamentally impossible due to the lack of type safety. It's a brave effort, and that it works at all is very impressive, but you can't take it as an exemplar of GC. –  Tom Anderson Dec 27 '10 at 13:50
7  
@Jon: decidedly not bullshit. bugzilla.novell.com/show_bug.cgi?id=621899 or, more generally: flyingfrogblog.blogspot.com/2009/01/… This is well-known and a property of all conservative GCs. –  Konrad Rudolph Dec 27 '10 at 14:22
2  
"The runtime cost of a modern GC is less than a normal malloc/free system." Red herring here. This is only because traditional malloc is a horribly inefficient algorithm. Modern allocators that use multiple buckets for different block sizes are much faster to allocate, far less prone to heap fragmentation, and still give you fast deallocation. –  Mason Wheeler Dec 27 '10 at 17:25
show 15 more comments

Please remember that in the end, everything boils down to a CPU executing instructions. To my knowledge all consumer grade CPUs have instruction sets which require you to have data stored in a given place in memory and you have pointers to said data. That's all that you have at the basic level.

Everything on top of that with garbage collection, references to data which may have been moved, heap compaction, etc. etc. is doing the work within the restrictions given by the above "memory chunk with an address pointer" paradigm. Same thing with smart pointers - you STILL have to make the code run on actual hardware.

share|improve this answer
add comment

Most smart pointers are implemented using reference counting. That is, each smart pointer that refers to an object increments the objects reference count. When that count goes to zero, the object is released.

The problem there is if you have circular references. That is, A has a reference to B, B has a reference to C and C has a reference to A. If you're using smart pointers, then in order to free the memory associated with A, B & C you need to manually get in there an "break" the circular reference (e.g. using weak_ptr in C++).

Garbage collection (typically) works quite differently. Most garbage collectors these days use a reachability test. That is, it looks at all of the references on the stack and the ones that are globally accessible and then traces every object that those references refer to, and objects they refer to, etc. Everything else is garbage.

In that way, circular references don't matter any more - as long as neither A, B and C are reachable, the memory can be reclaimed.

There are other advantages to "real" garbage collection. For example, memory allocation is extremely cheap: just increment the pointer to the "end" of the memory block. Deallocation has a constant amortized cost as well. But of course languages like C++ allow you to implement memory management pretty much any way you like, so you could come up with an allocation strategy that's even faster.

Of course, in C++ the amount of heap-allocated memory is typically less than a reference-heavy language like C#/.NET. But that's not really a garbage-collection vs. smart pointers issue.

In any case, the issue isn't cut-and-dry one is better than the other. They each have advantages and disadvantages.

share|improve this answer
add comment

Number one limitation of smart pointers is they don't always help against circular references. For example you have object A storing a smart pointer to object B and object B is storing a smart pointer to object A. If they are left together without resetting either of the pointers they won't ever be deallocated.

This happens because a smart pointer has to perform a specific action which won't be triigered in the above scenario because both objects are unreacheable to the program. Garbage collection will cope - it will properly identify that objects are not reachecable to the program and they will be collected.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.