Garbage (computer science)

In computer science, garbage includes data, objects, or other regions of the memory of a computer system (or other system resources), which will not be used in any future computation by the system, or by a program running on it. Because every computer system has a finite amount of memory, and most software produces garbage, it is frequently necessary to deallocate memory that is occupied by garbage and return it to the heap, or memory pool, for reuse.

Garbage is generally classified into two types: syntactic garbage, any object or data which is within a program's memory space but unreachable from the program's root set; and semantic garbage, any object or data which is never accessed by a running program for any combination of program inputs. Objects and data which are not garbage are said to be live.

Casually stated, syntactic garbage is data that cannot be reached, and semantic garbage is data that will not be reached. More precisely, syntactic garbage is data that is unreachable due to the reference graph (there is no path to it), which can be determined by many algorithms, as discussed in tracing garbage collection, and only requires analyzing the data, not the code. Semantic garbage is data that will not be accessed, either because it is unreachable (hence also syntactic garbage), or is reachable but will not be accessed; determining the latter requires code analysis, and is in general undecidable.

Syntactic garbage is a (usually strict) subset of semantic garbage, as it is entirely possible for an object to hold a reference to another object without ever using that object.

In the following simple stack implementation in Java, each element popped from the stack becomes semantic garbage once there are no outside references to it:

This is because elements[] still contains a reference to the object, but the object will never be accessed again through this reference, because elements[] is private to the class and the pop method only returns references to elements it has not already popped. (After it decrements size, this class will never access that element again.) However, knowing this requires analysis of the code of the class, which is undecidable in general.

If a later push call re-grows the stack to the previous size, overwriting this last reference, then the object will become syntactic garbage, because it can never be accessed again, and will be eligible for garbage collection.

An example of the automatic collection of syntactic garbage, by reference counting garbage collection, can be produced using the Python command-line interpreter: