A concurrent, generational garbage collector for a multithreaded implementation of ML

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A concurrent, generational garbage collector for a multithreaded implementation of ML

Full text

Pdf (1.01 MB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Charleston, South Carolina, United States

Pages: 113 - 123

Year of Publication: 1993

ISBN:0-89791-560-7

Authors

Damien Doligez
Xavier Leroy

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 65, Citation Count: 53

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

ABSTRACT

This paper presents the design and implementation of a “quasi real-time” garbage collector for Concurrent Caml Light, an implementation of ML with threads. This two-generation system combines a fast, asynchronous copying collector on the young generation with a non-disruptive concurrent marking collector on the old generation. This design crucially relies on the ML compile-time distinction between mutable and immutable objects.

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	Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
	2	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
	3	A. W. Appel and K. Li. Virtual memory primitives for user programs. Technical Report CS-TR-276- 90, Princeton University, 1990.
	4	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]
	5	Mordechai Ben-Ari, Algorithms for on-the-fly garbage collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.333-344, July 1984 [doi>10.1145/579.587]
	6	B. Berthomieu. Implementing CCS: the LCS experiment. Technical report 89425, LAAS, Dec. 1989.
	7	Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
	8	Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
	9	E. C. Cooper and R. P. Draves. C threads. Technical report CMU-CS-88-154, Carnegie Mellon University, 1988.
	10	G. Cousineau , P.-L. Curien, The categorical abstract machine, Science of Computer Programming, v.8 n.2, p.173-202, April 1, 1987 [doi>10.1016/0167-6423(87)90020-7]
	11	Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
	12	Robert H. Halstead, Jr., Implementation of multilisp: Lisp on a multiprocessor, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.9-17, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802017]
	13	Tim Hickey , Jacques Cohen, Performance analysis of on-the-fly garbage collection, Communications of the ACM, v.27 n.11, p.1143-1154, Nov. 1984 [doi>10.1145/1968.358298]
	14	H. T. Kung and S. W. Song. An efficient parallel garbage collection system and its correctness proof. In Foundations of Computer Science 1977, pages 120-131. IEEE Computer Society Press, 1977.
	15	X. Leroy. The ZINC experiment: an economical implementation of the ML language. Technical report 117, INRIA, 1990.
	16	X. Leroy and M. Mauny. The Caml Light system, version 0.5 documentation and user's guide. Technical report L-5, INRIA, 1992.
	17	Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
	18	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 [doi>10.1145/800055.802040]
	19	J. G Morrisett , Andrew Tolmach, A Portable Multiprocessor Interface for Standard ML of New Jersey, Carnegie Mellon University, Pittsburgh, PA, 1992
	20	S. C. North , J. H. Reppy, Concurrent garbage collection on stock hardware, Proc. of a conference on Functional programming languages and computer architecture, p.113-133, October 1987, Portland, Oregon, United States
	21	Laurence C. Paulson, ML for the working programmer, Cambridge University Press, New York, NY, 1991
	22	John H. Reppy, CML: A higher concurrent language, ACM SIGPLAN Notices, v.26 n.6, p.293-305, June 1991
	23	Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
	24	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 53

	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
	Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, ACM SIGPLAN Notices, v.36 n.5, p.125-136, May 2001
	Toshio Endo , Kenjiro Taura, Reducing pause time of conservative collectors, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Richard L. Hudson , J. Eliot B. Moss, Sapphire: copying GC without stopping the world, Proceedings of the 2001 joint ACM-ISCOPE conference on Java Grande, p.48-57, June 2001, Palo Alto, California, United States
	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
	Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis-guided allocation and low-pause incremental garbage collection in a concurrent language, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Damien Doligez , Georges Gonthier, Portable, unobtrusive garbage collection for multiprocessor systems, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.70-83, January 16-19, 1994, Portland, Oregon, United States
	Tamar Domani , Gal Goldshtein , Elliot K. Kolodner , Ethan Lewis , Erez Petrank , Dafna Sheinwald, Thread-local heaps for Java, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	Olin Shivers , James W. Clark , Roland McGrath, Atomic heap transactions and fine-grain interrupts, ACM SIGPLAN Notices, v.34 n.9, p.48-59, Sept. 1999
	D. Scott Alexander , Marianne Shaw , Scott M. Nettles , Jonathan M. Smith, Active bridging, ACM SIGCOMM Computer Communication Review, v.27 n.4, p.101-111, Oct. 1997
	Fabrice Le Fessant , Ian Piumarta , Marc Shapiro, An implementation of complete, asynchronous, distributed garbage collection, ACM SIGPLAN Notices, v.33 n.5, p.152-161, May 1998
	Lorenz Huelsbergen , James R. Larus, A concurrent copying garbage collector for languages that distinguish (im)mutable data, ACM SIGPLAN Notices, v.28 n.7, p.73-82, July 1993
	James O'Toole , Scott Nettles, Concurrent replicating garbage collection, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.34-42, July-Sept. 1994
	Lorenz Huelsbergen , Phil Winterbottom, Very concurrent mark-&-sweep garbage collection without fine-grain synchronization, ACM SIGPLAN Notices, v.34 n.3, p.166-175, March 1999
	Scott Nettles , James O'Toole, Real-time replication garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.217-226, June 1993
	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
	Adnan Agbaria , Roy Friedman, Virtual-machine-based heterogeneous checkpointing, Software—Practice & Experience, v.32 n.12, p.1175-1192, October 2002
	H.-W. Loidl , F. Rubio , N. Scaife , K. Hammond , S. Horiguchi , U. Klusik , R. Loogen , G. J. Michaelson , R. Peña , S. Priebe , Á J. Rebón , P. W. Trinder, Comparing Parallel Functional Languages: Programming and Performance, Higher-Order and Symbolic Computation, v.16 n.3, p.203-251, September 2003
	Katherine Barabash , Yoav Ossia , Erez Petrank, Mostly concurrent garbage collection revisited, ACM SIGPLAN Notices, v.38 n.11, November 2003
	Sara Porat , Marina Biberstein , Larry Koved , Bilha Mendelson, Automatic detection of immutable fields in Java, Proceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research, p.10, November 13-16, 2000, Mississauga, Ontario, Canada
	Hezi Azatchi , Yossi Levanoni , Harel Paz , Erez Petrank, An on-the-fly mark and sweep garbage collector based on sliding views, ACM SIGPLAN Notices, v.38 n.11, November 2003
	A. M. Cheadle , A. J. Field , S. Marlow , S. L. Peyton Jones , R. L. While, Non-stop Haskell, ACM SIGPLAN Notices, v.35 n.9, p.257-267, Sept. 2000
	Erik Johansson , Konstantinos Sagonas , Jesper Wilhelmsson, Heap architectures for concurrent languages using message passing, ACM SIGPLAN Notices, v.38 n.2 supplement, February 2003
	David Detlefs , Christine Flood , Steve Heller , Tony Printezis, Garbage-first garbage collection, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Yoav Ossia , Ori Ben-Yitzhak , Marc Segal, Mostly concurrent compaction for mark-sweep GC, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	David F. Bacon , Perry Cheng , V. T. Rajan, A unified theory of garbage collection, ACM SIGPLAN Notices, v.39 n.10, October 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
	Toshio Endo , Kenjiro Taura , Akinori Yonezawa, A scalable mark-sweep garbage collector on large-scale shared-memory machines, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 15-21, 1997, San Jose, CA
	Martin C. Rinard , Pedro C. Diniz, Eliminating synchronization bottlenecks using adaptive replication, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.3, p.316-359, May 2003
	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
	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
	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
	H. Gao , J. F. Groote , W. H. Hesselink, Lock-free parallel and concurrent garbage collection by mark&sweep, Science of Computer Programming, v.64 n.3, p.341-374, February, 2007
	Alfonso Sánchez , Luís Veiga , Paulo Ferreira, Distributed garbage collection for wide area replicated memory, Proceedings of the 6th conference on USENIX Conference on Object-Oriented Technologies and Systems, p.5-5, January 29-February 02, 2001, San Antonia, Texas
	Konstantinos Sagonas , Jesper Wilhelmsson, Efficient memory management for concurrent programs that use message passing, Science of Computer Programming, v.62 n.2, p.98-121, 1 October 2006
	Richard Carlsson , Konstantinos Sagonas , Jesper Wilhelmsson, Message analysis for concurrent programs using message passing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.4, p.715-746, July 2006
	Martin T. Vechev , Eran Yahav , David F. Bacon, Correctness-preserving derivation of concurrent garbage collection algorithms, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Anil Madhavapeddy , Alex Ho , Tim Deegan , David Scott , Ripduman Sohan, Melange: creating a "functional" internet, ACM SIGOPS Operating Systems Review, v.41 n.3, 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
	Okehee Goh , Yann-Hang Lee , Ziad Kaakani , Elliott Rachlin, Schedulable garbage collection in CLI virtual execution system, Real-Time Systems, v.36 n.1-2, p.47-74, July 2007
	R. M. Muthukumar , D. Janakiram, Yama: A Scalable Generational Garbage Collector for Java in Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.17 n.2, p.148-159, February 2006
	Filip Pizlo , Erez Petrank , Bjarne Steensgaard, A study of concurrent real-time garbage collectors, ACM SIGPLAN Notices, v.43 n.6, June 2008
	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
	Fridtjof Siebert, Limits of parallel marking garbage collection, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Matthew Fluet , Nic Ford , Mike Rainey , John Reppy , Adam Shaw , Yingqi Xiao, Status report: the manticore project, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany
	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
	Filip Pizlo , Daniel Frampton , Erez Petrank , Bjarne Steensgaard, Stopless: a real-time garbage collector for multiprocessors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada
	Matthew Fluet , Mike Rainey , John Reppy, A scheduling framework for general-purpose parallel languages, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Simon Marlow , Tim Harris , Roshan P. James , Simon Peyton Jones, Parallel generational-copying garbage collection with a block-structured heap, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA
	Wolfgang Puffitsch , Martin Schoeberl, Non-blocking root scanning for real-time garbage collection, Proceedings of the 6th international workshop on Java technologies for real-time and embedded systems, September 24-26, 2008, Santa Clara, California
	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
	Cosmin E. Oancea , Alan Mycroft , Stephen M. Watt, A new approach to parallelising tracing algorithms, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland