Topic: memory management by garbage collection

topics > computer science > operating system > Group: memory management

dangling pointers
finalization of data
heap memory management
memory management by age
memory management by reference counting
safe use of pointers


Garbage collection is reclaiming unused memory from the heap. It is important for managed, object-oriented code such as Java and C#. Lisp and Smalltalk include garbage collectors. Similar techniques are useful for other resources such as files. Distributed garbage collectors work across multiple nodes. Real-time garbage collectors bound the cost of garbage collection. Reference counting and garbage collection are closely related. (cbb 12/07)
Subtopic: garbage collection up

Quote: without garbage collection, objects must be owned; who releases a string that is queued for printing? [»swinDC7_1985]
Quote: garbage collection allows resources to be easily shared
Quote: garbage collection is essential for reliability; avoids memory leaks and dangling pointers which are expensive to correct [»goslJ6_1997]
Quote: big gain in Cedar was garbage collection; simplifies interfaces, e.g., functions which return strings [»donaJ7_1985a]
Quote: garbage collection increases flexibility of argument passing to procedure parameters and variables [»swinDC7_1985]
Quote: the life span of an object is limited by the life space of its reference value

Subtopic: language-based collector up

Quote: Cedar's safe storage improves system structure, convenience, and reliability [»swinDC7_1985]
Quote: large software systems often contain an application-specific garbage collector; should be part of the language
Quote: to be object-oriented, a computer must provide automatic storage management [»ingaDH8_1981a]
Quote: objects created by expressions and destroyed when last reference disappears; accessed by uniform reference throughout the system [»ingaDH8_1981a]
Quote: garbage collection simplifies interfaces; neither client nor implementation frees allocated references; e.g., Modula-3's required interface for Text [»nelsG_1991]
Quote: Modula-3 always uses garbage collection of traced references in safe modules
Quote: C-- is a portable assembly language; e.g., language-independent specification of garbage collection

Subtopic: immutable strings and garbage collection up

Quote: efficient string concatenation implies data sharing and automatic garbage collection [»boehHJ12_1995]
Quote: a Cedar rope is an immutable, garbage-collected, text string; widely used in all system levels [»swinDC7_1985]
Quote: Cedar ropes are immutable, garbage collected, strings; same as a value [»teitW3_1985]

Subtopic: file garbage collection up

Quote: Amoeba's bullet server deletes old versions when not in the file directory of name, capability pairs; garbage collection
Quote: an index defines the internal name for objects in a backing store server; objects exist as long as a name exists [»birrAD9_1980]
Quote: Amoeba's file server performs garbage collection by touching every file every k days and deleting a file if not accessed in n days (n>>k) [»taneAS12_1990]
Quote: use garbage collection to reclaim deleted files; mark deleted files by rename; on scan, delete from metadata; delete metadata for orphaned chunks [»gherS10_2003]
Quote: heartbeat messages sync chunkservers and master incrementally; deletes orphaned chunks
Quote: can delete a file's body, both header and body, and/or its index entry; garbage-collection removes unusable items [»stoyJE3_1972]

Subtopic: comparative study up

Quote: comparative study of semi-space, mark-sweek, reference counting, and generational garbage collection; direct and indirect costs of mutator, collector, L1 and L2 cache, TLB misses [»blacSM6_2004]
Quote: contiguous allocation important for cache performance of garbage collection; generational, copying collection is best [»blacSM6_2004]
QuoteRef: joneR_1996 ;;excellent survey of garbage collection algorithms

Subtopic: reference counting and garbage collecting up

Quote: tracing and reference counting are algorithmic duals for garbage collection; live vs. dead objects, anti-operations [»bacoDF10_2004]
Quote: tracing and reference counting are duals -- tracing the object graph, scanning an object [»bacoDF10_2004]
Quote: ulterior reference counting uses generational mark-sweep collector for young objects; good throughput with low pause times [»blacSM10_2003]
Quote: garbage collect if a reference count becomes negative; indicates an allocation cycle [»birrAD9_1980]
Quote: realistic, high-performance garbage collectors combine tracing with reference counting
Quote: lazy mark-scan: deletions are added to a queue for later mark-scan, but deleting the last reference performs an immediate deletion [»linsRD12_1992]
Quote: manage memory with reference counting and a sweep algorithm for circular structures; provides benefits of garbage collection at low cost [»dorwSM1_1997]
Quote: most high-performance, general-purpose systems use tracing garbage collectors instead of reference counting [»wilsPR9_1992]
Quote: a fast, cyclic reference counting algorithm based on partial traces and sub-graphs; total execution time is similar [»linCY3_2007]

Subtopic: explicit free up

Quote: for mark-sweep, free-me compiler analysis inserts explicit frees; reclaims 30% of all objects, mostly short-lived and factory methods; not useful for generational collection [»guyeSZ6_2006]

Subtopic: garbage-collection vs. explicit management up

Quote: in a garbage-collected program, simulate explicit memory management by inserting calls to 'free' after last use or after last reachable [»hertM10_2005]
Quote: with five times as much memory, an Appel-style generational collector is as fast as a reachability-based explicit memory manager; 70% slower with 2x memory [»hertM10_2005]

Subtopic: cost model up

Quote: uniform cost model for garbage collectors, both tracing and reference counting
Quote: cost model for garbage collection--unit time for collection, space overhead for metadata, frequency, mutation overhead, and total time overhead [»bacoDF10_2004]
Quote: with care, garbage collection is about 3-5 times slower than explicit memory management [»stroB_1987]
Quote: it may be cheaper and simpler to copy a return value than to allocate and deallocate an object on free store [»stroB_1991]

Subtopic: security up

Quote: many systems for untrusted OS extensions depend on a trusted garbage collector [»walkD7_2000]
Quote: Oberon's garbage collector must be safe; use type guards, range checks, and NIL tests for all pointers [»wirtN9_1989]
Quote: if capabilities include the object type, the owner may deallocate or reuse the capability's memory; allows safe deallocation of objects [»walkD7_2000]

Subtopic: generational collector up

Quote: generational collectors are better than whole heap collectors in almost all circumstances; lower collection time; write barrier is reasonable [»blacSM6_2004]
Quote: older-first garbage collection copies up to 10x less than generational collection; requires up to 10x more write barrier work [»stefD11_1999]
Quote: generational collectors perform similarly; use mark-sweep mature space in small heaps [»blacSM6_2004]
Quote: generational collectors provide good spatial locality for young objects; mature objects have good temporal locality
Quote: nursery size for generational collectors should be well above the L2 cache size [»blacSM6_2004]
Quote: generational collectors improving relative to explicit memory management; good use of spatial locality for young objects

Subtopic: copying garbage collector up

Quote: collect short-lived objects with a copying nursery; explicit free of short-lived objects does not improve generational collectors; similar results for stack collection [»guyeSZ6_2006]
Quote: the copying garbage collection algorithm only touches reachable cells; independent of garbage [»appeAW6_1987]
Quote: use virtual-memory hardware for efficient, copying garbage-collection; uniprocessors and shared-memory multiprocessors [»appeAW7_1988]

Subtopic: distributed garbage collection up

Quote: any distributed termination detection algorithm can solve the distributed, isolated train detection problem for garbage collection [»lowrMC12_2002]
Quote: taxonomy of distributed garbage-collection schemas; explores locality, overhead, and latency [»abduSE9_1998]
Quote: both distributed and normal garbage collection must balance completeness and expediency; difficult to do if distributed [»abduSE9_1998]

Subtopic: termination of distributed computations up

Quote: detecting termination of distributed computations is equivalent to a garbage collection problem; can use to derive new termination algorithms [»telG1_1993]
Quote: both termination and garbage collection satisfy safety (if marked, it is terminated/garbage) and liveness (will mark if terminated/garbage) [»telG1_1993]

Subtopic: concurrent garbarge collection up

Quote: Recycler multiprocessor garbage collector with low pause times; loosely synchronized, concurrent reference counting; local, concurrent cycle detection [»bacoDF6_2001]
Quote: local, concurrent cycle detection in O(n) with reduced constant factors
Quote: an on-the-fly, multiprocessor garbage collector based on sliding views; low pause times, good throughput [»azatH10_2003]
Quote: improved, mostly concurrent garbage collector; avoids initial trace of dirty cards; optimize for no traced objects [»baraK10_2003]

Subtopic: real-time garbage collection up

Quote: hierarchical real-time garbage collection of independently collected heaplets; 26% better worst-case response time and 2x mutator utilization [»pizlF6_2007]
Quote: multiprocessors complicate real-time garbage collection because atomicity requires locks; heaplets may help processor locality [»pizlF6_2007]
Quote: time-based scheduling is better than work-based scheduling for real-time garbage collector; yields consistent utilization without frequent pauses [»bacoDF1_2003]
Quote: Metronome is a hard real-time incremental uni-processor garbage collector; regular ticks between mutator and collector; combines mark-sweep with copying collection [»bacoDF6_2005]
Quote: Metronome garbage collector used less than 30% of each time period; configured with maximum simulateously live data and peak allocation rate

Subtopic: incremental collector up

Quote: Cedar's safe storage by incremental garbage collection, runtime type discrimination, generic reference, and symbolic access
Quote: Squeak usually uses one word of overhead per object, incremental garbage collection, bulk-mutation, extended BitBlt, multi-media
Quote: treadmill is a non-copying garbage collector that uses a doubly-linked list and a color field that assigns each object to a collection set [»wilsPR9_1992]
Quote: use tricolor marking to understand incremental garbage collection: release white objects, retain black objects, and process descendants of grey objects; no pointers from black to white objects [»wilsPR9_1992]
Quote: for incremental garbage collection, coordinate collector and mutator with read or write barriers; write barriers cause fewer faults [»wilsPR9_1992]
Quote: mostly non-copying, real-time incremental garbage collector with 4% read barrier overhead and 45% utilization in 1.6-2.5x actual space [»bacoDF1_2003]

Subtopic: region-based collector up

Quote: use a registration server instead of garbage-collection; register an object for cleanup at program termination; remove registration if object is explicitly terminated
Quote: contaminated garbage collection dynamically identifies each object with a stack frame; 4-24% faster than Java collector [»cannDJ6_2000]
Quote: contaminated garbage collection via an equilive equivalence relation with union by rank and path compression; four 32-bit words per object [»cannDJ6_2000]

Subtopic: pinned objects up

Quote: CLR supports pinned objects that do not move during garbage collection; for arguments to native functions [»hamiJ2_2003]
Quote: with garbage collection and debugging, a call can modify live local variables; C-- can mark parameters and variables as invariant across calls [»joneSP9_1999]
Quote: Eventrons can not change the reachability of managed objects; uses pinned objects that are accessible from ordinary threads [»spooD6_2006]
Quote: avoid incompletely constructed objects by setting a "fully constructed" flag on each object [»spooD6_2006]

Subtopic: compressor up

Quote: memory compressor assumes all objects are moved, using page protection to trap unmoved objects; copies pages when used [»kermH6_2006]
Quote: concurrent, incremental memory compressor with short pauses and one heap pass; requires 3x storage [»kermH6_2006]

Subtopic: generic code up

Quote: CLR generics identify compatible parameterizations; i.e., reference types, struct types compatible if same layout re garbage collection; otherwise unshared code [»kennA6_2001]

Subtopic: finalizer up

Quote: actions performed "at garbage-collection time" may occur any time between the object's last use and program termination; must execute under an unknown state [»stroB_1991]

Subtopic: implementation up

Quote: a garbage collector needs to partition memory into different strategies, traverse by tracing or reference counting, decide on space-time tradeoffs [»bacoDF10_2004]
Quote: collect cycles in memory by tracing or by regions [»bacoDF10_2004]
Quote: Oberon's mark-and-sweep garbage collector only runs between commands when the stack is empty; no local variables [»wirtN9_1989]
Quote: each Oberon module includes a pointer reference list of all global pointers; used for garbage collection [»wirtN9_1989]
Quote: C-- replaces C as a portable assembly language; includes a low-level, reusable run-time system that hides calling conventions and stack allocation; permits register allocation, liveness analysis, and garbage collection [»joneSP9_1999]

Subtopic: leak detection up

Quote: memory leak detection for garbage-collectors using differences between volumes of type points-from graph; no false positives, space and time efficient [»jumpM1_2007]

Subtopic: optimizing garbage collection up

Quote: fast garbage collection of complex list structures by using a unique defining reference; mark with a bit and reassign last [»specD3_1982]
Quote: use liveness analysis to reduce retained garbage; about 50% more expensive than type analysis
Quote: implement hashCode with bits for hasBeenHashed and hasHashField; for garbage collection of direct pointers [»agesO2_1999]
Quote: avoid bulk copying in garbage collection by hijacking the method table to create a per-object read barrier; low overhead but requires dynamic dispatch [»cheaAM9_2000]
Quote: use read-barrier to avoid scavenging newly-allocated objects for Baker's garbage collection algorithm [»cheaAM9_2000]
Quote: implement read-barriers for Baker's memory algorithm via address range checks, virtual memory, or hardware checks on pointers [»cheaAM9_2000]
Quote: share tables of live pointers across call sites; shrinks garbage collection tables to 20-25% of their original size; 1% of executable code [»tardD10_2000]

Subtopic: large memory objects up

Quote: Metronome garbage collector uses arrays of arraylets; the arrayoid contains the object header, arraylet pointers, and optionally. the last arraylet [»bacoDF6_2005]
Quote: keep arraylets in the heap and arrayoid in the garbage collector's nursery; allows large memory objects in the nursery without the space cost [»bacoDF6_2005]

Subtopic: virtual memory up

Quote: avoid paging while garbage collecting by cooperating with the virtual memory manager; use bookmarks to avoid virtual memory access; 5x faster under memory pressure [»hertM6_2005]
Quote: prior to eviction to disk; the BC garbage collector bookmarks references into the page and increments the target superpages' headers; allows collecting the heap without paging [»hertM6_2005]

Subtopic: optimizing memory and cache up

Quote: use low overhead profiling to reorganize layout for a generational garbage collector; reduces cache miss by 21-42% [»chilTM10_1998]
Quote: if sort live objects by address, selective sweeping can reclaim contiguous dead objects in one operation [»chunYC1_2000]
Quote: used class splitting and cache-conscious garbage collection; 20% faster and 29-43% fewer L2 cache misses [»chilTM12_2000]
Quote: improve cache performance via copying garbage collector, object-oriented languages, and octree coloring; 42% speedup [»chilTM12_2000]
Quote: garbage collection by collecting addresses during mark, sort and compact; expected linear time [»carlS2_1991]
Quote: achieve 'free' garbage collection by using 8x the memory [»appeAW6_1987]
Quote: if keep free-space pointer in a register, then allocating a cons cell from heap same as from stack [»appeAW6_1987]
Quote: if enough memory is available, cheaper to garbage collect a cell than to explicitly free it [»appeAW6_1987]

Subtopic: history up

Quote: a data record is created dynamically and reclaimed through garbage collection [»wirtN6_1966]
QuoteRef: palmJ5_1973 ;;9 Automatic garbage collection of non-referenced structures

Subtopic: problems with manual management up

Quote: manual memory management leads to global bookkeeping, slow memory leaks, dangling pointers, and fixed array sizes [»wilsPR9_1992]
Quote: dangling pointers and storage leaks tend to persist long after other errors are removed; prevent with garbage collection [»nelsG_1991]
Quote: with explicit storage allocation, programmer must avoid dangling references and storage leaks [»swinDC7_1985]
Quote: generational collectors improving relative to explicit memory management; good use of spatial locality for young objects

Subtopic: problems with garbage collection up

Quote: drawback of garbage-collection is that its overhead appears only during long runs

Related Topics up

Topic: dangling pointers (13 items)
Topic: finalization of data (11 items)
Topic: heap memory management (33 items)
Topic: memory management by age (18 items)
Topic: memory management by reference counting (23 items)
Topic: safe use of pointers
(102 items)

Updated barberCB 10/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.