Garbage (computer science)

Example

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:

<span id="mwJg"></span><span class="kd" id="mwJw">public</span><span class="w" id="mwKA"> </span><span class="kd" id="mwKQ">class</span> <span class="nc" id="mwKg">Stack</span><span class="w" id="mwKw"> </span><span class="p" id="mwLA">{</span> <span class="w" id="mwLQ"> </span><span class="kd" id="mwLg">private</span><span class="w" id="mwLw"> </span><span class="n" id="mwMA">Object</span><span class="o" id="mwMQ">[]</span><span class="w" id="mwMg"> </span><span class="n" id="mwMw">elements</span><span class="p" id="mwNA">;</span> <span class="w" id="mwNQ"> </span><span class="kd" id="mwNg">private</span><span class="w" id="mwNw"> </span><span class="kt" id="mwOA">int</span><span class="w" id="mwOQ"> </span><span class="n" id="mwOg">size</span><span class="p" id="mwOw">;</span> <span class="w" id="mwPA"> </span><span class="kd" id="mwPQ">public</span><span class="w" id="mwPg"> </span><span class="nf" id="mwPw">Stack</span><span class="p" id="mwQA">(</span><span class="kt" id="mwQQ">int</span><span class="w" id="mwQg"> </span><span class="n" id="mwQw">capacity</span><span class="p" id="mwRA">)</span><span class="w" id="mwRQ"> </span><span class="p" id="mwRg">{</span> <span class="w" id="mwRw"> </span><span class="n" id="mwSA">elements</span><span class="w" id="mwSQ"> </span><span class="o" id="mwSg">=</span><span class="w" id="mwSw"> </span><span class="k" id="mwTA">new</span><span class="w" id="mwTQ"> </span><span class="n" id="mwTg">Object</span><span class="o" id="mwTw">[</span><span class="n" id="mwUA">capacity</span><span class="o" id="mwUQ">]</span><span class="p" id="mwUg">;</span> <span class="w" id="mwUw"> </span><span class="p" id="mwVA">}</span> <span class="w" id="mwVQ"> </span><span class="kd" id="mwVg">public</span><span class="w" id="mwVw"> </span><span class="kt" id="mwWA">void</span><span class="w" id="mwWQ"> </span><span class="nf" id="mwWg">push</span><span class="p" id="mwWw">(</span><span class="n" id="mwXA">Object</span><span class="w" id="mwXQ"> </span><span class="n" id="mwXg">e</span><span class="p" id="mwXw">)</span><span class="w" id="mwYA"> </span><span class="p" id="mwYQ">{</span> <span class="w" id="mwYg"> </span><span class="n" id="mwYw">elements</span><span class="o" id="mwZA">[</span><span class="n" id="mwZQ">size</span><span class="o" id="mwZg">++]</span><span class="w" id="mwZw"> </span><span class="o" id="mwaA">=</span><span class="w" id="mwaQ"> </span><span class="n" id="mwag">e</span><span class="p" id="mwaw">;</span> <span class="w" id="mwbA"> </span><span class="p" id="mwbQ">}</span> <span class="w" id="mwbg"> </span><span class="kd" id="mwbw">public</span><span class="w" id="mwcA"> </span><span class="n" id="mwcQ">Object</span><span class="w" id="mwcg"> </span><span class="nf" id="mwcw">pop</span><span class="p" id="mwdA">()</span><span class="w" id="mwdQ"> </span><span class="p" id="mwdg">{</span> <span class="w" id="mwdw"> </span><span class="k" id="mweA">return</span><span class="w" id="mweQ"> </span><span class="n" id="mweg">elements</span><span class="o" id="mwew">[--</span><span class="n" id="mwfA">size</span><span class="o" id="mwfQ">]</span><span class="p" id="mwfg">;</span> <span class="w" id="mwfw"> </span><span class="p" id="mwgA">}</span> <span class="p" id="mwgQ">}</span>

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.

Automatic 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:

<span id="mwlQ"></span><span class="gp" id="mwlg">>>> </span><span class="k" id="mwlw">class</span><span class="w" id="mwmA"> </span><span class="nc" id="mwmQ">Foo</span><span class="p" id="mwmg">:</span> <span class="gp" id="mwmw">... </span><span class="w" id="mwnA"> </span><span class="sd" id="mwnQ">"""This is an empty testing class."""</span> <span class="gp" id="mwng">... </span> <span class="k" id="mwnw">pass</span> <span class="gp" id="mwoA">...</span> <span class="gp" id="mwoQ">>>> </span><span class="n" id="mwog">bar</span> <span class="o" id="mwow">=</span> <span class="n" id="mwpA">Foo</span><span class="p" id="mwpQ">()</span> <span class="gp" id="mwpg">>>> </span><span class="n" id="mwpw">bar</span> <span class="go" id="mwqA"><__main__.Foo object at 0x54f30></span> <span class="gp" id="mwqQ">>>> </span><span class="k" id="mwqg">del</span> <span class="n" id="mwqw">bar</span>

In this session, an object is created, its location in the memory is displayed, and the only reference to the object is then destroyed—there is no way to ever use the object again from this point on, as there are no references to it. This becomes apparent when we try to access the original reference:

<span id="mwrw"></span><span class="gp" id="mwsA">>>> </span><span class="n" id="mwsQ">bar</span> <span class="gt" id="mwsg">Traceback (most recent call last):</span> File <span class="nb" id="mwsw">"<stdin>"</span>, line <span class="m" id="mwtA">1</span>, in <span class="n" id="mwtQ">?</span> <span class="gr" id="mwtg">NameError</span>: <span class="n" id="mwtw">name 'bar' is not defined</span>

As it is now impossible to refer to the object, the object has become useless; it is garbage. Since Python uses garbage collection, it automatically deallocates the memory that was used for the object so that it may be used again:

<span id="mwuw"></span><span class="gp" id="mwvA">>>> </span><span class="k" id="mwvQ">class</span><span class="w" id="mwvg"> </span><span class="nc" id="mwvw">Bar</span><span class="p" id="mwwA">:</span> <span class="gp" id="mwwQ">... </span><span class="w" id="mwwg"> </span><span class="sd" id="mwww">"""This is another testing class."""</span> <span class="gp" id="mwxA">... </span> <span class="k" id="mwxQ">pass</span> <span class="gp" id="mwxg">...</span> <span class="gp" id="mwxw">>>> </span><span class="n" id="mwyA">baz</span> <span class="o" id="mwyQ">=</span> <span class="n" id="mwyg">Bar</span><span class="p" id="mwyw">()</span> <span class="gp" id="mwzA">>>> </span><span class="n" id="mwzQ">baz</span> <span class="go" id="mwzg"><__main__.Bar object at 0x54f30></span>

The Bar instance now resides at the memory location 0x54f30; at the same place as where our previous object, the Foo instance, was located. Since the Foo instance was destroyed, freeing up the memory used to contain it, the interpreter creates the Bar object at the same memory location as before, making good use of the available resources.

Effects

Garbage consumes heap memory, and thus one wishes to collect it (to minimize memory use, allow faster memory allocation, and prevent out-of-memory errors by reducing heap fragmentation and memory use).

However, collecting garbage takes time and, if done manually, requires coding overhead. Further, collecting garbage destroys objects and thus can cause calls to finalizers, executing potentially arbitrary code at an arbitrary point in the program's execution. Incorrect garbage collection (deallocating memory that is not garbage), primarily due to errors in manual garbage collection (rather than errors in garbage collectors), results in memory safety violations (that often create security holes) due to use of dangling pointers.

Syntactic garbage can be collected automatically, and garbage collectors have been extensively studied and developed. Semantic garbage cannot be automatically collected in general, and thus causes memory leaks even in garbage-collected languages. Detecting and eliminating semantic garbage is typically done using a specialized debugging tool called a heap profiler, which allows one to see which objects are live and how they are reachable, enabling one to remove the unintended reference.

Eliminating garbage

The problem of managing the deallocation of garbage is well-known in computer science. Several approaches are taken:

• Many operating systems reclaim the memory and resources used by a process or program when it terminates. Simple or short-lived programs which are designed to run in such environments can exit and allow the operating system to perform any necessary reclamation.
• In systems or programming languages with manual memory management, the programmer must explicitly arrange for memory to be deallocated when it is no longer used. C and C++ are two well-known languages which support this model.
• Garbage collection uses various algorithms to automatically analyze the state of a program, identify garbage, and deallocate it without intervention by the programmer. Many modern programming languages such as Java and Haskell provide automated garbage collection. However, it is not a recent development, as it has also been used in older languages such as LISP.
• There is ongoing research to type-theoretic approaches (such as region inference) to identification and removal of garbage from a program. No general type-theoretic solution to the problem has been developed.