86 votes
Accepted

Why don't compilers automatically insert deallocations?

Because it's undecidable whether the program will use the memory again. This means that no algorithm can correctly determine when to call free() in all cases, which ...
57 votes

Why don't compilers automatically insert deallocations?

As David Richerby rightly noted, the problem is undecidable in general. Object liveness is a global property of the program, and may in general depend on the inputs to the program. Even precise ...
  • 19.3k
30 votes

Why don't compilers automatically insert deallocations?

It's an incompleteness problem, not an undecidability problem While it's true that the optimal placement of deallocation statements is undecidable, that's simply not the issue here. Since it's ...
  • 1,331
24 votes

Why don't compilers automatically insert deallocations?

Currently, none of the posted answers are fully correct. It's not impossible to do this, but adding that feature would restrict mermory allocation patterns. Why don't compilers automatically insert ...
13 votes

How do garbage collectors avoid stack overflow?

Note that I am not a garbage collection expert. This answer only gives examples of techniques. I do not claim that it is a representative overview of garbage collection techniques. An unscanned queue ...
11 votes
Accepted

How do garbage collectors avoid stack overflow?

In a nutshell: Garbage collectors do not use recursion. They just control tracing by keeping track of essentially two sets (that may combine). The order of tracing and cell processing is irrelevant, ...
  • 19.2k
10 votes
Accepted

Why is the object destructor paradigm in garbage collected languages pervasively absent?

The pattern you're talking about, where objects know how to clean their resources up, falls into three relevant categories. Let's not conflate destructors with finalizers - only one is related to ...
10 votes

Why don't compilers automatically insert deallocations?

"Humans do it, so it's not impossible" is a well-known fallacy. We do not necessarily understand (let alone control) the things that we create - money is a common example. We tend to overestimate (...
9 votes

Why don't compilers automatically insert deallocations?

The lack of automatic memory management is a feature of the language. C is not supposed to be a tool for writing software easily. It is a tool for making the computer do whatever you tell it to do. ...
9 votes

Why don't compilers automatically insert deallocations?

The issue is mostly a historic artifact, not an impossibility of implementation. The way most C compilers build code is so that the compiler only sees each source file at a time; it never sees the ...
  • 207
9 votes
Accepted

Is reference counting GC vs. tracing GC a language property or an implementation property?

Swift guarantees that once the last reference to an object is dropped the object is deinitialized, and the deinit code is immediately run. Obtaining this kind of ...
  • 14.2k
9 votes
Accepted

Could a compiler automatically insert memory deallocations if it were to simulate every conditional statement?

No, it's not possible for a compiler to do that. Doing so is an undecidable problem. To get some intuition for why it is hard, consider the combinations of loops and conditional statements. It's not ...
  • 145k
8 votes

Are there any garbage collectors that take into account paging?

Emery Berger, Matthew Hertz & Yi Feng did some work on this. Garbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing ...
6 votes

Why don't compilers automatically insert deallocations?

Other answers have focussed on whether it is possible to do garbage collection, some details of how it's done, and some of the problems. One issue which hasn't yet been covered though is the ...
  • 219
6 votes

Could a compiler automatically insert memory deallocations if it were to simulate every conditional statement?

Even without (appropriately) invoking the halting problem, there are situations where this is impossible: for instance when the allocation/deallocation scheme depends on the particular values of the ...
  • 5,285
5 votes

Why is the object destructor paradigm in garbage collected languages pervasively absent?

In a nutshell Finalization is not a simple matter to be handled by garbage collectors. It is easy to use with reference counting GC, but this family of GC is often incomplete, requiring memory leaks ...
  • 19.2k
5 votes
Accepted

When was the terminology *tracing collector* introduced to denote both mark-and-sweep and copy collectors

The terminology was introduced in Lang and Dupont, Incremental Incrementally Compacting Garbage Collection, SIGPLAN 87. This is the paper which consolidated several lines of enquiry into one common ...
  • 19.3k
5 votes

Could a compiler automatically insert memory deallocations if it were to simulate every conditional statement?

What D.W. said is correct in one way: It is impossible for a compiler in general to decide that at point X in a program, object O is not referenced anymore and can be deallocated. However, you can (...
  • 25.9k
4 votes

Why is the object destructor paradigm in garbage collected languages pervasively absent?

The object destructor pattern is fundamental to error handling in systems programming, but has nothing to do with garbage collection. Rather, it has to do with matching object lifetime to a scope, ...
4 votes

How do garbage collectors avoid stack overflow?

The standard way to avoid a stack overflow is to use an explicit stack (stored as a data structure in the heap). That works for these purposes too. Garbage collectors often have a worklist of items ...
  • 145k
4 votes

Is reference counting GC vs. tracing GC a language property or an implementation property?

chi has answered the specific question in the body about swift, this answer answers the more general question in the title. Is reference counting GC vs. tracing GC a language property or an ...
4 votes

How do garbage collectors avoid stack overflow?

In "classic" descriptions of garbage collection (e.g., Mark Wilson, "Uniprocessor Garbage Collection Techniques", Int'l Workshop on Memory Management, 1992, (alternate link), or the description in ...
4 votes

Why don't compilers automatically insert deallocations?

The question presumes a deallocation is something the programmer is supposed to deduce from other parts of the source code. It's not. "At this point in the program, memory reference FOO isn't useful ...
4 votes
Accepted

Why does garbage collection extend only to memory and not other resource types?

GC deals with a predictable and reserved resource. The VM has total control over it and has total control over what instances are created and when. The keywords here are "reserved" and "total control"....
4 votes

Why don't compilers automatically insert deallocations?

What is done: There is garbage collection, and there are compilers using reference counting (Objective-C, Swift). Those that do reference counting need help from the programmer by avoiding strong ...
  • 25.9k
4 votes
Accepted

Is it possible to implement a WeakMap with primitive keys and weak values?

Okay. My confusion with this question is that I assumed that what you wanted is a weak value map, which it appears is what you want, and this can be implemented in a straightforward manner (at least ...
3 votes

Why does garbage collection extend only to memory and not other resource types?

There are many programming techniques to help manage these kinds of resources. C++ programmers often use a pattern called Resource Acquisition is Initialization, or RAII for short. This pattern ...
  • 145k
3 votes

Why does garbage collection extend only to memory and not other resource types?

This appears to be one of the reasons languages with garbage collectors implements finalizers. Finalizers are intended to allow a programmer to clean up an object's resources during garbage ...
3 votes

What are some possible "functional" memory structures?

The topic is fairly broad. Functional hardware has been explored in e.g. Lisp machines. More on the theoretical side, you may want to read about the various abstract machines which have been ...
  • 14.2k
3 votes

Why don't compilers automatically insert deallocations?

In languages like C, the programmer is expected to insert calls to free. Why doesn't the compiler do this automatically? Because the lifetime of a memory block is the programmer's decision, not the ...
  • 213

Only top scored, non community-wiki answers of a minimum length are eligible