1.3 Variants of the basic algorithm

The basic algorithm has several variants.

• There is the issue of whether the garbage collector moves objects in memory (that is, changes their address) or not: moving or non-moving GC.

• Some collectors can correctly identify all pointers (references) in an object; these are called "exact" collectors, the opposite being a "conservative" or "partly conservative" collector. "Conservative" collectors have to assume that any bit pattern in memory is a pointer if (when interpreted as a pointer) it would point into any allocated object. Thus, conservative collectors may have some false negatives, where storage is not released because of accidental fake pointers. However, this is not a big drawback in practice.

• There is the issue of whether the garbage collector can run interleaved or in parallel with any of the rest of the system: the simplest garbage collectors stop the rest of the system while they perform a cycle; they are non-incremental, whereas incremental collectors interleave their work with units of activity from the rest of the system. Some incremental collectors can run fully parallel in a separate thread; these can theoretically run on a separate CPU, but cache issues make this less practical than it may initially appear.

1.3.1 Mark and sweep

Tracing collectors can also be divided by considering how the three sets (of white, grey, and black objects) are implemented. A mark-sweep GC maintains a bit (or two) with each object to record whether it is white or black; the grey set is either maintained as a separate list or using another bit. A Copying GC is a moving GC which, in its simplest form, moves all reachable objects to a single memory area, and then reuses all memory outside this area. Copying GC has the important benefit of resisting fragmentation.

1.3.2 Generational GC

There is the issue of when to perform a cycle and what objects to place in the initial grey set. A simple collector will always put only the roots in the initial grey set, and everything else will be initially white.

Statistically speaking, the objects most recently created in the runtime system are also those most likely to quickly become unreachable. A Generational GC divides objects into generations and will generally only place the objects of a subset of all the generations into the initial white set (the grey set being everything else). This can result in faster cycles.

1.3.3 Disadvantages of tracing garbage collectors

The primary problems with tracing garbage collection arise from the nature of how it is invoked. A collection cycle can occur at any time and can require an arbitrarily long amount of time to complete. While acceptable in many applications, in others for which timing and quick response is critical such as real-time applications, it may cause disaster. Incremental garbage collection helps deal with this problem.

A more fundamental issue is that garbage collectors violate locality of reference, since they deliberately go out of their way to find bits of memory that haven't been accessed recently. This is a particular issue because modern computer architectures get more and more of their performance from manifold intricate levels of cachingThis article is about the computer term. For towns with this name, see Cache, Utah or Cache, Oklahoma and for general sense Cache in general. In computer science, a cache is a collection of duplicate data, where the original data is expensive to fetch or, which depend crucially for their effectiveness on the assumption of locality of reference. In other words, garbage collection is an inherently cache-hostile activity.

The other main problem is that a large amount of garbage can build up very quickly, particularly in functional programmingFunctional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. In contrast to imperative programming, functional programming emphasizes the evaluation of functional expressions, rather than execution languages, before the garbage collector has a chance to collect any of it, resulting in allocation inefficiencies, a temporary bloating in the image size, and a long collection cycle once it occurs; we say that it is not prompt.

To see how tracing garbage collectors are not prompt, consider this example:

loop x := new object x := 0

With a naive tracing garbage collector, each time through the loop more and more memory is allocated, until all the memory in the system is consumed and the garbage collector is forcibly invoked. It's clear why this is unacceptable when we realize that this code never needs more than the memory required for one object!

Finally, a fault shared by all existing garbage collectors is the conservative assumption that memory is still in use if it is still reachable. In many systems, references are kept long after they cease to be used. A popular research area is to find less conservative ways of collecting objects that will never be used again; that is, to safely collect objects to which references still exist. In systems with standard garbage-collection, freeing of this memory can be accelerated by explicitly destroying pointers, but this forces some of the responsibility of memory management back on the programmer.

As one simple example, consider the command-line arguments passed to the startup function. Typically, the program which uses them will parse these arguments and then perform a command accordingly, never touching the arguments themselves again. But they are still kept in memory, because references to them still exist at the bottom of the call stack, in the entry function. Although these objects occupy minimal memory, similar situations often occur with very large or numerous objects.

All of these are often used as arguments against garbage collection and for explicit memory handling, particularly in time-critical applications. However, other forms of garbage collection do not necessarily share all of these faults, although the last is nearly universal, but they may have different faults of their own; all options should be considered when deciding whether to use garbage collection.

2 Reference counting

Reference countingIn computer science, reference counting is a technique of storing the number of references, pointers or handles to a resource such as an object or block of memory. Use in garbage collection Reference counting is often known as a garbage collection algorit is a form of garbage collection where each object stores a count of the number of references to it, and the object is reclaimed when the count reaches zero. For data structures which do not involve cycles of references, such as binary treeTrees (structure) In computer science, a binary tree is an ordered tree data structure in which each node has at most two children. Typically the child nodes are called left and right''. One common use of binary trees is binary search trees; another is bis, it is often preferable to other forms of garbage collection. Even for data structures in which cycles of reference may be present, it's typically able to recover memory more quickly and promptly, despite requiring additional mechanisms to deal with the cycles. Its main disadvantage over tracing garbage collection is the overhead in time and space needed to maintain the reference counts. See reference countingIn computer science, reference counting is a technique of storing the number of references, pointers or handles to a resource such as an object or block of memory. Use in garbage collection Reference counting is often known as a garbage collection algorit for more information.

3 Languages whose standard implementations use automatic garbage collection

• BASICBASIC is a family of high-level programming languages. Originally devised as an easy-to-use tool, it became widespread on home microcomputers in the 1980s, and remains popular to this day in a handful of heavily evolved dialects. BASIC's name, coined in c
• C#
• Caml (and OCaml)
• D
• Dylan
• Eiffel
• Erlang
• Haskell
• ICI
• Java
• Javascript
• Lisp
• Lua
• Mercury
• Modula-3 (one of the major differences from Modula-2 is GC)
• ML
• Oberon (and Oberon-2, Active Oberon , etc)
• Perl
• PHP
• Pico
• Prolog
• Python
• Q
• Ruby
• Scheme
• Smalltalk
• SNOBOL
• Tcl
• Visual Basic.NET

4 External links

• The Memory Management Reference
• Publications by the OOPS group at the University of Texas: http://www.cs.utexas.edu/users/oops/papers.html
• A garbage collector for C and C++ by Hans Boehm (the site also links to a number of articles on garbage collection in general)
• Article "Garbage Collector Basics and Performance Hints" by Rico Mariani
• Citations from CiteSeer

<Hide>