Article

Free access

Garbage collection and local variable type-precision and liveness in Java virtual machines

Authors:

J. Eliot MossAuthors Info & Claims

PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation

Pages 269 - 279

https://doi.org/10.1145/277650.277738

Published: 01 May 1998 Publication History

Abstract

Full precision in garbage collection implies retaining only those heap allocated objects that will actually be used in the future. Since full precision is not computable in general, garbage collectors use safe (i.e., conservative) approximations such as reachability from a set of root references. Ambiguous roots collectors (commonly called "conservative") can be overly conservative because they overestimate the root set, and thereby retain unexpectedly large amounts of garbage. We consider two more precise collection schemes for Java virtual machines (JVMs). One uses a type analysis to obtain a type-precise root set (only those variables that contain references); the other adds a live variable analysis to reduce the root set to only the live reference variables. Even with the Java programming language's strong typing, it turns out that the JVM specification has a feature that makes type-precise root sets difficult to compute. We explain the problem and ways in which it can be solved.Our experimental results include measurements of the costs of the type and liveness analyses at load time, of the incremental benefits at run time of the liveness analysis over the type analysis alone, and of various map sizes and counts. We find that the liveness analysis often produces little or no improvement in heap size, sometimes modest improvements, and occasionally the improvement is dramatic. While further study is in order, we conclude that the main benefit of the liveness analysis is preventing bad surprises.

References

[1]

Shail Aditya, Christine Flood, and James Hicks. Garbage collection for strongly-typed languages using run-time type reconstruction. In {LFP, 1994}, pp. 12-23.

Digital Library

[2]

Ole Agesen and David Detlefs. Finding references in Java stacks. Tech. Rep. SMI~E-97-67, Sun Microsystems Laboratories, Chelmsford, MA, USA, Oct. 1997. Presented at the OOPSLA '97 workshop on garbage collection.

[3]

Ole Age,sen, Stephen Freund, and John C. Mitchell. Adding type parameterization to Java. In Proceedings of the ACM SIGPLAN Conference on Object-Oriented Programming Systems, lxmguages and Applications (OOPSLA-97) (New York, Oct.5-9 1997), vol. 32, 10 of ACM SIGPLAN Notices, ACM Press, pp. 49--65.

Digital Library

[4]

Andrew W. Appel. Runtime tags aren't necessary. L/sp and Symbolic Computation 2 (1989), 153-162.

[5]

Andrew W. Appel. Compiling with Continuations. Cambridge University Press, 1992, ch. 16, pp. 205-214.

Digital Library

[6]

Andrew W. Appel and David R. Hanson. Copying garbage collection in the presence of ambiguous references. Tech. Rep. CS-TR- 162-88, Princeton University, 1988.

[7]

Henry G. Baker. Unify and conquer (garbage, updating, aliasing .. ) in functional languages. In Conference Record of the 1990 ACM Symposium on Lisp and Functional Programming (Nice, France, June 1990), ACM Press, pp. 218-226.

Digital Library

[8]

Jeffrey M. Barth. Shifting garbage collection overhead to compile time. Communications ofthe ACM 20, 7 (July 1977), 513-518.

Digital Library

[9]

Joel E Bartlett. Compacting garbage collection with ambiguous roots. Tech. Rep. 88/2, DEC Western Research Laboratory, Palo Alto, CA, Feb. 1988. Also in Lisp Pointers 1, 6 (April-June 1988), pp. 2-12.

Digital Library

[10]

Joel F. Bartlett. Mostly-Copying garbage collection picks up generations and C++. Technical note, DEC Western Research Laboratory, Palo Alto, CA, Oct. 1989. Sources available in ftp://gatekeeper, dec.com/pub/DEC/CCgc.

[11]

Hans-Juergen Boehm. Simple GC-safe compilation. In OOPSA/ECOOP '91 Workshop on Garbage Collection in Object-Oriented Systems (Oct. 1991), Paul R. Wilson and Barry Hayes, Eds.

Digital Library

[12]

Hans-Juergen Boehm. Space efficient conservative garbage collection. In Proceedings of SIGPLAN'93 Conference on Programming Languages Design and Implementation (Albuquerque, New Mexico, June 1993), vol. 28(6) of ACM SIGPLAN Notices, ACM Press, pp. 197-206.

Digital Library

[13]

Hans-Juergen Boehm. Simple garbage-collector safety. In {PLDI, 1996}, pp. 89-98.

Digital Library

[14]

Hans-Juergen Boehm and David R. Chase. A proposal for garbage-collector-safe C compilation. Journal of C Language Translation (1992), 126-141.

[15]

Hans-Juergen Boehm and Zhong Shao. inferring type maps during garbage collection. In OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems (Oct. 1993), Eliot Moss, Paul R. Wilson, and Benjamin Zorn, Eds.

[16]

Hans-Juergen Boehm and Mark Weiser. Garbage collection in an uncooperative environment. Software Practice and Experience 18, 9 (1988), 807-820.

Digital Library

[17]

P. Branquart and J. Lewi. A scheme of storage allocation and garbage collection for Algol-68. In {Peck, 1971}, pp. 198-238.

[18]

Dianne Ellen Bfitton. Heap storage management for the programming language Pascal. Master's thesis, University of Arizona, 1975.

[19]

Maurice Bruynooghe. Compile-time garbage collection or How to transform programs in an assignment-free language into code with assignments. In Program specification and transformation. The IFiP TC2/WG 2.1 Working Conference, Bad To~ Germany, L. G. L. T. Meertens, Ed. North-Holland, Amsterdam, April 15-I7, 1986 1987, pp. 113-129.

Digital Library

[20]

David Chase, Nov. 1997. Personal communication.

[21]

David R. Chase. Garbage collection and other optimizations. Tech. rep., Rice University, Aug. 1987.

[22]

David R. Chase. Safety considerations for storage allocation optimizations. ACM SIGPLANNotices 23, 7 (1988), I-I0.

Digital Library

[23]

David R. Chase, Wegman, and Zadeck. Analysis of pointers and structures. ACM SlGPLANNotices 25, 6 (1990).

Digital Library

[24]

A. Deutsch. On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications. In Conference Record of the Seventeenth Annual A CM Symposium on Principles of Programming Ixmguages (San Francisco, CA, Jan. 1990), ACM SIGPLAN Notices, ACM Press, pp. 157 - 168.

Digital Library

[25]

Amer Diwan, J. Eliot B. Moss, and Richard L. Hudson. Compiler support for garbage collection in a statically typed language. In Proceedings of SIGPLAN'92 Conference on Programming Languages Design and Implementation (San Francisco, CA, June 1992), vol. 27 of ACM SIGPLANNotices, ACM Press, pp. 273-282.

Digital Library

[26]

Ian Foster and William Winsborough. Copy avoidance through compile-time analysis and local reuse. In Procee&'ngs of International Logic Programming Sympsium (1991), pp. 455--469.

[27]

Pascal Fradet. Collecting more garbage, in {LFP, 1994}, pp. 24-33.

Digital Library

[28]

Benjamin Goldberg. Tag-free garbage collection for strongly typed programming languages. ACM SIGPLAN Notices 26, 6 (1991), 165-176.

Digital Library

[29]

Benjamin Goldberg and Michael Gloger. Polymorphic type reconstruction for garbage collection without tags. In Conference Record of the 1992 ACM Symposium on Lisp and Functional Programming (San Francisco, CA, June 1992), ACM Press, pp. 53-65.

Digital Library

[30]

James Gosling. Java intermediate bytecodes. In Proceedings of the ACM $1GPLAN Workshop on Intermediate Representations (IR '95) (Jan. 1995), pp. 111-118. Published as ACM SIGPLAN Notices 30(3), March 1995.

Digital Library

[31]

James Gosling, Bill Joy, and Guy Steele. The Java Language Specification. Addison-Wesley, 1996.

Digital Library

[32]

G.W. Hamilton. Compile-Time Optirnisation of Store Usage in Lazy Funtional Programs. PhD thesis, University of StirUng, 1993.

[33]

G.W. Hamilton. Compile-time garbage collection for lazy functional languages. In Proceedings of International Workshop on Memory Matmgement (Dept. of Computer Science, Keele University, Sept. 1995), Henry Baker, Ed., Lecture Notes in Computer Science, Springer-Verlag.

Digital Library

[34]

G.W. Hamilton and Simon B. Jones. Compile-time garbage collection by necessity analysis. In {Peyton Jones et al., 1991}, pp. 66-70.

[35]

Lucy Hederman. Compile-time garbage collection using reference count analysis. Master's thesis, Rice University, Aug. 1988. Also Rice University Technical Report TR88-75 lint, according to Rice University's technical report list, this report is no longer available for distribution.

[36]

James Hicks. Experiences with compiler-directed storage reclamation. In Record of the 1993 Conference on Functional Programming and Computer Architecture (Motorola Cambridge Research Center, June 1993), R. John M. Hughes, Ed., vol. 523 of Lecture Notes in Computer Science, Springer-Verlag.

Digital Library

[37]

Paul R. Hudak. A semantic model of reference counting and its abstraction (detailed summary), in Conference Record of the 1986 A CM Symposium on Lisp and Functional Programming (Cambridge, MA, Aug. 1986), ACM SIGPLAN Notices, ACM Press, pp. 351-363.

Digital Library

[38]

Paul R. Hudak. A semantic model of reference counting and its abstraction. In Abstract Interpretation of Declarative Languages, Samson Abramsky and Chris Hankin, Eds. Ellis Horward, 1987, pp. 45--62.

[39]

Simon Hughes. Compile-time garbage collection for higher-order functional languages. Journal of Logic and Computation 2, 4 (Aug. 1992), 483-509. Special Issue on Abstract Interpretation.

[40]

Katsuro Inoue, Hiroyuki Seki, and Hikaru Yagi. Analysis of functional programs to detect run-time garbage cells. ACM Transactions on Programming Languages and Systems I0, 4 (Oct. 1988), 555-578.

Digital Library

[41]

Thomas P. lensen and Torben Mogensen. A backwards analysis for compile-time garbage collection. In E$OP'90 3rd European Symposium on Programming, Copenhagen, Denmark, May 1990. (Lecture Notes in Computer Science, voL 432) (1990), Neff D. Jones, Ed., Springer-Verlag, pp. 227-239.

Digital Library

[42]

Simon B. Jones. An experiment in compile time garbage collection. Tech. Rep. 84, Programming Methodology Group, Gtteborg University and Chalmers University of Technology, Jan. 1995.

[43]

Simon B. Jones and D. le Mttayer. Compile-time garbage collection by sharing analysis. In Record of the 1989 Conference on Functional Programming and Computer Architecture (Imperial College, London, Aug. 1989), ACM Press, pp. 54--74.

Digital Library

[44]

Simon B. Jones and Andrew S. Tyas. The implementer's dilemma: A mathematical model of compile-time garbage collection. In Sixth Annual Glasgow Workshop on Functional Programming (1993), Workshops in Computer Science, Springer-Verlag, pp. 139-144.

[45]

Simon B. Jones and M. White. Is compile time garbage collection worth the effort. In {Peyton Jones et aL, 1991}, pp. 172-176.

[46]

Conference Record of the 1994 ACM Symposium on Lisp and Functional Programming (June 1994), ACM Press.

[47]

Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification. Addison-Wesley, 1996.

Digital Library

[48]

Markus Mohnen. Efficient compile-time garbage collection for arbitrary data structures. Tech. Rep. 95-08, University of Aachen, May 1995. Also in Seventh International Symposium on Programming Languages, Implementations, Logics and Programs, PLILP95.

Digital Library

[49]

Anne Mulkers. Live Data Structures in Logic Programs. No. 675 in Lecture Notes in Computer Science. Springer-Verlag, 1993.

Digital Library

[50]

Anne Mulkers, William Winsborough, and Maurice Bmynooghe. Live-structure analysis for Prolog. ACM Transactions on Programming Languages and Systems 16, 2 (Mar. 1994).

Digital Library

[51]

J.E.L. Peck, Ed. Algol--68 implementation. North-Holland, Amsterdam, 1971.

Digital Library

[52]

Simon L. Peyton Jones, G. Hutton, and C. K. Hols, Eds. Third Annual Glasgow Workshop on Functional Programming (1991), Springer-Verlag.

[53]

Proceedings of SlGPLAN'96 Conference on Programming Languages Design and Implementation (1996), ACM SIGPLAN Notices, ACM Press.

[54]

Zhong Shao and Andrew W. Appel. Space-efficient closure representations. In {LFP, 1994}, pp. 150-161.

Digital Library

[55]

David Tarditi, Greg Motrisett, Perry Cheng, Chris Stone, Robert Harper, and Peter Lee. TIL: A type-directed optimizing compiler for ML. In {PLDI, 1996}.

Digital Library

[56]

Stephen Thomas. Garbage collection in shared-environment closure reducers: Space-efficient depth first copying using a tailored approach. Information Processing Letters 56, 1 (Oct. 1995), 1-7.

Digital Library

[57]

Stephen P. Thomas. The Pragmatics of Closure Reduction. PhD thesis, The Computing Laboratory, University of Kent at Canterbury, Oct. 1993.

[58]

Stephen P. Thomas and Richard E. Jones. Garbage collection for shared environment closure reducers. Tech. rep., University of Kent and University of Nottingham, Dec. 1994.

[59]

Andrew Tolmach. Tag-free garbage collection using explicit type parameters. In Proceedings of SIGPLAN'94 Conference on Programming Languages Design and Implementation (Orlando, Florida, June 1994), vol. 29 of ACM SlGPLANNotices, ACM Press, pp. 1-11. Also Lisp Pointers VIIi 3, July-September 1994.

Digital Library

[60]

Philip L. Wadler. Listlessness is better than laziness: Lazy evaluation and garbage collection at compile time. In Conference RecoM of the 1984 ACM Symt~sium on Lisp and Functional Programming (Austin, Texas, Aug. 1984), Guy L. Steele, Ed., ACM Press, pp. 45-52.

Digital Library

[61]

E.P. Wentworth. Pitfalls of conservative garbage collection. Software Practice and Experience 20, 7 (1990), 719--727.

Digital Library

[62]

P.L. Woden. Methods of garbage collection for Algol--68. In {Peck, 1971}, pp. 245-262.

Cited By

Wanninger NMcMichen TCampanoni SDinda PTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651326
Yuan YWang YWang RChowhury RTai CKim N(2021)QEI: Query Acceleration Can be Generic and Efficient in the Cloud2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA51647.2021.00040(385-398)Online publication date: Feb-2021
https://doi.org/10.1109/HPCA51647.2021.00040
Bansal AGoel SShah PSanyal AKumar PDing CMaas M(2020)Garbage collection using a finite liveness domainProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397208(1-15)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397208
Show More Cited By

Index Terms

Garbage collection and local variable type-precision and liveness in Java virtual machines
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Garbage collection and local variable type-precision and liveness in Java virtual machines

Full precision in garbage collection implies retaining only those heap allocated objects that will actually be used in the future. Since full precision is not computable in general, garbage collectors use safe (i.e., conservative) approximations such as ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation

May 1998

357 pages

ISBN:0897919874

DOI:10.1145/277650

Chairmen:
Jack W. Davidson
Univ. of Virginia
,
Keith D. Cooper
Rice Univ. Houston, TX
,
Editor:
A. Michael Berman
Rowan Univ. Glassboro, NJ

ACM SIGPLAN Notices Volume 33, Issue 5
May 1998
358 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/277652
Chairmen:
Jack W. Davidson
Univ. of Virginia
,
Keith D. Cooper
Rice Univ., Houston, TX
,
Editor:
A. Michael Berman
Rowan Univ., Glassboro, NJ
Issue’s Table of Contents

Copyright © 1998 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI98

Sponsor:

SIGPLAN

PLDI98: Conference on Programming Language

June 17 - 19, 1998

Quebec, Montreal, Canada

Acceptance Rates

PLDI '98 Paper Acceptance Rate 31 of 136 submissions, 23%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

55
Total Citations
View Citations
1,307
Total Downloads

Downloads (Last 12 months)154
Downloads (Last 6 weeks)30

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wanninger NMcMichen TCampanoni SDinda PTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Getting a Handle on Unmanaged MemoryProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651326(448-463)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651326
Yuan YWang YWang RChowhury RTai CKim N(2021)QEI: Query Acceleration Can be Generic and Efficient in the Cloud2021 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA51647.2021.00040(385-398)Online publication date: Feb-2021
https://doi.org/10.1109/HPCA51647.2021.00040
Bansal AGoel SShah PSanyal AKumar PDing CMaas M(2020)Garbage collection using a finite liveness domainProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397208(1-15)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397208
Shahriyar RBlackburn SMcKinley K(2014)Fast conservative garbage collectionACM SIGPLAN Notices10.1145/2714064.266019849:10(121-139)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660198
Shahriyar RBlackburn SMcKinley KBlack AMillstein T(2014)Fast conservative garbage collectionProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660198(121-139)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660198
Liang SSun WMight MKeep AHorn D(2014)Pruning, Pushdown Exception-Flow AnalysisProceedings of the 2014 IEEE 14th International Working Conference on Source Code Analysis and Manipulation10.1109/SCAM.2014.44(265-274)Online publication date: 28-Sep-2014
https://dl.acm.org/doi/10.1109/SCAM.2014.44
Ricci NGuyer SMoss J(2013)Elephant tracksACM SIGPLAN Notices10.1145/2555670.246648448:11(109-118)Online publication date: 20-Jun-2013
https://dl.acm.org/doi/10.1145/2555670.2466484
Ricci NGuyer SMoss JCheng PPetrank E(2013)Elephant tracksProceedings of the 2013 international symposium on memory management10.1145/2491894.2466484(109-118)Online publication date: 20-Jun-2013
https://dl.acm.org/doi/10.1145/2491894.2466484
Ricci NGuyer SMoss JCheng PPetrank E(2013)Elephant tracksProceedings of the 2013 international symposium on memory management10.1145/2464157.2466484(109-118)Online publication date: 20-Jun-2013
https://dl.acm.org/doi/10.1145/2464157.2466484
Ishizaki KOgasawara TCastanos JNagpurkar PEdelsohn DNakatani T(2012)Adding dynamically-typed language support to a statically-typed language compilerACM SIGPLAN Notices10.1145/2365864.215104747:7(169-180)Online publication date: 3-Mar-2012
https://dl.acm.org/doi/10.1145/2365864.2151047
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents