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.

Or in other words, what specific problems did automated garbage collection solve? I've never done low-level programming, so I don't know how complicated can freeing resources get.

Update - apologies for the unnecessary concision, please let me expand my question:

The kind of bugs that GC addresses seem (at least to an external observer) the kind of things that a programmer that knows well his language, libraries, concepts, idioms, etc, wouldn't do. But I could be wrong: is manual memory handling intrinsically complicated?

share|improve this question
3  
Please expand to tell us how your question is not answered by the Wikipedia article on garbace collection and more specifically the section on its benefits –  Yannis Rizos Jan 11 '12 at 9:59
    
Another benefit is security, e.g. buffer overruns are highly exploitable and many other security vulnerabilities arise from memory (mis)management. –  StuperUser Jan 11 '12 at 11:03
6  
@StuperUser: That has nothing to do with the origin of the memory. You can buffer overrun memory that came from a GC just fine. The fact that GC languages usually prevent this is orthogonal, and languages that are less than thirty years behind the GC technology you're comparing them to also offer buffer overrun protection. –  DeadMG Jan 11 '12 at 11:29
add comment

8 Answers

up vote 10 down vote accepted

(Sorry in advance for the long post. This is a very complicated subject, and even a brief overview of it requires going into some detail to avoid harmful oversimplifications.)

I've never done low-level programming, so I don't know how complicated can freeing resources get.

Funny how the definition of "low-level" changes over time. When I was first learning to program, any language that provided a standardized heap model that makes a simple allocate/free pattern possible was considered high-level indeed. In low-level programming, you'd have to keep track of the memory yourself, (not the allocations, but the memory locations themselves!), or write your own heap allocator if you were feeling really fancy.

Having said that, there's really nothing scary or "complicated" about it, at all. Remember when you were a child and your mom told you to put away your toys when you're done playing with them, that she is not your maid and wasn't going to clean up your room for you? Memory management is simply this same principle applied to code. (GC is like having a maid who will clean up after you, but she's very lazy and slightly clueless.) The principle of it is simple: Each variable in your code has one and only one owner, and it’s the responsibility of that owner to free the variable’s memory when it is no longer needed. (The Single Ownership Principle) This requires one call per allocation, and several schemes exist that automate ownership and cleanup in one way or another so you don't even have to write that call into your own code.

Garbage collection is supposed to solve two problems. It invariably does a very bad job at one of them, and depending on the implementation may or may not do well with the other one. The problems are memory leaks (holding on to memory after you're done with it) and dangling references (freeing memory before you're done with it.) Let's look at both issues:

Dangling references: Discussing this one first because it's the really serious one. You've got two pointers to the same object. You free one of them and don't notice the other one. Then at some later point you attempt to read (or write to or free) the second one. Undefined behavior ensues. If you don't notice it, you can easily corrupt your memory. Garbage collection is supposed to make this problem impossible by ensuring that nothing is ever freed until all references to it are gone. In a fully-managed language, this almost works, until you have to deal with external, unmanaged memory resources. Then it's right back to square 1. And in a non-managed language, things are trickier still. (Poke around on Mozilla's bug-tracker for Firefox sometime and see if you can find how many different crash bugs were caused by their garbage collector screwing up and freeing things too early!)

Fortunately, dealing with this issue is basically a solved problem. You don't need a garbage collector, you need a debugging memory manager. I use Delphi, for example, and with a single external library and a simple compiler directive I can set the allocator to "Full Debug Mode." This adds a negligible (less than 5%) performance overhead in return for enabling some features that keep track of used memory. If I free an object, it fills its memory with 0x80 bytes (easily recognizable in the debugger) and if I ever attempt to call a virtual method (including the destructor) on a freed object, it notices and interrupts the program with an error box with three stack traces--when the object was created, when it was freed, and where I am now--plus some other useful information, then raises an exception. This is obviously not suitable for release builds, but it makes tracking down and fixing dangling reference issues trivial.

The second issue is memory leaks. This is what happens when you continue to hold on to allocated memory when you no longer need it. It can happen in any language, with or without garbage collection, and can only be fixed by writing your code right. Garbage collection helps to mitigate one specific form of memory leak, the kind that happens when you have no valid references to a piece of memory that has not yet been freed, which means the memory stays allocated until the program ends. Unfortunately, the only way to accomplish this in an automated manner is by turning every allocation into a memory leak!

I'm probably going to get dinged by GC proponents if I try to say something like that, so allow me to explain. Remember that the definition of a memory leak is holding on to allocated memory when you no longer need it. In addition to having no references to something, you can also leak memory by having an unnecessary reference to it, such as holding it in a container object when you should have freed it. I've seen some memory leaks caused by doing this, and they are very difficult to track down whether you have a GC or not, since they involve a perfectly valid reference to the memory and there are no clear "bugs" for debugging tools to catch. As far as I know, there is no automated tool that allows you to catch this type of memory leak.

So a garbage collector only concerns itself with the no-references variety of memory leaks, because that's the only type that can be dealt with in an automated fashion. If it could watch all your references to everything and free every object as soon as it has zero references pointing to it, it would be perfect, at least with regards to the no-references problem. Doing this in an automated manner is called reference counting, and it can be done in some limited situations, but it has its own issues to deal with. (For example, object A holding a reference to object B, which holds a reference to object A. In a reference-counting scheme, neither object can be freed automatically, even when there are no external references to either A or B.) So garbage collectors use tracing instead: Start with a set of known-good objects, find all objects that they reference, find all objects that they reference, and so on recursively until you've found everything. Whatever does not get found in the tracing process is garbage and can be thrown away. (Doing this successfully, of course, requires a managed language that puts certain restrictions on the type system to ensure that the tracing garbage collector can always tell the difference between a reference and some random piece of memory that happens to look like a pointer.)

There are two problems with tracing. First, it's slow, and while it's happening the program has to be more or less paused to avoid race conditions. This can lead to noticeable execution hiccups when the program is supposed to be interacting with a user, or bogged-down performance in a server app. This can be mitigated by various techniques, such as breaking allocated memory up into "generations" on the principle that if an allocation doesn't get collected the first time you try, it's likely to stick around for a while. Both the .NET framework and the JVM use generational garbage collectors.

Unfortunately, this feeds into the second problem: memory not getting freed when you're done with it. Unless the tracing runs immediately after you finish with an object, it will stick around until the next trace, or even longer if it makes it past the first generation. In fact, one of the best explanations of the .NET garbage collector I've seen explains that, in order to make the process as fast as possible, the GC has to defer collection for as long as it can! So the problem of memory leaks is "solved" rather bizarrely by leaking as much memory as possible for as long as possible! This is what I mean when I say that a GC turns every allocation into a memory leak. In fact, there is no guarantee that any given object will ever be collected.

Why is this an issue, when the memory still gets reclaimed when needed? For a couple of reasons. First, imagine allocating a large object (a bitmap, for example,) that takes a significant amount of memory. And then soon after you're done with it, you need another large object that takes the same (or close to the same) amount of memory. Had the first object been freed, the second one can reuse its memory. But on a garbage-collected system, you may well be still waiting for the next trace to run, and so you end up unnecessarily wasting memory for a second large object. It's basically a race condition.

Second, holding memory unnecessarily, especially in large amounts, can cause problems in a modern multitasking system. If you take up too much physical memory, it can cause your program or other programs to have to page (swap some of their memory out to disc) which really slows things down. For certain sytems, such as servers, paging can not only slow the system down, it can crash the whole thing if it's under load.

Like the dangling references problem, the no-references problem can be solved with a debugging memory manager. Again, I'll mention the Full Debug Mode from Delphi's FastMM memory manager, since it's the one I'm most familiar with. (I'm sure similar systems exist for other languages.)

When a program running under FastMM terminates, you can optionally have it report the existence of all allocations that never got freed. Full Debug Mode takes it a step further: it can save a file to disc containing not only the type of allocation, but a stack trace from when it was allocated and other debug info, for each leaked allocation. This makes tracking down no-references memory leaks trivial.

When you really look at it, garbage collection may or may not do well with preventing dangling references, and universally does a bad job at handling memory leaks. Its one virtue, in fact, is not the garbage collection itself, but a side-effect: it provides an automated way to perform heap compaction. This can prevent an arcane problem (memory exhaustion through heap fragmentation) that can kill programs that run continually for a long time and have a high degree of memory churn, and heap compaction is pretty much impossible without garbage collection. However, any good memory allocator these days uses buckets to minimize fragmentation, which means that fragmentation only truly becomes a problem in extreme circumstances. For a program in which heap fragmentation is likely to be a problem, it's advisable to use a compacting garbage collector. But IMO in any other case, the use of garbage collection is premature optimization, and better solutions exist to the problems that it "solves."

share|improve this answer
    
The single ownership principle doesn't necessarily work in practice. Given a data object used in several places, it isn't trivial to assign a single owner or figure out when to release the memory. Even relatively primitive GC (like reference counting) can solve that problem. –  David Thornley Jan 11 '12 at 17:15
    
@David: Reference counting is an example of the single-ownership principle, and it's the appropriate way to deal with the situation you describe, as the linked article explains. –  Mason Wheeler Jan 11 '12 at 17:18
1  
I love this answer - I keep reading it every now and then. Can't come up with a relevant remark so all I can say is - thank you. –  vemv Jan 25 '12 at 9:03
1  
I'd like to point out that yes, GCs tend to "leak" memory (at least for a while), but this isn't an issue because it will collect the memory when the memory allocator cannot allocate memory prior to collection. With a non-GC language, a leak always stays a leak, meaning you actually can run out of memory due to too much uncollected memory. "garbage collection is premature optimization"... GC isn't an optimization and was not designed with that in mind. Otherwise, good answer. –  Thomas Eding Aug 15 '12 at 20:47
    
@ThomasEding: GC certainly is an optimization; it optimizes for minimal programmer effort, at the expense of performance and various other program quality metrics. –  Mason Wheeler Jan 8 at 3:16
add comment

Considering a non-garbage-collected memory management technique from an equivalent era as the garbage collectors in use in current popular systems, such as C++'s RAII. Given this approach, then the cost of not using automated garbage collection is minimal, and GC introduces plenty of it's own problems. As such, I'd suggest that "Not much" is the answer to your problem.

Remember, when people think of non-GC, they think malloc and free. But this is a giant logical fallacy- you'd be comparing non-GC resource management of the early 1970s to the garbage collectors of the late 90s. This is obviously a rather unfair comparison- the garbage collectors that were in use when malloc and free were designed were much too slow to run any meaningful program, if I remember correctly. Comparing something from a vaguely equivalent time period, e.g. unique_ptr, is much more meaningful.

Garbage collectors can handle reference cycles more easily, although these are pretty rare experiences. In addition, GCs can just "throw up" code because the GC will take care of all memory management, meaning that they can lead to faster dev cycles.

On the other hand, they tend to run into massive problems when dealing with memory that came from anywhere except their own GC pool. In addition, they lose a lot of their benefit when concurrency is involved, because you have to consider object ownership anyway.

Edit: Many of the things you mention have nothing to do with GC. You're confusing memory management and object orientation. See, here's the thing: If you program in a completey unmanaged system, like C++, you can have as much bounds checking as you like, and the Standard container classes do offer it. There's nothing GC about bounds checking, for example, or strong typing.

The problems you mention are solved by object-orientation, not GC. The origin of array memory and making sure you don't write outside it are orthogonal concepts.

Edit: It is worth noting that more advanced techniques can avoid the need for any form of dynamic memory allocation at all. For example, consider the use of this, which implements Y-combination in C++ with no dynamic allocation at all.

share|improve this answer
    
The extended discussion here has been cleaned up: if everyone can take it to chat to discuss the topic further, I'd really appreciate it. –  user8 Jan 11 '12 at 19:52
    
@DeadMG, do you know what combinator is supposed to do? It is supposed to COMBINE. By definition, combinator is a function without any free variables. –  SK-logic Jan 11 '12 at 20:02
2  
@SK-logic: I could have chosen to implement it purely by template and not have any member variables. But then you would not be able to pass in closures, which significantly limits it's usefulness. Care to come to chat? –  DeadMG Jan 11 '12 at 20:05
    
@DeadMG, a definition is crystal clear. No free variables. I consider any language "functional enough" if it is possible to define Y-combinator (properly, not your way). A big "+" is if it is possible to define it via S, K and I combinators. Otherwise language is not expressive enough. –  SK-logic Jan 11 '12 at 20:23
4  
@SK-logic: Why don't you come to the chat, like the kind moderator asked? Also, a Y-combinator is a Y-combinator, it does the job or it doesn't. The Haskell version of the Y-combinator is basically exactly the same as this one, it's just that the state expressed is hidden from you. –  DeadMG Jan 11 '12 at 20:24
add comment

The "freedom from having to worry about freeing resources" that garbage-collected languages supposedly provide is to a considerable extent an illusion. Keep adding stuff into a map without ever removing any, and you will soon understand what I am talking about.

In fact, memory leaks are quite frequent in programs written in GCed languages, because these languages tend to make the programmers lazy, and make them acquire a false security that the language somehow always takes care of every object that they do not wish to think about anymore.

Garbage collection is simply a necessary facility for languages that have another, more noble goal: to treat everything as a pointer to an object, and at the same time hide from the programmer the fact that it is a pointer, so that the programmer cannot commit suicide by attempting pointer arithmetic and the like. Everything being an object means that GCed languages need to allocate objects far more often than non-GCed languages, which means that if they put the burden of deallocating those objects on the programmer, they would be immensely unattractive.

Also, garbage collection is useful in order to provide the programmer with the ability to write tight code, manipulating objects inside expressions, in a functional programming fashion, without having to break the expressions down into separate statements in order to provide for the deallocation of every single object that participates in the expression.

Aside from all that, please note that in the beginning of my answer I wrote "it is to a considerable extent an illusion". I did not write that it is an illusion. I did not even write that it is mostly an illusion. Garbage collection is useful in taking away from the programmer the menial task of attending to the deallocation of his objects. So, in this sense it is a productivity feature.

share|improve this answer
add comment

Manual resource is not only tedious, but also difficult to debug. In other words, not only is it tedious to get it right, but also when you get it wrong, it's not obvious where the problem is. This is because, unlike for example division by zero, the effects of the error show up away from the source of error, and connecting the dots requires time, attention and experience.

share|improve this answer
add comment

Garbage collector does not address any "bugs". It is a neccessary part of some high level languages semantics. With a GC it is possible to define higher levels of abstractions, such as lexical closures and alike, whereas with a manual memory management those abstractions will be leaky, unnecessarily bound to the lower levels of the resource management.

A "single ownership principle", mentioned in the comments, is quite a good example of such a leaky abstraction. A developer should not be concerned at all about the number of links to any particular elementary data structure instance, otherwise any piece of code would not be generic and transparent without a huge number of additional (not directly visible in the code itself) limitations and requirements. Such a code cannot be composed into a higher level code, which is an intolerable breach of the layers of responsibility separation principle (a major building block of the software engineering, unfortunately not respected at all by most of the low level developers).

share|improve this answer
    
+1. That's what I am also talking about. I just do it with more words and less accurate terms. –  Mike Nakis Jan 11 '12 at 13:36
    
Funny. Delphi managed to implement lexical closures a couple years back with no GC... –  Mason Wheeler Jan 11 '12 at 14:09
1  
You're wrong. No GC can protect you from the fact that you cannot refer to stack variables. And it's funny- in C++, you can take the "Copy a pointer to a dynamically allocated variable which will be appropriately and automatically destroyed" approach, too. –  DeadMG Jan 11 '12 at 14:51
1  
@DeadMG, don't you see that your code is leaking low level entities through any other level you build on top? –  SK-logic Jan 11 '12 at 14:58
1  
@SK-Logic: OK, we have a terminology problem. What's your definition of "real closure," and what can they do that Delphi's closures can't? (And including anything about memory management in your definition is moving the goal posts. Let's talk about behavior, not implementation details.) –  Mason Wheeler Jan 11 '12 at 15:11
show 9 more comments

Really, managing your own memory is just one more potential source of bugs.

If you forget a call to free (or whatever the equivalent is in whichever language you're using), your program can pass all of its tests, but leak memory. And in a moderately complex program, it's quite easy to overlook a call to free.

share|improve this answer
2  
Missed free is not the worst thing. Early free is much more devastating. –  herby Jan 11 '12 at 10:47
1  
And the double free! –  quant_dev Jan 11 '12 at 10:51
    
Hehe! I'd go along with both of the two comments above. I've never committed one of these transgressions myself (as far as I know), but I can see how terrible the effects might be. The answer from quant_dev says it all - mistakes with memory allocation and de-allocation are notoriously hard to find and fix. –  David Wallace Jan 11 '12 at 11:10
1  
This is a fallacy. You're comparing "early 1970" to "late 1990". The GCs that existed at the time at which malloc and free was the non-GC way to go were vastly too slow to be useful for anything. You need to be comparing it to a modern non-GC approach, like RAII. –  DeadMG Jan 11 '12 at 11:17
1  
@DeadMG RAII is not manual memory management –  quant_dev Jan 11 '12 at 11:30
show 3 more comments

I think garbage collection gets a lot of credit for language improvements that have nothing to do with GC, other than being part of one big wave of progress.

The one solid benefit to GC I know of is that you can set an object free in your program and know it will go away when everyone is done with it. You can pass it to another class's method and not worry about it. You don't care what other methods it gets passed to, or what other classes reference it. (Memory leaks are the responsibility of the class referencing an object, not the class that created it.)

Without GC you have to track the entire life cycle of the allocated memory. Every time you pass an address up or down from the subroutine that created it, you have an out-of-control reference to that memory. In the bad old days, even with only one thread, recursion and an ornery operating system (Windows NT) made it impossible for me to control access to allocated memory. I had to rig the free method in my own allocation system to keep memory blocks around for a time until all the references got cleared out. The holding time was pure guesswork, but it worked.

So that's the only GC benefit I know of, but I couldn't live without it. I don't think any kind of OOP will fly without it.

share|improve this answer
1  
Just off the top of my head, Delphi and C++ have both been quite successful as OOP languages without any GC. All you need to prevent "out of control references" is a bit of discipline. If you understand the Single Ownership Principle, (see my answer,) the problems you're talking about here become total non-issues. –  Mason Wheeler Jan 12 '12 at 2:39
    
@MasonWheeler: When it's time for the owner object to be freed, it needs to know all the places that its owned objects are referenced. Maintaining this information and using it to remove the references looks like an awful lot of work to me. I often found the references could not be cleared quite yet. I had to mark the owner as deleted, then bring it to life periodically to see if it could safely free itself. I've never used Delphi, but for a small sacrifice in execution efficiency C#/Java gave me a big boost in development time over C++. (Not all due to GC, but it helped.) –  RalphChapin Jan 12 '12 at 19:56
add comment

Here's a list of problems faced by C++ programmers when dealing with memory:

  1. Scoping problem occurs in stack allocated memory: it's lifetime do not extend outside of the function where it was allocated in. There are three main solutions to this problem: heap memory, and moving the allocation point upwards in the call stack or allocating from inside objects.
  2. Sizeof problem is in stack allocated and allocating from inside object and partly heap allocated memory: The memory block's size cannot change on the runtime. Solutions are heap memory arrays, pointers and libraries and containers.
  3. Order of definition problem is when allocating from inside objects: the classes inside the program need to be in correct order. Solutions are restricting dependencies to a tree and reordering the classes and not using forward declarations, and pointers and heap memory and using forward declarations.
  4. Inside-Outside problem is in object allocated memory. Memory access inside objects is divided to two parts, some memory is inside an object and other memory is outside of it, and programmers need to correctly choose to use either composition or references based on this decision. Solutions are doing the decision correctly, or pointers and heap memory.
  5. Recursive objects problem is in object allocated memory. Size of objects becomes infinite if same object is placed inside itself, and solutions are references, heap memory and pointers.
  6. Ownership tracking problem is in heap allocated memory, the pointer containing address of the heap allocated memory has to be passed from allocation point to deallocation point. Solutions are stack allocated memory, object-alloated memory, auto_ptr, shared_ptr, unique_ptr, stdlib containers.
  7. Ownership duplication problem is in heap allocated memory: the deallocation can only be done once. Solutions are stack allocated memory, object-allocated memory, auto_ptr, shared_ptr, unique_ptr, stdlib containers.
  8. Null pointer problem is in heap allocated memory: the pointers are allowed to be NULL making many of the operations crash on runtime. Solutions are stack memory, object-allocated memory and careful analysis of heap areas and references.
  9. Memory leak problem is in heap allocated memory: Forgetting to call delete for every allocated memory block. Solutions are tools like valgrind.
  10. Stack overflow problem is for recursive function calls which are using stack memory. Normally size of stack is completely determined on compile time, except for the case of recursive algorithms. Defining OS's stack size wrong also often causes this problem since there is no way to measure the required size of stack space.

As you can see, the heap memory is solving very many existing problems, but it causes additional complexity. GC is designed to handle part of that complexity. (sorry if some problem names are not the correct names for these problems -- sometimes it's difficult to figure out the correct name)

share|improve this answer
1  
-1: Not an answer to the question. –  Sjoerd Jan 12 '12 at 23:53
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.