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

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

• Aditya et al., 1994: Shail Aditya , Christine H. Flood , James E. Hicks, Garbage collection for strongly-typed languages using run-time type reconstruction, Proceedings of the 1994 ACM conference on LISP and functional programming, p.12-23, June 27-29, 1994, Orlando, Florida, United States
• Agesen & Detlefs, 1997: 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.
• Agesen et al., 1997: Ole Agesen , Stephen N. Freund , John C. Mitchell, Adding type parameterization to the Java language, ACM SIGPLAN Notices, v.32 n.10, p.49-65, Oct. 1997
• Appel, 1989: Andrew W. Appel. Runtime tags aren't necessary. L/sp and Symbolic Computation 2 (1989), 153-162.
• Appel, 1992: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• Appel & Hanson, 1988: 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.
• Baker, 1990: 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 [doi>10.1145/91556.91652]
• Barth, 1977: Jeffrey M. Barth, Shifting garbage collection overhead to compile time, Communications of the ACM, v.20 n.7, p.513-518, July 1977 [doi>10.1145/359636.359713]
• Bartlett, 1988: 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.
• Bartlett, 1989: 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.
• Boehm, 1991: Paul R. Wilson , Barry Hayes, Garbage collection in object oriented systems, Addendum to the proceedings on Object-oriented programming systems, languages, and applications (Addendum), p.63-71, October 06-11, 1991, Phoenix, Arizona, United States
• Boehm, 1993: Hans-Juergen Boehm, Space efficient conservative garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.197-206, June 1993
• Boehm, 1996: Hans-J. Boehm, Simple garbage-collector-safety, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.89-98, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• Boehm & Chase, 1992: Hans-Juergen Boehm and David R. Chase. A proposal for garbage-collector-safe C compilation. Journal of C Language Translation (1992), 126-141.
• Boehm & Shao, 1993: 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.
• Boehm & Weiser, 1988: 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]
• Branquart & Lewi, 1971: P. Branquart and J. Lewi. A scheme of storage allocation and garbage collection for Algol-68. In {Peck, 1971}, pp. 198-238.
• Britton, 1975: Dianne Ellen Bfitton. Heap storage management for the programming language Pascal. Master's thesis, University of Arizona, 1975.
• Bruynooghe, 1987: M. Bruynooghe, Compile-time garbage collection or How to transform programs in an assignment-free language into code with assignments, The IFIP TC2/WG 2.1 Working Conference on Program specification and transformation, p.113-129, June 1987, Bad To:9Ailz, Germany
• Chase, 1997: David Chase, Nov. 1997. Personal communication.
• Chase, 1987: David R. Chase. Garbage collection and other optimizations. Tech. rep., Rice University, Aug. 1987.
• Chase, 1988: D. R. Chase, Safety consideration for storage allocation optimizations, ACM SIGPLAN Notices, v.23 n.7, p.1-10, July 1988
• Chase et al., 1990: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
• Deutsch, 1990: Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
• Diwan et al., 1992: 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
• Foster & Winsborough, 1991: 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.
• Fradet, 1994: Pascal Fradet, Collecting more garbage, Proceedings of the 1994 ACM conference on LISP and functional programming, p.24-33, June 27-29, 1994, Orlando, Florida, United States
• Goldberg, 1991: Benjamin Goldberg, Tag-free garbage collection for strongly typed programming languages, ACM SIGPLAN Notices, v.26 n.6, p.165-176, June 1991
• Goldberg & Gloger, 1992: Benjamin Goldberg , Michael Gloger, Polymorphic type reconstruction for garbage collection without tags, Proceedings of the 1992 ACM conference on LISP and functional programming, p.53-65, June 22-24, 1992, San Francisco, California, United States
• Gosling, 1995: James Gosling, Java intermediate bytecodes: ACM SIGPLAN workshop on intermediate representations (IR'95), ACM SIGPLAN Notices, v.30 n.3, p.111-118, March 1993
• Gosling et al., 1996: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• Hamilton, 1993: G.W. Hamilton. Compile-Time Optirnisation of Store Usage in Lazy Funtional Programs. PhD thesis, University of StirUng, 1993.
• Hamilton, 1995: G. W. Hamilton, Compile-Time Garbage Collection for Lazy Functional Languages, Proceedings of the International Workshop on Memory Management, p.119-144, September 27-29, 1995
• Hamilton & Jones, 1991: G.W. Hamilton and Simon B. Jones. Compile-time garbage collection by necessity analysis. In {Peyton Jones et al., 1991}, pp. 66-70.
• Hederman, 1988: 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.
• Hicks, 1993: James Hicks, Experiences with compiler-directed storage reclamation, Proceedings of the conference on Functional programming languages and computer architecture, p.95-105, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165194]
• Hudak, 1986: Paul Hudak, A semantic model of reference counting and its abstraction (detailed summary), Proceedings of the 1986 ACM conference on LISP and functional programming, p.351-363, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319876]
• Hudak, 1987: 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.
• Hughes, 1992: 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.
• Inoue et al., 1988: Katsuro Inoue , Hiroyuki Seki , Hikaru Yagi, Analysis of functional programs to detect run-time garbage cells, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.4, p.555-578, Oct. 1988 [doi>10.1145/48022.48025]
• Jensen & Mogensen, 1990: T. P. Jensen , T. Æ Mogensen, A backwards analysis for compile-time garbage collection, Proceedings of the third European symposium on programming on ESOP '90, p.227-239, May 1990, Copenhagen, Denmark
• Jones, 1995: 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.
• Jones & le Métayer, 1989: Simon B. Jones , Daniel Le Métayer, Compile-time garbage collection by sharing analysis, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.54-74, September 11-13, 1989, Imperial College, London, United Kingdom [doi>10.1145/99370.99375]
• Jones & Tyas, 1993: 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.
• Jones & White, 1991: Simon B. Jones and M. White. Is compile time garbage collection worth the effort. In {Peyton Jones et aL, 1991}, pp. 172-176.
• LFP, 1994: Conference Record of the 1994 ACM Symposium on Lisp and Functional Programming (June 1994), ACM Press.
• Lindholm & Yellin, 1996: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• Mohnen, 1995: Markus Mohnen, Efficient Compile-Time Garbage Collection for Arbitrary Data Structures, Proceedings of the 7th International Symposium on Programming Languages: Implementations, Logics and Programs, p.241-258, September 20-22, 1995
• Mulkers, 1993: Anne Mulkers, Live Data Structures in Logic Programs, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• Mulkers et al., 1994: Anne Mulkers , William Winsborough , Maurice Bruynooghe, Live-structure dataflow analysis for Prolog, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.2, p.205-258, March 1994 [doi>10.1145/174662.174664]
• Peck, 1971: J. E. L. Peck, ALGOL Sixty-Eight Implementation, Elsevier Science Inc., New York, NY, 1971
• Peyton Jones et al., 1991: Simon L. Peyton Jones, G. Hutton, and C. K. Hols, Eds. Third Annual Glasgow Workshop on Functional Programming (1991), Springer-Verlag.
• PLDI, 1996: Proceedings of SlGPLAN'96 Conference on Programming Languages Design and Implementation (1996), ACM SIGPLAN Notices, ACM Press.
• Shao & Appel, 1994: Zhong Shao , Andrew W. Appel, Space-efficient closure representations, Proceedings of the 1994 ACM conference on LISP and functional programming, p.150-161, June 27-29, 1994, Orlando, Florida, United States
• Tarditi et al., 1996: 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
• Thomas, 1995: Stephen Thomas, Garbage collection in shared-environment closure reducers: space-efficient depth first copying using a tailored approach, Information Processing Letters, v.56 n.1, p.1-7, Oct. 13, 1995 [doi>10.1016/0020-0190(95)00131-U]
• Thomas, 1993: Stephen P. Thomas. The Pragmatics of Closure Reduction. PhD thesis, The Computing Laboratory, University of Kent at Canterbury, Oct. 1993.
• Thomas & Jones, 1994: 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.
• Tolmach, 1994: Andrew Tolmach, Tag-free garbage collection using explicit type parameters, ACM SIGPLAN Lisp Pointers, v.VII n.3, p.1-11, July-Sept. 1994
• Wadler, 1984: Philip Wadler, Listlessness is better than laziness: Lazy evaluation and garbage collection at compile-time, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.45-52, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802020]
• Wentworth, 1990: E. P. Wentworth, Pitfalls of conservation garbage collection, Software—Practice & Experience, v.20 n.7, p.719-727, July 1990 [doi>10.1002/spe.4380200707]
• Woden, 1971: P.L. Woden. Methods of garbage collection for Algol--68. In {Peck, 1971}, pp. 245-262.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Java

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Experimentation, Measurement, Performance, Verification