skip to main content
10.1145/1375634.1375655acmconferencesArticle/Chapter ViewAbstractPublication PagesismmConference Proceedingsconference-collections
research-article

Parametric prediction of heap memory requirements

Published: 07 June 2008 Publication History

Abstract

This work presents a technique to compute symbolic polynomial approximations of the amount of dynamic memory required to safely execute a method without running out of memory, for Javalike imperative programs. We consider object allocations and deallocations made by the method and the methods it transitively calls. More precisely, given an initial configuration of the stack and the heap, the peak memory consumption is the maximum space occupied by newly created objects in all states along a run from it. We over-approximate the peak memory consumption using a scopedmemory management where objects are organized in regions associated with the lifetime of methods. We model the problem of computing the maximum memory occupied by any region configuration as a parametric polynomial optimization problem over a polyhedral domain and resort to Bernstein basis to solve it. We apply the developed tool to several benchmarks.

References

[1]
P. Abdulla, B. Jonsson, M. Nilsson, M. Saksena. A survey of regular model checking. CONCUR'04, LNCS 3170, 2004.
[2]
E. Albert, P. Arenas, S. Genaim, G. Puebla, D. Zanardini. Cost analysis of java bytecode. ESOP'07, LNCS 4421, 2007.
[3]
E. Albert, S. Genaim, M. Góomez-Zamalloa. Heap space analysis for java bytecode. ISMM'07, ACM 2007.
[4]
D. Bacon, P. Cheng, D. Grove. Garbage collection for embedded systems. EMSOFT'04, ACM 2004.
[5]
G. Barthe, M. Pavlova, G. Schneider. Precise analysis of memory consumption using program logics. SEFM'05. IEEE 2005.
[6]
G. Bollella, J. Gosling. The Real-Time Specification for Java. Addison-Wesley Longman Publishing Co., Inc., 2000.
[7]
V. Braberman, D. Garbervetsky, S. Yovine. A static analysis for synthesizing parametric specifications of dynamic memory consumption. JOT 5(5):31--58, 2006.
[8]
B. Cahoon, K. S. McKinley. Data flow analysis for software prefetching linked data structures in Java. PACT'01, IEEE 2001.
[9]
S. Cherem, R. Rugina. Region analysis and transformation for Java programs. ISMM'04, ACM 2004.
[10]
W. Chin, S. Khoo, S. Qin, C. Popeea, H. Nguyen. Verifying safety policies with size properties and alias controls. ICSE'05, ACM 2005.
[11]
W. Chin, H. H. Nguyen, S. Qin, M. Rinard. Memory usage verification for oo programs. SAS'05, LNCS 3672, 2005.
[12]
W.N. Chin, H.H. Nguyen, C. Popeea, S. Qin Analysing memory resource bounds for low-level programs. In ISMM'08, 2008.
[13]
Ph. Clauss, I. Tchoupaeva. A symbolic approach to Bernstein expansion for program analysis and optimization. CC'04, 2004.
[14]
Ph. Clauss, F. Fernández, D. Garbervetsky, S. Verdoolaege. Symbolic polynomial maximization over convex sets and its application to memory requirement estimation. TR06-04, Univ. L. Pasteur, 2006.
[15]
D. Detlefs. A hard look at hard real-time garbage collection. ISORC'04, IEEE 2004.
[16]
M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S. Tschantz, C. Xiao. The Daikon system for dynamic detection of likely invariants. Sci. Comput. Program. 69(1-3): 35--45, 2007.
[17]
D. Garbervetsky. Parametric specification of dymamic memory utilization. Ph.D Thesis, DC, FCEyN, UBA, November 2007.
[18]
D. Gay, A. Aiken. Language support for regions.PLDI'01, ACM 2001.
[19]
O. Gheorghioiu. Statically determining memory consumption of real-time java threads. MEng, MIT, 2002.
[20]
M. Hofman, S. Jost. Static prediction of heap usage for first-order functional programs. POPL'03, ACM 2003.
[21]
M. Hofman, S. Jost. Type-based amortised heap-space analysis. In ESOP'06. 2006.
[22]
J. Hughes, L. Pareto. Recursion and dynamic data-structures in bounded space: towards embedded ML programming. ICFP'99, SIGPLAN Notices 34(9), ACM 1999.
[23]
J. Hughes, L. Pareto, A. Sabry. Proving the correctness of reactive systems using sized types. POPL'96, ACM 1996.
[24]
V. Sundaresan, P. Lam, E. Gagnon, R. Vallée-Rai, L. Hendren, P. Co. Soot: A java optimization framework. CASCON'99, IBM 1999.
[25]
G. Salagnac, Ch. Rippert, S. Yovine. Semi-automatic regionbased memory management for real-time java embedded systems. RTCSA'07, IEEE 2007.
[26]
G. Salagnac, S. Yovine, D. Garbervetsky. Fast escape analysis for region-based memory management. ENTCS, 131:99--110, 2005.
[27]
A. Salcianu, M. Rinard. Pointer and escape analysis for multithreaded programs. PPoPP'01, SIGPLAN Notices 36(7), ACM 2001.
[28]
M. Tofte, J.P. Talpin. Region-based memory management. Inf. Comput. 132(2):109--176, 1997.
[29]
L. Unnikrishnan, S.D. Stoller, Y.A. Liu. Optimized live heap bound analysis. VMCAI'03, LNCS 2575, 2003.

Cited By

View all
  • (2023)OOM-Guard: Towards Improving the Ergonomics of Rust OOM Handling via a Reservation-Based ApproachProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616303(733-744)Online publication date: 30-Nov-2023
  • (2023)Runtime Performance Prediction for Deep Learning Models with Graph Neural NetworkProceedings of the 45th International Conference on Software Engineering: Software Engineering in Practice10.1109/ICSE-SEIP58684.2023.00039(368-380)Online publication date: 17-May-2023
  • (2022)Reasoning about “reasoning about reasoning”: semantics and contextual equivalence for probabilistic programs with nested queries and recursionProceedings of the ACM on Programming Languages10.1145/34986776:POPL(1-28)Online publication date: 12-Jan-2022
  • Show More Cited By

Index Terms

  1. Parametric prediction of heap memory requirements

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ISMM '08: Proceedings of the 7th international symposium on Memory management
      June 2008
      170 pages
      ISBN:9781605581347
      DOI:10.1145/1375634
      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: 07 June 2008

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. heap consumption
      2. heap space analysis
      3. java
      4. memory regions

      Qualifiers

      • Research-article

      Conference

      ISMM '08
      Sponsor:

      Acceptance Rates

      Overall Acceptance Rate 72 of 156 submissions, 46%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)9
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 16 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)OOM-Guard: Towards Improving the Ergonomics of Rust OOM Handling via a Reservation-Based ApproachProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616303(733-744)Online publication date: 30-Nov-2023
      • (2023)Runtime Performance Prediction for Deep Learning Models with Graph Neural NetworkProceedings of the 45th International Conference on Software Engineering: Software Engineering in Practice10.1109/ICSE-SEIP58684.2023.00039(368-380)Online publication date: 17-May-2023
      • (2022)Reasoning about “reasoning about reasoning”: semantics and contextual equivalence for probabilistic programs with nested queries and recursionProceedings of the ACM on Programming Languages10.1145/34986776:POPL(1-28)Online publication date: 12-Jan-2022
      • (2022)Property-directed reachability as abstract interpretation in the monotone theoryProceedings of the ACM on Programming Languages10.1145/34986766:POPL(1-31)Online publication date: 12-Jan-2022
      • (2022)Interval universal approximation for neural networksProceedings of the ACM on Programming Languages10.1145/34986756:POPL(1-29)Online publication date: 12-Jan-2022
      • (2022)On type-cases, union elimination, and occurrence typingProceedings of the ACM on Programming Languages10.1145/34986746:POPL(1-31)Online publication date: 12-Jan-2022
      • (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
      • (2022)Learning formulas in finite variable logicsProceedings of the ACM on Programming Languages10.1145/34986716:POPL(1-28)Online publication date: 12-Jan-2022
      • (2022)A cost-aware logical frameworkProceedings of the ACM on Programming Languages10.1145/34986706:POPL(1-31)Online publication date: 12-Jan-2022
      • (2020)Estimating GPU memory consumption of deep learning modelsProceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3368089.3417050(1342-1352)Online publication date: 8-Nov-2020
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media