Article

Estimating the impact of heap liveness information on space consumption in Java

Authors:

Ran Shaham,

Elliot K. Kolodner,

Mooly SagivAuthors Info & Claims

ISMM '02: Proceedings of the 3rd international symposium on Memory management

Pages 64 - 75

https://doi.org/10.1145/512429.512437

Published: 20 June 2002 Publication History

Get Access

Abstract

We study the potential impact of different kinds of liveness information on the space consumption of a program in a garbage collected environment, specifically for Java. The idea is to measure the time difference between the actual time an object is collected by the garbage collector (GC) and the potential earliest time an object could be collected assuming liveness information were available. We focus on the following kinds of liveness information: (i) stack-reference liveness (local reference variable liveness in Java), (ii) global-reference liveness (static reference variable liveness in Java), (iii) heap-reference liveness (instance reference variable liveness or array reference liveness in Java), and (vi) any combination of (i)-(iii). We also provide some insights on the kind of interface between a compiler and GC that could achieve these potential savings.The Java Virtual Machine (JVM) was instrumented to measure (dynamic) liveness information. Experimental results are given for 10 benchmarks, including 5 of the SPEC-jvm98 benchmark suite. We show that in general stack-reference liveness may yield small benefits, global-reference liveness combined with stack-reference liveness may yield medium benefits, and heap-reference liveness yields the largest potential benefit. Specifically, for heap-reference liveness we measure an average potential savings of 39% using an interface with complete liveness information, and an average savings of 15% using a more restricted interface.

References

[1]

O. Agesen, D. Detlefs, and E. Moss. Garbage Collection and Local Variable Type-Precision and Liveness in Java Virtual Machines. In SIGPLAN Conf. on Prog. Lang. Design and Impl., pages 269--279, June 1998]]

Digital Library

Google Scholar

[2]

D. Detlefs and E. Moss, Feb. 2002. Private Communication]]

Google Scholar

[3]

M. Hirzel, A. Diwan, and A. L. Hosking. On the usefulness of liveness for garbage collection and leak detection. In ECOOP, pages 181--206, 2001]]

Digital Library

Google Scholar

[4]

Java Grande Benchmark Suite. Available at http://www.epcc.ed.ac.uk/javagrande]]

Google Scholar

[5]

Sun JDK 1.2. Available at http://java.sun.com/j2se]]

Google Scholar

[6]

T. Lev-Ami and M. Sagiv. TVLA: A framework for kleene based static analysis. In SAS'00, Static Analysis Symposium, pages 280--301. Springer, 2000. Available at "http://www.math.tau.ac.il/~rumster"]]

Digital Library

Google Scholar

[7]

S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann, 1997]]

Digital Library

Google Scholar

[8]

N. Rojemo and C. Runciman. Lag, drag, void and use---heap profiling and space-efficient compilation revisited. In Proceedings of the 1996 ACM SIGPLAN Int. Conf. on Func. Prog., pages 34--41, Philadelphia, Pennsylvania, 24--26 May 1996]]

Digital Library

Google Scholar

[9]

R. Shaham, E. K. Kolodner, and M. Sagiv. Automatic removal of array memory leaks in java. In Int. Conf. on Comp. Construct., pages 50--66, Apr. 2000]]

Digital Library

Google Scholar

[10]

R. Shaham, E. K. Kolodner, and M. Sagiv. On the effectiveness of GC in java. In Int. Symp. on Memory Management, pages 12--17. ACM, Oct. 2000]]

Digital Library

Google Scholar

[11]

R. Shaham, E. K. Kolodner, and M. Sagiv. Heap profiling for space-efficient java. In SIGPLAN Conf. on Prog. Lang. Design and Impl., pages 104--113. ACM, June 2001]]

Digital Library

Google Scholar

[12]

SPEC98. Standard Performance Evaluation Corporation (SPEC), Fairfax, VA, 1998. Available at http://www.spec.org/osg/jvm98/]]

Google Scholar

Cited By

View all

Kumar K. PSanyal AKarkare A(2016)Liveness-based garbage collection for lazy languagesACM SIGPLAN Notices10.1145/3241624.292669851:11(122-133)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/3241624.2926698
Kumar K. PSanyal AKarkare AFlood CZhang Z(2016)Liveness-based garbage collection for lazy languagesProceedings of the 2016 ACM SIGPLAN International Symposium on Memory Management10.1145/2926697.2926698(122-133)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/2926697.2926698
Sonobe TSuenaga KIgarashi A(2014)Automatic Memory Management Based on Program Transformation Using OwnershipProgramming Languages and Systems10.1007/978-3-319-12736-1_4(58-77)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12736-1_4
Show More Cited By

Index Terms

Estimating the impact of heap liveness information on space consumption in Java
1. General and reference
  1. Cross-computing tools and techniques
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Allocation / deallocation strategies
        Garbage collection

Recommendations

Estimating the impact of heap liveness information on space consumption in Java
MSP 2002 and ISMM 2002

We study the potential impact of different kinds of liveness information on the space consumption of a program in a garbage collected environment, specifically for Java. The idea is to measure the time difference between the actual time an object is ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting it frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the risk of not ...
Liveness-based garbage collection for lazy languages
ISMM '16

We consider the problem of reducing the memory required to run lazy first-order functional programs. Our approach is to analyze programs for liveness of heap-allocated data. The result of the analysis is used to preserve only live data—a subset of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISMM '02: Proceedings of the 3rd international symposium on Memory management

June 2002

192 pages

ISBN:1581135394

DOI:10.1145/512429

General Chair:
Hans-J. Boehm
Hewlett-Packard Labs, USA
,
Program Chair:
David Detlefs
Sun Microsystems Labs, USA

ACM SIGPLAN Notices Volume 38, Issue 2 supplement
MSP 2002 and ISMM 2002
February 2003
291 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/773039
Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISMM02

Sponsor:

SIGPLAN

ISMM02: 2002 International Symposium on Memory Management ( co-located with PLDI 2002 )

June 20 - 21, 2002

Berlin, Germany

Acceptance Rates

ISMM '02 Paper Acceptance Rate 17 of 41 submissions, 41%;

Overall Acceptance Rate 72 of 156 submissions, 46%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
411
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kumar K. PSanyal AKarkare A(2016)Liveness-based garbage collection for lazy languagesACM SIGPLAN Notices10.1145/3241624.292669851:11(122-133)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/3241624.2926698
Kumar K. PSanyal AKarkare AFlood CZhang Z(2016)Liveness-based garbage collection for lazy languagesProceedings of the 2016 ACM SIGPLAN International Symposium on Memory Management10.1145/2926697.2926698(122-133)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/2926697.2926698
Sonobe TSuenaga KIgarashi A(2014)Automatic Memory Management Based on Program Transformation Using OwnershipProgramming Languages and Systems10.1007/978-3-319-12736-1_4(58-77)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12736-1_4
Qian JZhou X(2012)Inferring weak references for fixing Java memory leaksProceedings of the 2012 IEEE International Conference on Software Maintenance (ICSM)10.1109/ICSM.2012.6405323(571-574)Online publication date: 23-Sep-2012
https://dl.acm.org/doi/10.1109/ICSM.2012.6405323
Khedker USanyal ASathe B(2010)ReferencesData Flow Analysis10.1201/9780849332517.bmatt(371-378)Online publication date: 13-Jan-2010
https://doi.org/10.1201/9780849332517.bmatt
Liang PTripp ONaik MSagiv M(2010)A dynamic evaluation of the precision of static heap abstractionsACM SIGPLAN Notices10.1145/1932682.186949445:10(411-427)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869494
Liang PTripp ONaik MSagiv MCook WClarke SRinard MSullivan KSteinberg D(2010)A dynamic evaluation of the precision of static heap abstractionsProceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/1869459.1869494(411-427)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1869459.1869494
Kiciman ELivshits B(2010)AjaxScopeACM Transactions on the Web10.1145/1841909.18419104:4(1-52)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1841909.1841910
Albert EGenaim SGómez-Zamalloa M(2010)Parametric inference of memory requirements for garbage collected languagesACM SIGPLAN Notices10.1145/1837855.180667145:8(121-130)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1837855.1806671
Petricek TSyme D(2010)Collecting hollywood's garbageACM SIGPLAN Notices10.1145/1837855.180666245:8(53-62)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1837855.1806662
Show More Cited By

View Options

Login options

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

Cited By

Index Terms

Recommendations

Estimating the impact of heap liveness information on space consumption in Java

Controlling garbage collection and heap growth to reduce the execution time of Java applications

Liveness-based garbage collection for lazy languages