More Web Proxy on the site http://driver.im/

research-article

Live heap space analysis for languages with garbage collection

Authors:

Miguel Gómez-Zamalloa GilAuthors Info & Claims

ISMM '09: Proceedings of the 2009 international symposium on Memory management

Pages 129 - 138

https://doi.org/10.1145/1542431.1542450

Published: 19 June 2009 Publication History

Abstract

The peak heap consumption of a program is the maximum size of the live data on the heap during the execution of the program, i.e., the minimum amount of heap space needed to run the program without exhausting the memory. It is well-known that garbage collection (GC) makes the problem of predicting the memory required to run a program difficult. This paper presents, the best of our knowledge, the first live heap space analysis for garbage-collected languages which infers accurate upper bounds on the peak heap usage of a program's execution that are not restricted to any complexity class, i.e., we can infer exponential, logarithmic, polynomial, etc., bounds. Our analysis is developed for an (sequential) object-oriented bytecode language with a scoped-memory manager that reclaims unreachable memory when methods return. We also show how our analysis can accommodate other GC schemes which are closer to the ideal GC which collects objects as soon as they become unreachable. The practicality of our approach is experimentally evaluated on a prototype implementation. We demonstrate that it is fully automatic, reasonably accurate and efficient by inferring live heap space bounds for a standardized set of benchmarks, the JOlden suite.

References

[1]

E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Zanardini. Cost Analysis of Java Bytecode. In Rocco De Nicola, editor, 16th European Symposium on Programming, ESOP'07, volume 4421 of Lecture Notes in Computer Science, pages 157--172. Springer, March 2007.

Digital Library

[2]

E. Albert, P. Arenas, S. Genaim, G. Puebla, and D. Zanardini. COSTA: Design and Implementation of a Cost and Termination Analyzer for Java Bytecode. In Post-proceedings of Formal Methods for Components and Objects (FMCO'07), number 5382 in LNCS, pages 113--133. Springer-Verlag, October 2008.

Digital Library

[3]

E. Albert, S. Genaim, and M. GÓmez-Zamalloa. Heap Space Analysis for Java Bytecode. In ISMM '07: Proceedings of the 6th international symposium on Memory management, pages 105--116, New York, NY, USA, October 2007. ACM Press.

Digital Library

[4]

Bruno Blanchet. Escape Analysis for Object Oriented Languages. Application to Java(TM). In Conference on Object-Oriented Programming, Systems, Languages and Applications (OOPSLA'99), pages 20--34. ACM, November 1999.

Digital Library

[5]

V. Braberman, F. Fernández, D. Garbervetsky, and S. Yovine. Parametric Prediction of Heap Memory Requirements. In Proceedings of the International Symposium on Memory management (ISMM), New York, NY, USA, 2008. ACM.

Digital Library

[6]

Sigmund Cherem and Radu Rugina. Region analysis and transformation for java programs. In David F. Bacon and Amer Diwan, editors, Proceedings of the 4th International Symposium on Memory Management, ISMM 2004, Vancouver, BC, Canada, October 24--25, 2004, pages 85--96. ACM, 2004.

Digital Library

[7]

W.-N. Chin, H. H. Nguyen, S. Qin, and M. C. Rinard. Memory Usage Verification for OO Programs. In Proc. of SAS'05, volume 3672 of LNCS, pages 70--86, 2005.

Digital Library

[8]

W-N. Chin, H.H. Nguyen, C. Popeea, and S. Qin. Analysing Memory Resource Bounds for Low-Level Programs. In Proceedings of the International Symposium on Memory management (ISMM), New York, NY, USA, 2008. ACM.

Digital Library

[9]

P. Cousot and N. Halbwachs. Automatic Discovery of Linear Restraints among Variables of a Program. In ACM Symposium on Principles of Programming Languages (POPL), pages 84--97. ACM Press, 1978.

Digital Library

[10]

K. Crary and S. Weirich. Resource bound certification. In POPL'00. ACM Press, 2000.

Digital Library

[11]

M. Hofmann and S. Jost. Static prediction of heap space usage for first-order functional programs. In ACM Symposium on Principles of Programming Languages (POPL), 2003.

Digital Library

[12]

JOlden Suite Collection. http://www-ali.cs.umass.edu/DaCapo/benchmarks.html.

[13]

H. Lehner and P. Muller. Formal translation of bytecode into BoogiePL. In Bytecode'07, ENTCS, pages 35--50. Elsevier, 2007.

Digital Library

[14]

T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Addison-Wesley, 1996.

Digital Library

[15]

Y. G. Park and B. Goldberg. Escape analysis on lists. In PLDI, pages 116--127, 1992.

Digital Library

[16]

Mads Tofte and Jean--Pierre Talpin. Region-based memory management. Inf. Comput., 132(2):109--176, 1997.

Digital Library

[17]

L. Unnikrishnan, S. D. Stoller, and Y. A. Liu. Automatic Accurate Live Memory Analysis for Garbage-Collected Languages. In Proc. of LCTES/OM, pages 102--111. ACM, 2001.

Digital Library

[18]

L. Unnikrishnan, S. D. Stoller, and Y. A. Liu. Optimized Live Heap Bound Analysis. In Proc. of VMCAI'03, volume 2575 of LNCS, pages 70--85, 2003.

Digital Library

[19]

R. Vallee-Rai, L. Hendren, V. Sundaresan, P. Lam, E. Gagnon, and P. Co. Soot -- a Java optimization framework. In CASCON'99, pages 125--135, 1999.

Digital Library

[20]

B. Wegbreit. Mechanical Program Analysis. Comm. of the ACM, 18(9), 1975.

Digital Library

[21]

John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In PLDI, pages 131--144. ACM, 2004.

Digital Library

[22]

R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. B. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra F. Mueller, I. Puaut, P. P. Puschner, J. Staschulat, and P. Stenström. The worst-case execution-time problem -- overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst., 7(3), 2008.

Digital Library

Cited By

Madiot JPottier F(2022)A separation logic for heap space under garbage collectionProceedings of the ACM on Programming Languages10.1145/34986726:POPL(1-28)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498672
Lu TChang BTrivedi A(2021)Selectively-Amortized Resource BoundingStatic Analysis10.1007/978-3-030-88806-0_14(286-307)Online publication date: 13-Oct-2021
https://doi.org/10.1007/978-3-030-88806-0_14
Sui YCheng XZhang GWang H(2020)Flow2Vec: value-flow-based precise code embeddingProceedings of the ACM on Programming Languages10.1145/34283014:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428301
Show More Cited By

Index Terms

Live heap space analysis for languages with garbage collection
1. Theory of computation
  1. Design and analysis of algorithms
  2. Semantics and reasoning
    1. Program reasoning
      1. Program analysis
    2. Program semantics

Recommendations

Parametric inference of memory requirements for garbage collected languages
ISMM '10: Proceedings of the 2010 international symposium on Memory management

The accurate prediction of program's memory requirements is a critical component in software development. Existing heap space analyses either do not take deallocation into account or adopt specific models of garbage collectors which do not necessarily ...
Parametric inference of memory requirements for garbage collected languages
ISMM '10

The accurate prediction of program's memory requirements is a critical component in software development. Existing heap space analyses either do not take deallocation into account or adopt specific models of garbage collectors which do not necessarily ...
Heap space analysis for java bytecode
ISMM '07: Proceedings of the 6th international symposium on Memory management

This article presents a heap space analysis for (sequential) Java bytecode. The analysis generates heap space cost relations which define at compile-time the heap consumption of a program as a function of its data size. These relations can be used to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISMM '09: Proceedings of the 2009 international symposium on Memory management

June 2009

158 pages

ISBN:9781605583471

DOI:10.1145/1542431

General Chair:
Hillel Kolodner
IBM Haifa Research
,
Program Chair:
Guy Steele
Sun Microsystems Laboratories

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISMM '09

Sponsor:

ISMM '09: International Symposium on Memory Management

June 19 - 20, 2009

Dublin, Ireland

Acceptance Rates

ISMM '09 Paper Acceptance Rate 15 of 32 submissions, 47%;

Overall Acceptance Rate 72 of 156 submissions, 46%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
242
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Madiot JPottier F(2022)A separation logic for heap space under garbage collectionProceedings of the ACM on Programming Languages10.1145/34986726:POPL(1-28)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498672
Lu TChang BTrivedi A(2021)Selectively-Amortized Resource BoundingStatic Analysis10.1007/978-3-030-88806-0_14(286-307)Online publication date: 13-Oct-2021
https://doi.org/10.1007/978-3-030-88806-0_14
Sui YCheng XZhang GWang H(2020)Flow2Vec: value-flow-based precise code embeddingProceedings of the ACM on Programming Languages10.1145/34283014:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428301
Gavran IDarulova EMajumdar R(2020)Interactive synthesis of temporal specifications from examples and natural languageProceedings of the ACM on Programming Languages10.1145/34282694:OOPSLA(1-26)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428269
Atkinson ECarbin M(2020)Programming and reasoning with partial observabilityProceedings of the ACM on Programming Languages10.1145/34282684:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428268
Winterer DZhang CSu Z(2020)On the unusual effectiveness of type-aware operator mutations for testing SMT solversProceedings of the ACM on Programming Languages10.1145/34282614:OOPSLA(1-25)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428261
Trinh MChu DJaffar J(2020)Inter-theory dependency analysis for SMT string solversProceedings of the ACM on Programming Languages10.1145/34282604:OOPSLA(1-27)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428260
Chen XTrinh MRodrigues NPeña LRoşu G(2020)Towards a unified proof framework for automated fixpoint reasoning using matching logicProceedings of the ACM on Programming Languages10.1145/34282294:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428229
Farooq UZhao ZSridharan MNeamtiu I(2020)LiveDroid: identifying and preserving mobile app state in volatile runtime environmentsProceedings of the ACM on Programming Languages10.1145/34282284:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428228
Feldman YKhyzha AEnea CMorrison ANanevski ARinetzky NShoham S(2020)Proving highly-concurrent traversals correctProceedings of the ACM on Programming Languages10.1145/34281964:OOPSLA(1-29)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428196
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.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents