Tracing
Memory that is no longer needed is garbage. An automatic garbage collection system detects and releases this garbage without any help from the programmer. Taking away this responsibility from programmers has some benefits. The programmer won't forget to free memory, so there won't be memory leaks. The programmer isn't freeing memory, so there will be no inadvertent double-frees that corrupt free lists. Memory won't be classified as garbage until all pointers to it have gone out of scope, so there will be no dangling pointers.
Several automatic garbage collection systems are in use, including tracing, reference counting, and Rust's ownership model. We examine the first of these now and the others later on.
Many of the languages you use, including Java, C#, Ruby, JavaScript, and Python have a garbage collector that is included in the language runtime. It maintains a list of all objects that have been allocated on the heap. The collector periodically traces through static memory and all stack frames to find references to heap allocations. The objects on the heap to which these references point are still in play and must be retained. The collector recurses on any objects it finds in an accessible object's state. If any object on the list of all objects has no references pointing to it, it is inaccessible garbage and is eligible to be freed.
This garbage collection algorithm was named mark-and-sweep by its inventor John McCarthy, who developed it for LISP in the late 1950s. The garbage collector kicked in when memory ran out. No other work could be performed while objects were being marked as accessible. This exclusivity had unfortunate side effects. Allan Martin wrote in Teaching and Learning with Logo what impact the garbage collector had on playing music:
A problem which may arise, especially when long tunes with harmony are being played, is that inexplicable pauses may suddenly interrupt the music. These are due to “garbage collections”: these take place whenever the computer is running short of memory to run a program, and involve a reorganisation of items in the computer's memory in order to make as much memory as possible available to run the program. Automatic garbage collections are part of all LISP and LOGO systems. They are essential, since these systems tend to use up a lot of memory whilst running programs; and garbage collections maximise the amount of memory available. But they do produce a short pause in the program run, and can occur at inconvenient moments.
Martin suggested scheduling garbage collection during rests and in between musical phrases. Such intermittent hiccups are unacceptable in some contexts, including life-critical systems and games, which is why the determinism of manual memory management of C and C++ remains popular.
Java ships with several different garbage collectors. The serial collector, like the original mark-and-sweep collector, halts execution while a single thread traces through objects to find reachable allocations. The parallel collector, which was the default collector up through Java 8, also halts execution but traces with multiple threads. The epsilon collector intentionally does not trace or reclaim memory. It's used when we don't want garbage collection to interfere with code that we are trying to benchmark. More advanced collectors, like concurrent mark sweep and garbage first, run concurrently with our program instead of halting it. We choose which collector is used through arguments to the JVM.
Some collectors perform compaction by copying marked objects into a consolidated region of memory. Compaction reduces fragmentation. Since allocations are being moved, the collector must update a program's references to point at the new allocations. The JVM is better situated to perform this update than the C and C++ runtimes because pointers are are abstracted away behind references.
Many objects are allocated and needed for only a short time before they become garbage. Accordingly, some collectors devote most of their attention to tracing only objects that were recently allocated. These collectors partition the heap into generations. Each new object is placed initially in the youngest generation, which the Java designers named Eden Space. This space is traced frequently. If a newborn object survives several collection cycles, it is moved to Survivor Space, which is traced less frequently. If it continues to survive, it is moved to Tenured Space, which is traced even less frequently.
Garbage collection via tracing is a dynamic activity whose significant overhead and non-determinism puts some developers on edge. They'd prefer garbage collection to be more predictable. Reference counting may be what they're looking for.