Garbage collection in a large LISP system

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Garbage collection in a large LISP system

Full text

Pdf (1.25 MB)

Source

Conference on LISP and Functional Programming archive
Proceedings of the 1984 ACM Symposium on LISP and functional programming table of contents

Austin, Texas, United States

Pages: 235 - 246

Year of Publication: 1984

ISBN:0-89791-142-3

Author

David A. Moon

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 17, Downloads (12 Months): 73, Citation Count: 90

Additional Information:

abstract references cited by index terms collaborative colleagues

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/800055.802040 What is a DOI?

ABSTRACT

This paper discusses garbage collection techniques used in a high-performance Lisp implementation with a large virtual memory, the Symbolics 3600. Particular attention is paid to practical issues and experience. In a large system problems of scale appear and the most straightforward garbage-collection techniques do not work well. Many of these problems involve the interaction of the garbage collector with demand-paged virtual memory. Some of the solutions adopted in the 3600 are presented, including incremental copying garbage collection, approximately depth-first copying, ephemeral objects, tagged architecture, and hardware assists. We discuss techniques for improving the efficiency of garbage collection by recognizing that objects in the Lisp world have a variety of lifetimes. The importance of designing the architecture and the hardware to facilitate garbage collection is stressed.

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	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 [doi>10.1145/359460.359470]
	2	C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
	3	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	4	L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
	5	Hayashi, H., Hattori, A., and Akimoto, H. ALPHA: High-Performance Lisp Machine equipped with a New Stack Structure and Real Time Garbage Collection System. Fujitsu Laboratories, Ltd. draft report.
	6	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 [doi>10.1145/358141.358147]
	7	David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984

CITED BY 90

	Tamar Domani , Elliot K. Kolodner , Erez Petrank, A generational on-the-fly garbage collector for Java, ACM SIGPLAN Notices, v.35 n.5, p.274-284, May 2000
	Benjamin Zorn, Comparing mark-and sweep and stop-and-copy garbage collection, Proceedings of the 1990 ACM conference on LISP and functional programming, p.87-98, June 27-29, 1990, Nice, France
	Douglas Johnson, Trap architectures for Lisp systems, Proceedings of the 1990 ACM conference on LISP and functional programming, p.79-86, June 27-29, 1990, Nice, France
	Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, Age-based garbage collection, ACM SIGPLAN Notices, v.34 n.10, p.370-381, Oct. 1999
	D. R. Chase, Safety consideration for storage allocation optimizations, ACM SIGPLAN Notices, v.23 n.7, p.1-10, July 1988
	José M. Piquer, Indirect distributed garbage collection: handling object migration, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.5, p.615-647, Sept. 1996
	David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, ACM SIGPLAN Notices, v.28 n.6, p.187-196, June 1993
	Tony Printezis , Alex Garthwaite, Visualising the train garbage collector, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Mark B. Reinhold, Cache performance of garbage-collected programs, ACM SIGPLAN Notices, v.29 n.6, p.206-217, June 1994
	Tim Brecht , Eshrat Arjomandi , Chang Li , Hang Pham, Controlling garbage collection and heap growth to reduce the execution time of Java applications, ACM SIGPLAN Notices, v.36 n.11, p.353-366, 11/01/2001
	Ravi Sharma , Mary Lou Soffa, Parallel generational garbage collection, ACM SIGPLAN Notices, v.26 n.11, p.16-32, Nov. 1991
	Henry G. Baker, Unify and conquer, Proceedings of the 1990 ACM conference on LISP and functional programming, p.218-226, June 27-29, 1990, Nice, France
	Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States
	David D. Clark, The structuring of systems using upcalls, ACM SIGOPS Operating Systems Review, v.19 n.5, p.171-180, Dec. 1-4, 1985
	Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, ACM SIGPLAN Notices, v.37 n.5, May 2002
	William J. Schmidt , Kelvin D. Nilsen, Performance of a hardware-assisted real-time garbage collector, ACM SIGPLAN Notices, v.29 n.11, p.76-85, Nov. 1994
	Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Caching considerations for generational garbage collection, ACM SIGPLAN Lisp Pointers, v.V n.1, p.32-42, Jan. 1992
	Elliot K. Kolodner , William E. Weihl, Atomic incremental garbage collection and recovery for a large stable heap, ACM SIGMOD Record, v.22 n.2, p.177-186, June 1, 1993
	Guy L. Steele, Jr. , Richard P. Gabriel, The evolution of Lisp, ACM SIGPLAN Notices, v.28 n.3, p.231-270, March 1993
	Damien Doligez , Xavier Leroy, A concurrent, generational garbage collector for a multithreaded implementation of ML, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.113-123, March 1993, Charleston, South Carolina, United States
	Martin Hirzel , Johannes Henkel , Amer Diwan , Michael Hind, Understanding the connectivity of heap objects, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.34 n.5, p.104-117, May 1999
	William D. Clinger , Lars T. Hansen, Generational garbage collection and the radioactive decay model, ACM SIGPLAN Notices, v.32 n.5, p.97-108, May 1997
	Trishul M. Chilimbi , James R. Larus, Using generational garbage collection to implement cache-conscious data placement, ACM SIGPLAN Notices, v.34 n.3, p.37-48, March 1999
	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
	Elliot Kolodner , Barbara Liskov , William Weihl, Atomic garbage collection: managing a stable heap, ACM SIGMOD Record, v.18 n.2, p.15-25, June 1989
	Michael W. Hicks , Jonathan T. Moore , Scott M. Nettles, The measured cost of copying garbage collection mechanisms, ACM SIGPLAN Notices, v.32 n.8, p.292-305, Aug. 1997
	Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
	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
	Patrick M. Sansom , Simon L. Peyton Jones, Generational garbage collection for Haskell, Proceedings of the conference on Functional programming languages and computer architecture, p.106-116, June 09-11, 1993, Copenhagen, Denmark
	James R. Allard , Lowell B. Hawkinson, Real-time programming in Common Lisp, Communications of the ACM, v.34 n.9, p.64-69, Sept. 1991
	Trishul M. Chilimbi , Mark D. Hill , James R. Larus, Cache-conscious structure layout, ACM SIGPLAN Notices, v.34 n.5, p.1-12, May 1999
	Barry Hayes, Using key object opportunism to collect old objects, ACM SIGPLAN Notices, v.26 n.11, p.33-46, Nov. 1991
	Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, ACM SIGPLAN Notices, v.33 n.11, p.12-23, Nov. 1998
	David A. Barrett , Benjamin G. Zorn, Garbage collection using a dynamic threatening boundary, ACM SIGPLAN Notices, v.30 n.6, p.301-314, June 1995
	Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
	Yefim Shuf , Manish Gupta , Hubertus Franke , Andrew Appel , Jaswinder Pal Singh, Creating and preserving locality of java applications at allocation and garbage collection times, ACM SIGPLAN Notices, v.37 n.11, November 2002
	David F. Bacon , Perry Cheng , V. T. Rajan, A real-time garbage collector with low overhead and consistent utilization, ACM SIGPLAN Notices, v.38 n.1, p.285-298, January 2003
	P. R. Wilson , T. G. Moher, Design of the opportunistic garbage collector, ACM SIGPLAN Notices, v.24 n.10, p.23-35, Oct. 1989
	D. Kevin Layer , Chris Richardson, Lisp systems in the 1990s, Communications of the ACM, v.34 n.9, p.48-57, Sept. 1991
	Douglas Johnson, The case for a read barrier, ACM SIGPLAN Notices, v.26 n.4, p.279-287, Apr. 1991
	Paul R. Wilson , Michael S. Lam , Thomas G. Moher, Effective “static-graph” reorganization to improve locality in garbage-collected systems, ACM SIGPLAN Notices, v.26 n.6, p.177-191, June 1991
	A. W. Appel , J. R. Ellis , K. Li, Real-time concurrent collection on stock multiprocessors, ACM SIGPLAN Notices, v.23 n.7, p.11-20, July 1988
	Marco T. Morazán , Douglas R. Troeger , Myles Nash, Paging in a distributed virtual memory, Trends in functional programming, Intellect Books, Exeter, UK, 2002
	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
	Katherine Barabash , Yoav Ossia , Erez Petrank, Mostly concurrent garbage collection revisited, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Suresh Jagannathan , Jim Philbin, A foundation for an efficient multi-threaded scheme system, ACM SIGPLAN Lisp Pointers, v.V n.1, p.345-357, Jan. 1992
	Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, ACM SIGPLAN Notices, v.26 n.4, p.96-107, Apr. 1991
	Satish M. Thatte, Persistent memory: a storage architecture for object-oriented database systems, Proceedings on the 1986 international workshop on Object-oriented database systems, p.148-159, September 23-26, 1986, Pacific Grove, California, United States
	P. R. Wilson , T. G. Moher, Demonic memory for process histories, ACM SIGPLAN Notices, v.24 n.7, p.330-343, July 1989
	Dirk Grunwald , Benjamin Zorn , Robert Henderson, Improving the cache locality of memory allocation, ACM SIGPLAN Notices, v.28 n.6, p.177-186, June 1993
	Mark B. Wells , Margaret A. Hug , Rollo Silver, Libraries as programs preserved within compiler continuations, ACM SIGPLAN Notices, v.20 n.7, p.83-91, July 1985
	Guy E. Blelloch , Perry Cheng, On bounding time and space for multiprocessor garbage collection, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Andrew W. Appel, Real-time concurrent collection on stock multiprocessors, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Yoav Ossia , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Avi Owshanko, A parallel, incremental and concurrent GC for servers, ACM SIGPLAN Notices, v.37 n.5, May 2002
	Guy L. Steele , Richard P. Gabriel, The evolution of Lisp, History of programming languages---II, ACM Press, New York, NY, 1996
	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
	Matthew Hertz , Yi Feng , Emery D. Berger, Garbage collection without paging, ACM SIGPLAN Notices, v.40 n.6, June 2005
	David F. Bacon , Perry Cheng , David Grove , Martin T. Vechev, Syncopation: generational real-time garbage collection in the metronome, ACM SIGPLAN Notices, v.40 n.7, July 2005
	Katherine Barabash , Ori Ben-Yitzhak , Irit Goft , Elliot K. Kolodner , Victor Leikehman , Yoav Ossia , Avi Owshanko , Erez Petrank, A parallel, incremental, mostly concurrent garbage collector for servers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1097-1146, November 2005
	Ting Yang , Matthew Hertz , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, Automatic heap sizing: taking real memory into account, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Matthias Meyer, A Novel Processor Architecture with Exact Tag-Free Pointers, IEEE Micro, v.24 n.3, p.46-55, March 2004
	Matthias Meyer, A true hardware read barrier, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Christian Queinnec, Dynamic extent objects, ACM SIGPLAN Lisp Pointers, v.2 n.1, p.11-21, July-August-September 1988
	Henry G. Baker, CONS should not CONS its arguments, or, a lazy alloc is a smart alloc, ACM SIGPLAN Notices, v.27 n.3, p.24-34, March 1992
	Timothy J. McEntee, Overview of garbage collection in symbolic computing, ACM SIGPLAN Lisp Pointers, v.1 n.3, p.8-16, August-September 1987
	Henry G. Baker, Efficient implementation of bit-vector operation in Common Lisp, ACM SIGPLAN Lisp Pointers, v.III n.2-4, p.8-22, April-June 1990
	Antony L. Hosking, Portable, mostly-concurrent, mostly-copying garbage collection for multi-processors, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Katherine Barabash , Niv Buchbinder , Tamar Domani , Elliot K. Kolodner , Yoav Ossia , Shlomit S. Pinter , Janice Shepherd , Ron Sivan , Victor Umansky, Mostly accurate stack scanning, Proceedings of the Java^TM Virtual Machine Research and Technology Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.19-19, April 23-24, 2001, Monterey, California
	William D. Clinger , Fabio V. Rojas, Linear combinations of radioactive decay models for generational garbage collection, Science of Computer Programming, v.62 n.2, p.184-203, 1 October 2006
	Wen-ke Chen , Sanjay Bhansali , Trishul Chilimbi , Xiaofeng Gao , Weihaw Chuang, Profile-guided proactive garbage collection for locality optimization, ACM SIGPLAN Notices, v.41 n.6, June 2006
	David Siegwart , Martin Hirzel, Improving locality with parallel hierarchical copying GC, Proceedings of the 2006 international symposium on Memory management, June 10-11, 2006, Ottawa, Ontario, Canada
	Martin Hirzel, Data layouts for object-oriented programs, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
	David Detlefs , Ross Knippel , William D. Clinger , Matthias Jacob, Concurrent Remembered Set Refinement in Generational Garbage Collection, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.13-26, August 01-02, 2002
	Tim Brecht , Eshrat Arjomandi , Chang Li , Hang Pham, Controlling garbage collection and heap growth to reduce the execution time of Java applications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.5, p.908-941, September 2006
	Filip Pizlo , Erez Petrank , Bjarne Steensgaard, Path specialization: reducing phased execution overheads, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	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
	David A. Moon, Architecture of the Symbolics 3600, ACM SIGARCH Computer Architecture News, v.13 n.3, p.76-83, June 1985
	Patrick H. Dussud, Lisp hardware architecture: the Explorer II and beyond, ACM SIGPLAN Lisp Pointers, v.1 n.6, p.13-18, April-May-June 1988
	Henry G. Baker, Infant mortality and generational garbage collection, ACM SIGPLAN Notices, v.28 n.4, p.55-57, April 1993
	Henry G. Baker, The Boyer Benchmark at warp speed, ACM SIGPLAN Lisp Pointers, v.V n.3, p.13-14, July-Sept. 1992
	Henry G. Baker, Lively linear Lisp: “look ma, no garbage!”, ACM SIGPLAN Notices, v.27 n.8, p.89-98, Aug. 1992
	Robert Courts, Improving locality of reference in a garbage-collecting memory management system, Communications of the ACM, v.31 n.9, p.1128-1138, Sept. 1988
	Paul R. Wilson, Some issues and strategies in heap management and memory hierarchies, ACM SIGPLAN Notices, v.26 n.3, p.45-52, March 1991
	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
	Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992
	P. R. Wilson , T. G. Moher, A “card-marking” scheme for controlling intergenerational references in generation-based garbage collection on stock hardware, ACM SIGPLAN Notices, v.24 n.5, p.87-92, May 1989
	B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, ACM SIGPLAN Notices, v.22 n.7, p.253-263, July 1987
	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
	Michael D. Bond , Kathryn S. McKinley, Leak pruning, ACM SIGPLAN Notices, v.44 n.3, March 2009