An efficient, incremental, automatic garbage collector

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient, incremental, automatic garbage collector

Full text

Pdf (543 KB)

Source

Communications of the ACM archive
Volume 19 , Issue 9 (September 1976) table of contents

Pages: 522 - 526

Year of Publication: 1976

ISSN:0001-0782

Authors

L. Peter Deutsch	Xerox Palo Alto Research Center, Palo Alto, CA
Daniel G. Bobrow	Xerox Palo Alto Research Center, Palo Alto, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 100, Citation Count: 79

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/360336.360345 What is a DOI?

ABSTRACT

This paper describes a new way of solving the storage reclamation problem for a system such as Lisp that allocates storage automatically from a heap, and does not require the programmer to give any indication that particular items are no longer useful or accessible. A reference count scheme for reclaiming non-self-referential structures, and a linearizing, compacting, copying scheme to reorganize all storage at the users discretion are proposed. The algorithms are designed to work well in systems which use multiple levels of storage, and large virtual address space. They depend on the fact that most cells are referenced exactly once, and that reference counts need only be accurate when storage is about to be reclaimed. A transaction file stores changes to reference counts, and a multiple reference table stores the count for items which are referenced more than once.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bobrow, D.G. Storage management in LISP. In Symbol Manpulation Languages and Techniques, D.G. Bobrow, Ed., North-Holland Pub. Co., Amsterdam, 1968.
	2	Daniel G. Bobrow, A note on hash linking, Communications of the ACM, v.18 n.7, p.413-415, July 1975 [doi>10.1145/360881.360920]
	3	Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
	4	Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
	5	Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
	6	Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
	7	Van der Poel, W.L. A manual of HISP for the PDP-9. U. of Delft, Delft, Netherlands, 1974.

CITED BY 79

	Norihisa Suzuki, Analysis of pointer “rotation”, Communications of the ACM, v.25 n.5, p.330-335, May 1982
	Yasuhiko Yokote , Mario Tokoro, The design and implementation of Concurrent Smalltalk, ACM SIGPLAN Notices, v.21 n.11, p.331-340, Nov. 1986
	Patrick J. Caudill , Allen Wirfs-Brock, A third generation Smalltalk-80 implementation, ACM SIGPLAN Notices, v.21 n.11, p.119-130, Nov. 1986
	Ted Kaehler, Virtual memory on a narrow machine for an object-oriented language, ACM SIGPLAN Notices, v.21 n.11, p.87-106, Nov. 1986
	Norihisa Suzuki, Analysis of pointer rotation, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 28-30, 1980, Las Vegas, Nevada
	David S. Wise, Morris's Garbage Compaction Algorithm Restores Reference Counts, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.115-120, July 1979
	Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977
	Susan Owicki, Making the world safe for garbage collection, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.77-86, January 26-28, 1981, Williamsburg, Virginia
	Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976
	David Chase , Mark Wegman , F. Ken Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Norihisa Suzuki , Minoru Terada, Creating efficient systems for object-oriented languages, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.290-296, January 15-18, 1984, Salt Lake City, Utah, United States
	David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States
	L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States
	David S. Burris , Kurt Schember, Sorting sequential files with limited auxiliary storage, Proceedings of the 18th annual Southeast regional conference, March 24-26, 1980, Tallahassee, Florida
	Richard R. Burton , L. M. Masinter , Daniel G. Bobrow , Willie Sue Haugeland , Ronald M. Kaplan , B. A. Sheil, Overview and status of DoradoLisp, Proceedings of the 1980 ACM conference on LISP and functional programming, p.243-247, August 25-27, 1980, Stanford University, California, United States
	Taehyoun Kim , Naehyuck Chang , Namyun Kim , Heonshik Shin, Scheduling garbage collector for embedded real-time systems, ACM SIGPLAN Notices, v.34 n.7, p.55-64, July 1999
	Pramod G. Joisha, Overlooking roots: a framework for making nondeferred reference-counting garbage collection fast, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	Barry Hayes, Ephemerons: a new finalization mechanism, ACM SIGPLAN Notices, v.32 n.10, p.176-183, Oct. 1997
	Ashwin Ram , Janak H. Patel, Parallel garbage collection without synchronization overhead, ACM SIGARCH Computer Architecture News, v.13 n.3, p.84-90, June 1985
	L. Peter Deutsch, Experience with a microprogrammed Interlisp system, ACM SIGMICRO Newsletter, v.9 n.4, p.128-129, Dec. 1978
	Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988
	L. Peter Deutsch, ByteLisp and its Alto implementation, Proceedings of the 1980 ACM conference on LISP and functional programming, p.231-242, August 25-27, 1980, Stanford University, California, United States
	Timothy J. McEntee, Overview of garbage collection in symbolic computing, ACM SIGPLAN Lisp Pointers, v.1 n.3, p.8-16, August-September 1987
	David Ungar , Frank Jackson, Tenuring policies for generation-based storage reclamation, ACM SIGPLAN Notices, v.23 n.11, p.1-17, Nov. 1988
	Ralph E. Johnson, Reducing the latency of a real-time garbage collector, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.1, p.46-58, March 1992
	David Gay , Alex Aiken, Memory management with explicit regions, ACM SIGPLAN Notices, v.33 n.5, p.313-323, May 1998
	B. Goldberg, Generational reference counting: a reduced-communication distributed storage reclamation scheme, ACM SIGPLAN Notices, v.24 n.7, p.313-321, July 1989
	Wolfgang Puffitsch, Decoupled root scanning in multi-processor systems, Proceedings of the 2008 international conference on Compilers, architectures and synthesis for embedded systems, October 19-24, 2008, Atlanta, GA, USA
	Guy Lewis Steele, Jr. , Gerald Jay Sussman, Design of a LISP-based microprocessor, Communications of the ACM, v.23 n.11, p.628-645, Nov. 1980
	Young Gil Park , Benjamin Goldberg, Reference escape analysis: optimizing reference counting based on the lifetime of references, ACM SIGPLAN Notices, v.26 n.9, p.178-189, Sept. 1991
	Hirotoshi Maegawa, Memory organization and management for linked data structures, Proceedings of the 19th annual conference on Computer Science, p.105-112, April 1991, San Antonio, Texas, United States
	David S. Wise , Joshua Walgenbach, Static and dynamic partitioning of pointers as links and threads, ACM SIGPLAN Notices, v.31 n.6, p.42-49, June 15, 1996
	Bernard Lang , Christian Queinnec , José Piquer, Garbage collecting the world, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.39-50, January 19-22, 1992, Albuquerque, New Mexico, United States
	Paul R. Wilson, Pointer swizzling at page fault time: efficiently supporting huge address spaces on standard hardware, ACM SIGARCH Computer Architecture News, v.19 n.4, p.6-13, June 1991
	David Ungar , Frank Jackson, An adaptive tenuring policy for generation scavengers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.1, p.1-27, Jan. 1992
	Hiromu Hayashi , Akira Hattori , Haruo Akimoto, ALPHA-a high-performance LISP machine equipped with a new stack structure and garbage collection system, ACM SIGARCH Computer Architecture News, v.11 n.3, p.342-348, June 1983
	David S. Wise , Brian Heck , Caleb Hess , Willie Hunt , Eric Ost, Research Demonstration of a Hardware Reference-Counting Heap, Lisp and Symbolic Computation, v.10 n.2, p.159-181, July 1997
	Gurindar S. Sohi , Edward S. Davidson , Janak H. Patel, An efficient LISP-execution architecture with a new representation for list structures, ACM SIGARCH Computer Architecture News, v.13 n.3, p.91-98, June 1985
	David J. Roth , David S. Wise, One-bit counts between unique and sticky, ACM SIGPLAN Notices, v.34 n.3, p.49-56, March 1999
	David Gay , Rob Ennals , Eric Brewer, Safe manual memory management, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	Paul Griffin , Witawas Srisa-an , J. Morris Chang, An energy efficient garbage collector for java embedded devices, ACM SIGPLAN Notices, v.40 n.7, July 2005
	David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
	Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983
	Butler W. Lampson, Hints for computer system design, ACM SIGOPS Operating Systems Review, v.17 n.5, p.33-48, October 1983
	Daniel C. Swinehart , Polle T. Zellweger , Robert B. Hagmann, The structure of Cedar, ACM SIGPLAN Notices, v.20 n.7, p.230-244, July 1985
	Margaret H. Butler, Storage reclamation in object oriented database systems, ACM SIGMOD Record, v.16 n.3, p.410-425, Dec. 1987
	Hans-J. Boehm, The space cost of lazy reference counting, ACM SIGPLAN Notices, v.39 n.1, p.210-219, January 2004
	Daniel H. H. Ingalls, The Smalltalk-76 programming system design and implementation, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.9-16, January 23-25, 1978, Tucson, Arizona
	Gabriel Kliot , Erez Petrank , Bjarne Steensgaard, A lock-free, concurrent, and incremental stack scanning for garbage collectors, Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 11-13, 2009, Washington, DC, USA
	Pramod G. Joisha, A principled approach to nondeferred reference-counting garbage collection, Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments, March 05-07, 2008, Seattle, WA, USA
	Lars T. Hansen , William D. Clinger, An experimental study of renewal-older-first garbage collection, ACM SIGPLAN Notices, v.37 n.9, p.247-258, September 2002
	Matthew Hertz , Stephen M. Blackburn , J. Eliot B. Moss , Kathryn S. McKinley , Darko Stefanović, Generating object lifetime traces with Merlin, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.3, p.476-516, May 2006
	Pramod G. Joisha, Compiler optimizations for nondeferred reference: counting garbage collection, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	David F. Bacon , Clement R. Attanasio , Han B. Lee , V. T. Rajan , Stephen Smith, Java without the coffee breaks: a nonintrusive multiprocessor garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.92-103, May 2001
	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
	Daniel C. Swinehart , Polle T. Zellweger , Richard J. Beach , Robert B. Hagmann, A structural view of the Cedar programming environment, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.4, p.419-490, Oct. 1986
	Daniel G. Bobrow , Douglas W. Clark, Compact Encodings of List Structure, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.266-286, Oct. 1979
	Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978
	Harel Paz , David F. Bacon , Elliot K. Kolodner , Erez Petrank , V. T. Rajan, An efficient on-the-fly cycle collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.4, p.20-es, August 2007
	Henry G. Baker, Minimizing reference count updating with deferred and anchored pointers for functional data structures, ACM SIGPLAN Notices, v.29 n.9, p.38-43, Sept. 1994
	Cliff Click , Gil Tene , Michael Wolf, The pauseless GC algorithm, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA
	Yossi Levanoni , Erez Petrank, An on-the-fly reference counting garbage collector for Java, ACM SIGPLAN Notices, v.36 n.11, p.367-380, 11/01/2001
	Yossi Levanoni , Erez Petrank, An on-the-fly reference-counting garbage collector for java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.1-69, January 2006
	Stephen M Blackburn , Kathryn S. McKinley, In or out?: putting write barriers in their place, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Nikhil Swamy , Michael Hicks , Greg Morrisett , Dan Grossman , Trevor Jim, Safe manual memory management in cyclone, Science of Computer Programming, v.62 n.2, p.122-144, 1 October 2006
	B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.253-263, July 1987
	Yefim Shuf , Manish Gupta , Rajesh Bordawekar , Jaswinder Pal Singh, Exploiting prolific types for memory management and optimizations, ACM SIGPLAN Notices, v.37 n.1, p.295-306, Jan. 2002
	Stephen M. Blackburn , Kathryn S. McKinley, Ulterior reference counting: fast garbage collection without a long wait, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
	David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, ACM SIGPLAN Notices, v.39 n.10, October 2004
	Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
	J. P. Sansonnet , M. Castan , C. Percebois , D. Botella , J. Perez, Direct execution of lisp on a list_directed architecture, ACM SIGARCH Computer Architecture News, v.10 n.2, p.132-139, March 1982
	David Chase , Mark Wegman , F. Ken Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
	Guy L. Steele, Jr. , Richard P. Gabriel, The evolution of Lisp, ACM SIGPLAN Notices, v.28 n.3, p.231-270, March 1993
	Guy L. Steele , Richard P. Gabriel, The evolution of Lisp, History of programming languages---II, ACM Press, New York, NY, 1996
	Saleh E. Abdullahi , Graem A. Ringwood, Garbage collecting the Internet: a survey of distributed garbage collection, ACM Computing Surveys (CSUR), v.30 n.3, p.330-373, Sept. 1998
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994
	B Wah , G J Li, Survey on special purpose computer architectures for AI, ACM SIGART Bulletin

INDEX TERMS

Keywords:
Lisp, garbage collection, storage management

Collaborative Colleagues:

L. Peter Deutsch: colleagues

Daniel G. Bobrow: colleagues

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player