Is garbage collection necessary?

Question

Do any languages really need garbage collection? Is there not a way to figure out when a object should be destroyed? I haven't had leaks in C++ and i dont use smart pointers or reference counters or anything special. I confirm this by attaching something for leak detection: whether its built in to the IDE or a header that uses magic (defines) to overloads new/free.

Is garbage collection necessary, or is it possible to have a leak-free application in a language without placing the memory burden on the programmer?

Related/possible duplicates: Why Garbage Collection if smart pointers are there, Is there a need for Garbage Collection in a Stack Based Language? — , Oct 09 '11 at 01:41
Yes, take a look at automatic reference counting in objective-c. It's an amazing tool, and it's essentially compile-time GC (so theres no runtime load). — Richard J. Ross III, May 13 '13 at 05:39
@RichardJ.RossIII: Reference counting is generally the slowest memory management technique. There is simply so many reference and unreference operations that it gets really noticeable. If done manually, you can often optimize many of those operations away, but the compiler usually can't. — Jan Hudec, Oct 15 '13 at 08:12
@JanHudec while most of the time I would agree with you, read up on this document to see that it is actually able to optimize a significant number of situations. — Richard J. Ross III, Oct 15 '13 at 16:16
@RichardJ.RossIII Also worth noting it's still subject to circular references, just like "manual" reference counting. — weberc2, Nov 20 '15 at 20:44

Ben · Answer 1 · 2011-10-09T03:27:05.647

23

Is there not a way to figure out when a object should be destroyed?

The short answer is no. It is not possible for compilers to figure out at compile time when objects need to be freed, in the general case.

Consider the following pseudo-code:

def my_function(some_input):
    A = allocate_some_object(some_input)
    B = allocate_other_object(some_input)
    if check_some_condition(A, B):
        return A
    else
        return B

In order for the compiler to know whether A or B should be freed after this function returns, it has to know what check_some_condition(A, B) will return. That would require solving the halting problem, which is not possible in the general case.

More seriously, check_some_condition could store a reference to A somewhere else, in which case A is not garbage at the end of the function even if B is returned. The compiler would have to be able to know whether this happens with 100% certainty, and even if it did know you then have to solve the problem of flowing the information around until you find some place where A does become garbage and can be deallocated. That could be in a completely different part of the program.

Plus, deallocating every object as soon as it becomes possible isn't actually always the best option. If objects are being created and dropped all the time, and you have enough memory available, running a garbage collector every so often and deallocating the garbage in bulk can actually be more efficient than hand-tuned C-style manual memory management (despite claims that GC is always a trade off between performance and convenience).

There are techniques that can do some of this, some of the time. Escape analysis can allow the compiler to deduce that a given object cannot "escape" some section of code, so what looks like a heap allocation can be turned into a stack allocation, which is effectively memory managed by the compiler. I've read about other techniques allowing a compiler to tell that a given object must be garbage at the point another object of the same size is created, so instead of compiling an allocation of a new object it re-uses the dead value. But it simply isn't possible to completely replace garbage collection cycles with the compiler figuring out statically when every object needs to be deallocated, because the compiler can only figure that out some of the time.

edited Oct 09 '11 at 03:27

answered Oct 09 '11 at 01:38

Ben

1,027
7
10

Very good. I want to pick a few points 1) if it was recursive and its only true in the base case why would the gc free the memory? How would it know the if statement wont execute 2) i heard many memory managers in C are bad. As in they do all the bookkeeping on every delete and new instead if flip a few flags and run them in bulk. I dont suppose gc can do them faster if the memory manager tries to free in bulk? – Oct 09 '11 at 02:39
If "the compiler figuring out statically when every object needs to be deallocated" why is it not possible "to completely replace garbage collection"?

Oct 09 '11 at 02:41

@acidzombie24 1) I think I framed that example very badly. What I was trying to do was make you think of a case where a heuristic static memory manager would get it wrong and have to keep excess memory around, where a dynamic garbage collector would prevent unbounded memory growth. Such cases exist; I just failed to demonstrate one. – Ben Oct 09 '11 at 03:05

@acidzombie24 2) The essential difference is that by reacting to objects dropping out of scope then you need at least some operations for every object you free even if that's just flipping a few flags and then the amortized cost of the bulk deallocate (although you probably can't bulk deallocate in C; the objects will be non-contiguous). A fully managed GC scans the live objects, and can compact the heap as it goes. So the final deallocate is just a single pointer subtraction, and the scan only considers live objects, and only on each GC cycle. For some workloads this can be less work. – Ben Oct 09 '11 at 03:18

@acidzombie24 And 3) my point was that it is not possible for the compiler to figure out statically when every object needs to be deallocated. There's always cases that require information from runtime to do properly, so if the compiler were doing it statically it would have to use conservative safe assumptions. And that means there'll always be cases where those rules aren't good enough, and the program uses too much memory, while a GC would let it run fine. – Ben Oct 09 '11 at 03:20

@acidzombie24 There, I've updated my example of "undecidable garbage" to be a lot clearer, I hope. – Ben Oct 09 '11 at 03:27

2

The return value of check_some_condition(A,B) is irrelevant for determining when to free A or B, at least for this example. The compiler could trivially insert frees: if check_some_condition(A,B) { free B; return A } else { free A; return B }. The problem here is if check_some_condition(A,B) stores references to A or B anywhere. – 8bittree Jun 17 '16 at 19:42

"The short answer is no. It is not possible for compilers to figure out at compile time when objects need to be freed, in the general case."

I just want to add one comment, your answer is completely stupid if not borderline retarded. The code you have mentioned works today in rust https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2986b67e9c80a79a7f50ec416b5b40cf and I'm so sick of people on the internet, out of their own ignorance saying "something is impossible" when they have no clue what they're talking about. Your attitude limited research and creativity at 2011.

– Vanilla Face Jan 11 '19 at 11:05

score 17 · Answer 2 · answered Oct 09 '11 at 05:12

Do any languages really need garbage collection?

I'm going to stick to only this question (at least for now).

Others have posited that the answer is clearly no, garbage collection is never really needed (just often very convenient). I'm going to go on record as saying they're wrong, or have at least answered a question somewhat different from what was asked.

It's absolutely true that the externally visible behavior of a program written in a language that includes garbage collection can normally be imitated to an arbitrary degree of accuracy with code written in a language that does not include garbage collection.

The original question wasn't about programs though, it was about languages. Addressing that question, the answer is yes, garbage collection really is needed for some languages. Some languages (e.g., Lisp family) have had/used GC for so long that it has become completely fundamental to how that language is used. In theory, a couple of functions (or probably special forms) to allocate and free memory would be trivial to add. In reality, however, much of how most Lisp code is written depends so thoroughly on the presence of GC that if it were removed and the programmer were forced to handle such allocation and freeing manually, the result would be a language almost completely different from Lisp, that just happened to have almost the same syntax.

Caleb · Answer 3 · 2011-10-09T01:23:35.140

3

It seems that you've answered your own question. No, of course garbage collection isn't necessary, and the very existence of languages without GC such as C and C++ show that.

Garbage collection can be a nice feature, however. It removes the burden of properly managing memory from the programmer, thereby making a language both easier to use and more reliable.

GC isn't the only way to lighten the programmer's load with respect to memory management. For example, Apple has recently added Automatic Reference Counting (ARC) to Objective-C. Previously, Objective-C programmers could manage memory manually using Objective-C's reference counting mechanism (retain/release), or (on the MacOS X platform) they could opt for garbage collection. ARC basically combines the two: a static analyzer looks at the code and automatically inserts calls to the appropriate memory management methods. This frees the programmer from having to manually manage memory, but eliminates the need for a garbage collector.

edited Oct 09 '11 at 01:23

answered Oct 09 '11 at 00:27

Caleb

39,147
8
95
152

I edited the last part of my question – Oct 09 '11 at 00:31
Okay, I've updated my answer. – Caleb Oct 09 '11 at 01:25
1

Note that any solution based solely on reference counts cannot cope with cycles. The application (i.e the programmer) has to deal with this by breaking each cycle at the appropriate point in time. In general, that is difficult. – Stephen C Oct 09 '11 at 02:06
Thats actually really cool. – Oct 09 '11 at 02:18
1

It was pretty nifty when the static analyzer started pointing out mistakes in memory management. ARC takes it a step further: since the analyzer can figure out where the memory management calls should be, it can also put them in for you. Very nice. – Caleb Oct 09 '11 at 02:21
I would say automatic use of reference counting is a form of garbage collection. It's also known as a particularly inefficient way to implement garbage collection. – Ben Oct 12 '11 at 20:41
2

@Ben GC based on reference counting is inefficient only if you have only strong references. ARC is automatic but you have to comply with a lot of rules - break cycles by using weak references, use defined method naming rules (method names starting by "init", "create", "copy" are special). Basically, the programmer needs to decide who owns an object. And it's pretty efficient. Don't mix it with a reference-counting based GC. With ARC the runtime doesn't search object graph for unused objects. – Sulthan Oct 15 '13 at 08:51
1

A very late rebuttal to @Ben: ARC is not garbage collection because ARC doesn't use a garbage collector. GC generally includes a run time component that reclaims memory that's no longer needed. ARC is essentially manual memory management, except that the compiler takes care of inserting appropriate memory management calls. ARC is quite like so-called "compile time GC", but that's a pretty long way from what's traditionally considered to be "garbage collection." If you consider ARC to be GC, then traditional Obj-C memory management is "manual GC." – Caleb Oct 15 '13 at 14:36
Not so much a rebuttal as a different definition. I would consider any technology for automatically collecting no-longer-needed memory to be "garbage collection". Heap scanning is one broad family of implementation technique for that idea; automatic use of reference counts is another. (For whatever it's worth, the wikipedia page on garbage collection uses the term the same way I do) – Ben Oct 15 '13 at 15:13
@Caleb: "ARC is not garbage collection because ARC doesn't use a garbage collector". Reference counting is regarded as a form of garbage collection in the literature. See http://gchandbook.org – J D Mar 21 '15 at 15:16
2

@Sulthan: "GC based on reference counting is inefficient only if you have only strong references". The JVM and CLR do not use reference counting precisely because that is not true. – J D Mar 21 '15 at 15:17

Jon Purdy · Answer 4 · 2013-10-15T08:03:08.380

Garbage collection is not necessary any more than variables, types, or loops. These are all conveniences for expressing different kinds of problems. The job of garbage collection is to simulate a machine with infinite memory. Some languages heavily encourage using it; others offer it merely to make the programmer’s life easier.

Tracing garbage collection is not the only approach to automated memory management. Reference counting is the dual to tracing, and most production garbage collectors include features of both—e.g., generational tracing and cycle-detecting RC. Some languages even obviate the need for runtime garbage collection by predicting resource allocation at compile time. This can be done with substructural types.

Anonymous downvoter: kindly explain? – Jon Purdy Oct 10 '11 at 13:53 — Jon Purdy, Oct 10 '11 at 13:53

score 3 · Answer 5 · answered May 12 '13 at 23:53

Garbage collection per se is not necessary to the virtual machine of languages where it is commonly used. In such languages the assumption is actually that objects live indefinitely after creation. In one of the LISP machines of the '80's there was originally no garbage collection. Instead, one ran the machine until memory ran out, and then saved the image, restarted the machine and reloaded the image. Saving the image only saved the reachable data, so when you reloaded you'd be using less memory. After a little while a garbage collector was added to this system. For one reference of this, see "Evolution of LISP", "Evolution of LISP" in PDF form, page 27

Today I think it would be completely reasonable to prototype a language like that with no garbage collector, but eventually one will need to reclaim unused objects or else run out of memory.

Also, many neophytes have wondered if there was some way to avoid all this with the stack. This has been considered in academia using a derivation of arena-based memory management called Region Inference where the compiler determines the lives of references to objects based on scope information, which is where the stack comes in, and type information, which in a language like ML is already being analyzed. Some programs run more slowly under this system, but many do run faster, according to citations in the Wikipedia article.

Stephen C · Answer 6 · 2011-10-09T01:00:34.057

Garbage collection is really a way of simplifying the problem of memory management for the programmer. So when you ask whether a language "really needs garbage collection", you are actually asking whether the programmer needs help.

And the answer to that is that it depends on:

how complex are the problems that the programmer is trying to solve,
how good is the programmer at dealing with this, and
whether the programmer has the time to deal with this.

While you believe that C and C++ don't need garbage collection based on your experiences, maybe this is telling you that your experiences are limited. My experience is that garbage collection makes my life a lot simpler when writing complex software, and that there are certain kinds of problem that I would not dream of implementing in a non-GC'ed language.

The other point is that garbage collection (supported at the language level) does memory management safely. It removes the risk of some bit of code will accidentally free an object twice, use an object after it has been freed, or write beyond the end of an object / array and trampling something else. (OK, the particularities of this depend on the language we are talking about. But the properties of safety and GC go hand in hand in a typical GC'ed language.)

i mean if the language can figure out when to delete/free so we have no leaks (rather then it using a collector)

There are three known effective ways to automate memory reclamation:

The compiler figures out that certain objects can never be used once a scope has exited, and emits code to free them. (Or allocates them on the stack). This is only applicable in certain cases.
The compiler (or the programmer via "smart pointers") uses reference counting and frees objects when their reference counts reach zero. This approach doesn't work when there are reference cycles.
A garbage collector traverses the graph of reachable objects and throws away those that are not reachable. This works provided that the application doesn't keep references to objects that are not needed.

I'm not aware of any other ways of automating memory management.

(Note that even GC'ed languages are vulnerable to certain kinds of storage leak.)

+1. Is there a name for the first point? (The compiler figures out that certain objects can never be used once a scope has exited) has a language implemented that? — , Oct 09 '11 at 01:28
In the context of Java (at least) it is called "escape analysis". Note that it is not a substitute for GC, since it only works for simple cases; e.g. the kind where you could say (in C) "ah ... I can allocate that on the stack and it will always work". — Stephen C, Oct 09 '11 at 01:57
@acidzombie24: I'd call it escape analysis. It gets used in Java, but for a different reason. I don't think there's a language using it for GC: Alone it's too weak, together with other GC techniques it doesn't help much (as modern GC don't handle memory regions to be freed explicitly, instead they copy regions to be preserved). — maaartinus, Oct 09 '11 at 02:02
Of course mistakes in a GC language still result in bugs, such as many Java programs which continue to consume memory until they crash, because of programmers that retain live references to unneeded objects. — Zan Lynx, Oct 10 '11 at 15:35

score 0 · Answer 7 · answered Oct 09 '11 at 00:26

0

What do you mean by necessary? You can certainly manage the memory with smart pointers and that takes minimal effort too (although the occasional cyclic reference can be a problem but that's not too hard to fix in most cases). Garbage collection is just another way of freeing unneeded memory.

One additional thing that garbage collectors can do is defragmenting the memory (if they use another level of indirection). If you have lots of allocations and deallocations of small objects, the memory can become fragmented and even if there is enough physical memory available in total, paging still occurs. I have never seen such thing happening, but it's possible (if you are developing to constrained hardware).

answered Oct 09 '11 at 00:26

Tamás Szelei

7,767

I think he's asking whether we need languages without automatic garbage collection any more ... – Rook Oct 09 '11 at 00:28
@Rook Nah i mean if the language can figure out when to delete/free so we have no leaks (rather then it using a collector) – Oct 09 '11 at 00:33
1

@acidzombie24: you seem to misunderstand something. When we refer to GC, like in Java or other modern languages, the GC is not some kind of afterthought, it is PART of the language. – c_maker Oct 09 '11 at 00:41

score 0 · Answer 8 · answered Oct 09 '11 at 00:29

If you have a heap, allocated memory must be released. In practice, this is little more than a bookkeeping entry, but new allocations can only use unallocated memory. If your language is not designed to have deterministic deallocation, you have to clean it up some other way. The reason not to have deterministic deallocation is that it makes the access to objects easier and less constraining. For the purposes of some languages, this is an advantage. It is one that would not be advantageous to C++. But you do have to do one or the other.

score 0 · Answer 9 · answered Oct 09 '11 at 00:37

0

There is no reason to have a modern language which does not come with its own memory management. These days languages attempt to optimize developer productivity and the less things we have to worry about, the better.

answered Oct 09 '11 at 00:37

c_maker

8,280

I didnt mean that. I mean shouldnt languages now be able to determine when something should be deleted? I never heard of leaks in a functional language. – Oct 09 '11 at 01:25
@acidzombie24: Yes. The garbage collector determines what should be deleted. – c_maker Oct 09 '11 at 01:26
2

@acidzombie24 Functional languages typically have garbage collectors. Still necessary despite the fact that they also typically have WAY more information available to the compiler to optimize with. It's not enough. – Ben Oct 09 '11 at 01:40

subbareddy · Answer 10 · 2013-05-14T08:56:29.393

Garbage collection is not necessary to provide. In java, you can create only objects you never destroy that. That destruction system will taken care-of. Just you can close that objects never destroy.

In C++ construction and destruction is manually not in java.

if suppose your applying the garbage collection. There is no surety that objects are destroyed or not.

Not only me any one also told this one for this question.

Is garbage collection necessary?

10 Answers10

Linked

Related