On the usefulness of type and liveness accuracy for garbage collection and leak detection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the usefulness of type and liveness accuracy for garbage collection and leak detection

Full text

Pdf (685 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 24 , Issue 6 (November 2002) table of contents

Pages: 593 - 624

Year of Publication: 2002

ISSN:0164-0925

Authors

Martin Hirzel	University of Colorado, Boulder, CO
Amer Diwan	University of Colorado, Boulder, CO
Johannes Henkel	University of Colorado, Boulder, CO

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 50, Citation Count: 10

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

ABSTRACT

The effectiveness of garbage collectors and leak detectors in identifying dead objects depends on the accuracy of their reachability traversal. Accuracy has two orthogonal dimensions: (i) whether the reachability traversal can distinguish between pointers and nonpointers (type accuracy), and (ii) whether the reachability traversal can identify memory locations that will be dereferenced in the future (liveness accuracy). This article presents an experimental study of the importance of type and liveness accuracy for reachability traversals. We show that liveness accuracy reduces the reachable heap size by up to 62% for our benchmark programs. However, the simpler liveness schemes (e.g., intraprocedural analysis of local variables) are largely ineffective for our benchmark runs: one must analyze global variables using interprocedural analysis to obtain significant benefits. Type accuracy has an insignificant impact on a garbage collector's ability to find unreachable objects in our benchmark runs. We report results for programs written in C, C++, and Eiffel.

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	Ole Agesen , David Detlefs , J. Eliot Moss, Garbage collection and local variable type-precision and liveness in Java virtual machines, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.269-279, June 17-19, 1998, Montreal, Quebec, Canada
	2	B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
	3	Andrew W. Appel, A runtime system, Lisp and Symbolic Computation, v.3 n.4, p.343-380, Nov. 1990 [doi>10.1007/BF01807697]
	4	Attanasio, C. R., Bacon, D. F., Cocchi, A., and Smith, S. 2001. A comparative evaluation of parallel garbage collector implementations. In Workshop on Languages and Compilers for Parallel Computing (LCPC), (Aug.).
	5	Bartlett, J. F. 1988. Compacting garbage collection with ambiguous roots. Tech. Rep. 88/2. DEC Western Research Laboratory, Palo Alto, Calif. (Also in LISP Pointers 1, 6 (Apr.-June), 2--12.
	6	Bartlett, J. F. 1989. Mostly-copying garbage collection picks up generations and C++. Tech. Rep. DEC Western Research Laboratory, Palo Alto, Calif.
	7	Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.157-164, June 24-28, 1991, Toronto, Ontario, Canada
	8	Boehm, H.-J., Demers, A. J., and Weiser, M. 2002. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/.
	9	Boehm, H.-J. and Shao, Z. 1993. Inferring type maps during garbage collection. In OOPSLA '93 Workshop on Memory Management and Garbage Collection (Sept.). ACM, New York.
	10	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]
	11	Dominique Colnet , Philippe Coucaud , Olivier Zendra, Compiler support to customize the mark and sweep algorithm, Proceedings of the 1st international symposium on Memory management, p.154-165, October 17-19, 1998, Vancouver, British Columbia, Canada
	12	Dion, J. and Monier, L. 2002. Third degree. http://research.compaq.com/wrl/projects/om/third.html.
	13	Amer Diwan , Eliot Moss , Richard Hudson, Compiler support for garbage collection in a statically typed language, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.273-282, June 15-19, 1992, San Francisco, California, United States
	14	Edison Design Group. 2002. http://www.edg.com.
	15	Robert Fitzgerald , David Tarditi, The case for profile-directed selection of garbage collectors, Proceedings of the 2nd international symposium on Memory management, p.111-120, October 15-16, 2000, Minneapolis, Minnesota, United States
	16	Geodesic Systems. 2002. Great Circle---Real-time error detection and code diagnosis for developers. http://www.geodesic.com/solutions/products_gc_overview.html.
	17	James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
	18	Hastings, R. and Joyce, B. 1992. Fast detection of memory leaks and access errors. In Proceedings of the Winter '92 USENIX Conference, pp. 125--136.
	19	Fergus Henderson, Accurate garbage collection in an uncooperative environment, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
	20	Michael W. Hicks , Jonathan T. Moore , Scott M. Nettles, The measured cost of copying garbage collection mechanisms, Proceedings of the second ACM SIGPLAN international conference on Functional programming, p.292-305, June 09-11, 1997, Amsterdam, The Netherlands
	21	Richard L. Hudson , J. E Moss , Amer Diwan , Christopher F. Weight, A Language-Independent Garbage Collector Toolkit, University of Massachusetts, Amherst, MA, 1991
	22	Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
	23	Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
	24	Greg Nelson, Systems programming with Modula-3, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
	25	Niklas Röjemo , Colin Runciman, Lag, drag, void and use—heap profiling and space-efficient compilation revisited, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.34-41, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	26	Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, On effectiveness of GC in Java, Proceedings of the 2nd international symposium on Memory management, p.12-17, October 15-16, 2000, Minneapolis, Minnesota, United States
	27	Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, Heap profiling for space-efficient Java, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.104-113, June 2001, Snowbird, Utah, United States
	28	Frederick Smith , Greg Morrisett, Comparing mostly-copying and mark-sweep conservative collection, Proceedings of the 1st international symposium on Memory management, p.68-78, October 17-19, 1998, Vancouver, British Columbia, Canada
	29	Stanford University SUIF Research Group. 2002. SUIF compiler system version 1.x. http://suif.stanford.edu/suif/suif1/index.html.
	30	James M. Stichnoth , Guei-Yuan Lueh , Michał Cierniak, Support for garbage collection at every instruction in a Java compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.118-127, May 01-04, 1999, Atlanta, Georgia, United States
	31	D. Tarditi , G. Morrisett , P. Cheng , C. Stone , R. Harper , P. Lee, TIL: a type-directed optimizing compiler for ML, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.181-192, May 21-24, 1996, Philadelphia, Pennsylvania, United States
	32	Mads Tofte, A brief introduction to regions, Proceedings of the 1st international symposium on Memory management, p.186-195, October 17-19, 1998, Vancouver, British Columbia, Canada
	33	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
	34	Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
	35	Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
	36	Benjamin Zorn, The measured cost of conservative garbage collection, Software—Practice & Experience, v.23 n.7, p.733-756, July 1993 [doi>10.1002/spe.4380230704]
	37	Zorn, B. G., 1991. The effect of garbage collection on cache performance. Tech. Rep. CU-CS-528-91. Univ. Colorado at Boulder, Boulder, Col., May.

CITED BY 10

	Luc Moreau , Peter Dickman , Richard Jones, Birrell's distributed reference listing revisited, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.6, p.1344-1395, November 2005
	Chen Ding , Chengliang Zhang , Xipeng Shen , Mitsunori Ogihara, Gated memory control for memory monitoring, leak detection and garbage collection, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois
	Ran Shaham , Eran Yahav , Elliot K. Kolodner , Mooly Sagiv, Establishing local temporal heap safety properties with applications to compile-time memory management, Science of Computer Programming, v.58 n.1-2, p.264-289, October 2005
	Samuel Z. Guyer , Kathryn S. McKinley , Daniel Frampton, Free-Me: a static analysis for automatic individual object reclamation, ACM SIGPLAN Notices, v.41 n.6, June 2006
	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
	Derek Rayside , Lucy Mendel, Object ownership profiling: a technique for finding and fixing memory leaks, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA
	Uday P. Khedker , Amitabha Sanyal , Amey Karkare, Heap reference analysis using access graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.1, p.1-es, November 2007
	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
	Michael D. Bond , Kathryn S. McKinley, Tolerating memory leaks, ACM SIGPLAN Notices, v.43 n.10, September 2008
	Jon Rafkind , Adam Wick , John Regehr , Matthew Flatt, Precise garbage collection for C, Proceedings of the 2009 international symposium on Memory management, June 19-20, 2009, Dublin, Ireland