81

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 means that any compiler that tried to do this would necessarily produce some programs with memory leaks and/or some programs that continued to use memory that had been freed. Even if you ensured ...


53

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 dynamic garbage collection is an undecidable problem! All real-world garbage collectors use reachability as a conservative approximation to whether or not an ...


29

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 undecidable for both humans and compilers, it's impossible to always knowingly select the optimal deallocation placement, regardless of whether it's a manual or ...


23

Currently, none of the posted answers are fully correct. Why don't compilers automatically insert deallocations? Some do. (I'll explain later.) Trivially, you can call free() just before the program exits. But there's an implied need in your question to call free() as soon as possible. The problem of when to call free() in any C program as soon as the ...


19

Here are a few papers that talk about the cache implications of generational garbage collectors: Caching Considerations for Generational Garbage Collection The Effect of Garbage Collection on Cache Performance From what I can gather, the primary issue is that garbage collected systems trade off space in memory to avoid up front collection. The same thing ...


13

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 is a common choice. The queue can get large — potentially as large as the deepest data structure. The queue is typically stored explicitly, not on the stack of ...


11

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, which gives considerable implementation freedom to represent the sets. Hence there are many solutions that are actually very cheap in memory usage. This is ...


10

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 garbage collection: The finalizer pattern: cleanup method declared automatically, defined by programmer, called automatically. Finalizers are called ...


10

There is a very tricky aspect of all garbage collectors that might be glossed over in some descriptions, and that is the "full scan" or "full collect". Periodically, randomly, intermittently they must scan all objects. generational collectors are better at postponing the full scan and minimizing its duration, but it is still required. The generational ...


10

"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 (sometimes dramatically) our chances of success in technological matters, especially when human factors seem to be absent. Human performance in computer ...


9

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. That includes allocating and deallocating memory at the moment of your choosing. C is a low-level language you use when you want to control the computer ...


9

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 whole program at once. When one source file calls a function from another source file or a library, all the compiler sees is the header file with the return type ...


9

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 guarantee through GC is not possible - at least, not without sacrifying performance. Standard GC mechanisms only ensure the deinit code is eventually run, e.g. at the next GC cycle. For precise ...


8

As I recall, copy collectors are supposed to be paging friendly, as the tracing by copying tends to improve the locality of pointer references. This has a positive effect on the program (mutator) that will cause less page faults when following links, and will also improve the next collection cycle as tracing will also cause less page faults. The tracing ...


7

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 garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are in memory, especially during ...


6

Like Häagen-Dazs ice-cream, Object Orientation comes in many flavor, though with more nuts and bananas. Hence it is hazardous to answer your question stated in very general terms. Specific OO languages could have unexpected features that might raise problems with virtual methods. I fear that trying to imagine what kind of features could make things go wrong ...


6

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 inevitable delay in garbage collection. In C, when a programmer calls free(), that memory is immediately available for reuse. (In theory at least!) So a programmer ...


5

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 to be compensated for by explicit triggering of destruction and finalization of some objects and structures. Tracing garbage collectors are much more effective,...


5

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 language. The way I found this out was by consulting Paul Wilson's 1992 survey, Uniprocessor Garbage Collection Techniques, which is required reading if you need ...


4

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, and can be implemented/used in any language that has first class functions. Example (pseudocode). Suppose you have a "raw file" type, like the Posix file ...


4

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 that need to be examined/traversed, which serves this role. For instance, your "Unscanned" queue is an example of exactly this sort of pattern. The queue can ...


4

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 Andrew Appel's Modern Compiler Implementation (Cambridge University Press, 1998)), collectors are classified as either "Mark and Sweep" or "Copying". Mark and ...


4

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 proposed for running functional languages. Some of them are the SECD machine, the CAM (categorical), the Krivine machine, the STG machine. Perhaps a more radical ...


4

GC deals with a predictable and reserved resource. The VM has total control over it and has total control over what is created and when. The key words here are "reserved" and "total control". On the other hand, handles and are resources allocated by the OS, and pointers are... well pointers to resources allocated outside the managed space. Because of that, ...


4

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 anymore" is information only known in the mind of the programmer until it's encoded into (in procedural languages) a deallocation statement. It's not ...


4

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 reference cycles. The real answer to the "why" is that compiler writers haven't figured out a way that is good enough and fast enough to make it usable in a ...


4

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 as straightforward as a weak key map). I'm using (slightly modified) terminology from Designing Efficient and Safe Weak References in Eiffel with Parametric ...


3

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 implementation property? reference counting GC and tracing GC provide the programmer with different gaurantees. Reference counting provides determinism in the ...


3

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 ensures that when an object that holds onto resources goes out of scope, it will close the resources it was holding on to. This is helpful when the object's ...


3

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 collection. The big problem with finalizers is that they aren't guaranteed to run. There's a pretty good write-up on using finalizers here: Object finalization and ...


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