ⓘ Garbage, computer science. Garbage can also refer to garbled data; See Data corruption. In computer science, garbage includes objects, data, or other regions of ..


ⓘ Garbage (computer science)

Garbage can also refer to garbled data; See Data corruption.

In computer science, garbage includes objects, data, or other regions of the memory of a computer system, which will not be used in any future computation by the system, or by a program running on it. As computer systems all have finite amounts of memory, it is frequently necessary to deallocate garbage and return it to the heap, or memory pool, so the underlying memory can be reused.


1. Classification

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

Casually stated, syntactic garbage is data that cannot be reached, while 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 collector 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 reachable but will not be accessed; this latter requires analysis of the code, and is in general an undecidable problem.

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 the latter object being used.


2. Example

In the following simple stack implementation in Java, elements popped from the stack become semantic garbage once there are no outside references to them:

This is because there is still a reference to the object from elements, but the object will never be accessed again through this reference, since elements is private to the class and the pop method only returns references to elements it has not already popped once size is decremented, that element will never be accessed again by this class. However, 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, since it is unreachable, and will be eligible for garbage collection.


2.1. Example 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:

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:

As it is impossible to refer to the object, it has become useless: the object 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:

Note that 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.


3. Effects

Garbage consumes heap memory, and thus one wishes to collect it to minimize memory use, and 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 programs 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 often 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 cause 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 what objects are live and how they are reachable, enabling one to remove the unintended reference.


4. Eliminating garbage

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

  • 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.
  • Many operating systems will 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.
  • There is ongoing research to type theoretic approaches such as region inference to identification and removal of garbage from a program. Note that no general type-theoretic solution to the problem has been developed.
  • In computer science garbage collection GC is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage
  • Garbage may also refer to: Litter, improperly disposed waste products Garbage computer science unreferenced data in a computer s memory Garbage band
  • In computer science garbage in, garbage out GIGO is the concept that flawed, or nonsense input data produces nonsense output or garbage In the UK
  • Garbage collection, or waste collection, is part of municipal waste management. Garbage collection may also refer to: Garbage collection computer science
  • In computer science coalescing is the act of merging two adjacent free blocks of memory. When an application frees memory, gaps can fall in the memory
  • The North Atlantic garbage patch is an area of man - made marine debris found floating within the North Atlantic Gyre, originally documented in 1972. Based
  • The Great Pacific garbage patch, also described as the Pacific trash vortex, is a gyre of marine debris particles in the north central Pacific Ocean.
  • The garbage can model also known as garbage can process, or garbage can theory describes the chaotic reality of organizational decision making in an
  • environment for JamaicaCAR. Aicas Garbage collection computer science Real time Java Embedded Java Fridtjof Siebert, Realtime Garbage Collection in the JamaicaVM
  • substantial error later in the simulation. While all computer analysis is subject to the GIGO garbage in, garbage out restriction, this is especially true of
  • D. March, J. Olsen, J. P. 1972 A Garbage Can Model of Organizational Choice Administrative Science Quarterly. 17 1 1 25. doi: 10.2307 2392088