Topic:
dangling pointers
Topic:
finalization of data
Topic:
heap memory management
Topic:
memory management by age
Topic:
memory management by reference counting
Topic:
safe use of pointers
| |
Summary
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 
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
| 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
Quote: drawback of garbage-collection is that its overhead appears only during long runs
[»wolfW9_1989]
|
Related Topics
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)
|
