Compiler support for garbage collection in a statically typed language

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compiler support for garbage collection in a statically typed language

Full text

Pdf (1.03 MB)

Source

Conference on Programming Language Design and Implementation archive
Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation table of contents

San Francisco, California, United States

Pages: 273 - 282

Year of Publication: 1992

ISBN:0-89791-475-9

Also published in ...

Authors

Amer Diwan
Eliot Moss
Richard Hudson

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 29, Citation Count: 24

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

ABSTRACT

We consider the problem of supporting compacting garbage collection in the presence of modern compiler optimizations. Since our collector may move any heap object, it must accurately locate, follow, and update all pointers and values derived from pointers. To assist the collector, we extend the compiler to emit tables describing live pointers, and values derived from pointers, at each program location where collection may occur. Significant results include identification of a number of problems posed by optimizations, solutions to those problems, a working compiler, and experimental data concerning table sizes, table compression, and time overhead of decoding tables during collection. While gc support can affect the code produced, our sample programs show no significant changes, the table sizes are a modest fraction of the size of the optimized code, and stack tracing is a small fraction of total gc time. Since the compiler enhancements are also modest, we conclude that the approach is practical.

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	Malcolm Atkinson , Ken Chisholm , Paul Cockshott, PS-algol: an algol with a persistent heap, ACM SIGPLAN Notices, v.17 n.7, July 1982 [doi>10.1145/988376.988378]
	2	Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
	3	J. E Moss, Implementing Persistence for an Object Oriented Language, University of Massachusetts, Amherst, MA, 1987
	4	A.L. Hosking, "Main memory management for persistence," Oct. 1991. Position paper for OOPSLA '91 Workshop on Garbage Collection.
	5	J. F. Bartlett,"Compacting garbage collection with ambiguous roots," Research Report 88/2, Western Research Laboratory, Digital Equipment Corporation, Feb. 1988.
	6	J. F. Bartlett, "Mostly-copying garbage collection picks up generations and C++," Technical Note TN. 12, Western Research Laboratory, Digital Equipment Corporation, Palo Alto, CA 94301, Oct. 1989.
	7	R.M. Stallman, GCC. Free Software Foundation, Cambridge, MA.
	8	Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
	9	Craig Chambers , David Ungar, Making pure object-oriented languages practical, ACM SIGPLAN Notices, v.26 n.11, p.1-15, Nov. 1991
	10	S. Harbison. Personal Communication, 1992.
	11	Richard P. Gabriel, Performance and evaluation of LISP systems, Massachusetts Institute of Technology, Cambridge, MA, 1985
	12	A. L. Hosking, J. E. B. Moss, and D. Stefanovid, "A comparative performance evaluation of write barrier implementations." Submitted for publication, Feb. 1992.
	13	H.-j. Boehm, "A proposal for GC-safe C compilation," Oct. 1991. Position paper for OOPSLA '91 Workshop on Garbage Collection.
	14	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
	15	Richard L. Hudson , J. E Moss , Amer Diwan , Christopher F. Weight, A Language-Independent Garbage Collector Toolkit, University of Massachusetts, Amherst, MA, 1991
	16	P. Branquart and J. Lewi, "A scheme for storage allocation and garbage collection in Algol-68," in Algol 68 Implementation (J. E. L. Peck, ed.), North-Holland Publishing Company, 1971.
	17	Benjamin Goldberg, Tag-free garbage collection for strongly typed programming languages, ACM SIGPLAN Notices, v.26 n.6, p.165-176, June 1991
	18	H.-J. Boehm, "Personal communication," July 1991.
	19	A. Diwan, "Exception handling in Modula-3." Internal OOS Document, 1990.
	20	L. W. Zurawski and R. E. Johnson, "Debugging optimized code with expected behavior," ACM Trans. Programming Languages and Systems, To appear.

CITED BY 24

	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
	Andrew W. Appel, Book review: Garbage Collection: Algorithms for Automatic Dynamic Memory Management by Richard Jones and Rafael Lins, John Wiley & Sons, 1996., Journal of Functional Programming, v.7 n.2, p.227-229, March 1997
	Michael Franz , Deepak Chandra , Andreas Gal , Vivek Haldar , Fermín Reig , Ning Wang, A portable Virtual Machine target for Proof-Carrying Code, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.24-31, June 12-12, 2003, San Diego, California
	Michael Franz , Deepak Chandra , Andreas Gal , Vivek Haldar , Christian W. Probst , Fermín Reig , Ning Wang, A portable virtual machine target for proof-carrying code, Science of Computer Programming, v.57 n.3, p.275-294, September 2005
	James M. Stichnoth , Guei-Yuan Lueh , Michał Cierniak, Support for garbage collection at every instruction in a Java compiler, ACM SIGPLAN Notices, v.34 n.5, p.118-127, May 1999
	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
	Fridtjof Siebert, Realtime garbage collection in the JamaicaVM 3.0, Proceedings of the 5th international workshop on Java technologies for real-time and embedded systems, September 26-28, 2007, Vienna, Austria
	Gor V. Nishanov , Sibylle Schupp, Garbage collection in generic libraries, ACM SIGPLAN Notices, v.34 n.3, p.86-96, March 1999
	Kelvin D. Nilsen , William J. Schmidt, Cost-effective object space management for hardware-assisted real-time garbage collection, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.338-354, Dec. 1992
	B. Steensgaard , E. Jul, Object and native code thread mobility among heterogeneous computers (includes sources), ACM SIGOPS Operating Systems Review, v.29 n.5, p.68-77, Dec. 3, 1995
	Daniel C. Wang , Andrew W. Appel, Type-preserving garbage collectors, ACM SIGPLAN Notices, v.36 n.3, p.166-178, March 2001
	Rasmus Pedersen , Martin Schoeberl, Exact roots for a real-time garbage collector, Proceedings of the 4th international workshop on Java technologies for real-time and embedded systems, October 11-13, 2006, Paris, France
	John R. Ellis , David L. Detlefs, Safe, efficient garbage collection for C++, Proceedings of the 6th conference on USENIX Sixth C++ Technical Conference, p.9-9, April 11-14, 1994, Cambridge, MA
	Hans-J. Boehm, Simple garbage-collector-safety, ACM SIGPLAN Notices, v.31 n.5, p.89-98, May 1996
	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
	Martin Hirzel , Amer Diwan , Johannes Henkel, On the usefulness of type and liveness accuracy for garbage collection and leak detection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.593-624, November 2002
	Dominique Colnet , Philippe Coucaud , Olivier Zendra, Compiler support to customize the mark and sweep algorithm, ACM SIGPLAN Notices, v.34 n.3, p.154-165, March 1999
	D. Tarditi , G. Morrisett , P. Cheng , C. Stone , R. Harper , P. Lee, TIL: a type-directed optimizing compiler for ML, ACM SIGPLAN Notices, v.31 n.5, p.181-192, May 1996
	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
	Sunil Soman , Chandra Krintz, Application-specific garbage collection, Journal of Systems and Software, v.80 n.7, p.1037-1056, July, 2007
	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
	Ole Agesen , David Detlefs , J. Eliot Moss, Garbage collection and local variable type-precision and liveness in Java virtual machines, ACM SIGPLAN Notices, v.33 n.5, p.269-279, May 1998
	Antony L. Hosking , Jiawan Chen, Mostly-copying reachability-based orthogonal persistence, ACM SIGPLAN Notices, v.34 n.10, p.382-398, Oct. 1999
	David Tarditi , Greg Morrisett , Perry Cheng , Chris Stone , Robert Harper , Peter Lee, TIL: a type-directed, optimizing compiler for ML, ACM SIGPLAN Notices, v.39 n.4, April 2004