article

Automatic Accurate Live Memory Analysis for Garbage-Collected Languages

Authors:

Leena Unnikrishnan,

Scott D. Stoller,

Yanhong A. LiuAuthors Info & Claims

ACM SIGPLAN Notices, Volume 36, Issue 8

Pages 102 - 111

https://doi.org/10.1145/384196.384212

Published: 01 August 2001 Publication History

Abstract

This paper describes a general approach for automatic and accurate live heap space and live heap space-bound analyses for high-level languages. The approach is based on program analysis and transformations and is fully automatic. The space-bound analysis produces accurate (tight) upper bounds in the presence of partially known input structures. The analyses have been implemented and experimental results confirm their accuracy.

References

[1]

P. Altenbernd. On the false path problem in hard real-time programs. In Proceedings of the 8th EuroMicro Workshop on Real-Time Systems, pages 102-107, L'Aquila, June 1996.

[2]

W.-N. Chin and S.-C. Khoo. Calculating sized types. In Proceedings of the ACM SIGPLAN 2000 Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 62-72. ACM, New York, Jan. 2000.

Digital Library

[3]

T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Press/McGraw-Hill, 1990.

Digital Library

[4]

K. Crary and S. Weirich. Resource bound certification. In Conference Record of the 27th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, Jan. 2000.

Digital Library

[5]

Proceedings of the 3rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, May 1990.

[6]

P. Flajolet, B. Salvy, and P. Zimmermann. Automatic average-case analysis of algorithms. Theoretical Computer Science, Series A, 79(1):37-109, Feb. 1991.

Digital Library

[7]

Proceedings of the 4th International Conference on Functional Programming Languages and Computer Architecture. ACM, New York, Sept. 1989.

[8]

S. Ghosh, M. Martonosi, and S. Malik. Cache miss equations: A compiler framework for analyzing and tuning memory behavior. ACM Trans. Program. Lang. Syst., 21(4):703-746, July 1999.

Digital Library

[9]

R. Henriksson. Scheduling Garbage Collection in Embedded Systems. PhD thesis, Department of Computer Science, Lund University, Sept. 1998.

[10]

J. Hughes and L. Pareto. Recursion and dynamic data-structures in bounded space: Towards embedded ML programming. In Proceedings of the 1999 ACM SIGPLAN International Conference onFunctional Programming, pages 70-81. ACM, New York, Sept. 1999.

Digital Library

[11]

J. Hughes, L. Pareto, and A. Sabry. Proving the correctness of reactive systems using sized types. In Conference Record of the 23rd Annual ACM Symposium on Principles of Programming Languages, pages 410-423. ACM, New York, Jan. 1996.

Digital Library

[12]

K. Inoue, H. Seki, and H. Yagi. Analysis of functional programs to detect run-time garbage cells. ACM Trans. Program. Lang. Syst., 10(4):555-578, Oct. 1988.

Digital Library

[13]

T. P. Jensen and T. Mogensen. A backwards analysis for compile-time garbage collection. In ESOP 1990 {5}, pages 227-239.

Digital Library

[14]

R. Jones and R. Lins. Garbage Collection : Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, New York, 1996.

Digital Library

[15]

S. B. Jones and D. Le Metayer. Compile-time garbage collection by sharing analysis. In FPCA 1989 {7}, pages 54-74.

Digital Library

[16]

D. E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, Reading, Mass., 1968.

Digital Library

[17]

Proceedings of the ACM SIGPLAN 1999 Workshop on Languages, Compilers, and Tools for Embedded Systems. ACM, New York, May 1999.

[18]

D. Le Metayer. Ace: An automatic complexity evaluator. ACM Trans. Program. Lang. Syst., 10(2):248-266, Apr. 1988.

Digital Library

[19]

Y. A. Liu and G. Gomez. Automatic accurate time-bound analysis for high-level languages. In Proceedings of the ACM SIGPLAN 1998 Workshop on Languages, Compilers, and Tools for Embedded Systems, volume 1474 of Lecture Notes in Computer Science, pages 31-40. Springer-Verlag, June 1998.

Digital Library

[20]

M. Martonosi, A. Gupta, and T. Anderson. Effectiveness of trace sampling for performance debugging tools. In Proceedings of the 1993 ACM SIGMETRICS Conference onMeasurement and Modeling of Computer Systems, pages 248-259. ACM, New York, 1992.

Digital Library

[21]

C. Y. Park. Predicting program execution times by analyzing static and dynamic program paths. Real-Time Systems, 5:31-62, 1993.

Digital Library

[22]

P. Persson. Live memory analysis for garbage collection in embedded systems. In LCTES 1999 {17}, pages 45-54.

Digital Library

[23]

W. Pugh. The Omega Test: A fast and practical integer programming algorithm for dependence analysis. Commun. ACM, 31(8), Aug. 1992.

[24]

M. Rosendahl. Automatic complexity analysis. In FPCA 1989 {7}, pages 144-156.

Digital Library

[25]

I. Ryu. Issues and challenges in developing embedded software for information appliances and telecommunication terminals. In LCTES 1999 {17}, pages 104-120. Invited talk.

Digital Library

[26]

D. Sands. Complexity analysis for a lazy higher-order language. In ESOP 1990 {5}, pages 361-376.

Digital Library

[27]

L. Unnikrishnan, S. D. Stoller, and Y. A. Liu. Automatic accurate stack space and heap space analysis for high-level languages. Technical Report 538, Computer Science Dept., Indiana University, Apr. 2000.

[28]

R. Wilhelm and C. Ferdinand. On predicting data cache behaviour for real-time systems. In Proceedings of the ACM SIGPLAN 1998 Workshop on Languages, Compilers, and Tools for Embedded Systems, volume 1474 of Lecture Notes in Computer Science, pages 16-30. Springer-Verlag, June 1998.

Digital Library

[29]

P. Zimmermann and W. Zimmermann. The automatic complexity analysis of divide-and-conquer algorithms. In Computer and Information Sciences VI. Elsevier, 1991.

Cited By

Bendersky APetrank E(2012)Space overhead bounds for dynamic memory management with partial compactionACM Transactions on Programming Languages and Systems10.1145/2362389.236239234:3(1-43)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2362389.2362392
Albert EGenaim SGómez-Zamalloa Gil MKolodner HSteele G(2009)Live heap space analysis for languages with garbage collectionProceedings of the 2009 international symposium on Memory management10.1145/1542431.1542450(129-138)Online publication date: 19-Jun-2009
https://dl.acm.org/doi/10.1145/1542431.1542450
Liu YStoller S(2008)Dynamic Programming via Static IncrementalizationAutomatic Program Development10.1007/978-1-4020-6585-9_9(71-92)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_9
Show More Cited By

Index Terms

Automatic Accurate Live Memory Analysis for Garbage-Collected Languages
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection
2. Theory of computation
  1. Logic
  2. Semantics and reasoning
    1. Program reasoning

Recommendations

Automatic Accurate Live Memory Analysis for Garbage-Collected Languages
LCTES '01: Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems

This paper describes a general approach for automatic and accurate live heap space and live heap space-bound analyses for high-level languages. The approach is based on program analysis and transformations and is fully automatic. The space-bound ...
Automatic Accurate Live Memory Analysis for Garbage-Collected Languages
OM '01: Proceedings of the 2001 ACM SIGPLAN workshop on Optimization of middleware and distributed systems

This paper describes a general approach for automatic and accurate live heap space and live heap space-bound analyses for high-level languages. The approach is based on program analysis and transformations and is fully automatic. The space-bound ...
Live heap space analysis for languages with garbage collection
ISMM '09: Proceedings of the 2009 international symposium on Memory management

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 36, Issue 8

Aug. 2001

245 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/384196

Chairman:
Ron K. Cytron
Washington Univ., St. Louis, MO
,
Editor:
Cindy Norris
Appalachian State Univ., Boone, NC

Issue’s Table of Contents

LCTES '01: Proceedings of the ACM SIGPLAN workshop on Languages, compilers and tools for embedded systems
August 2001
250 pages
ISBN:1581134258
DOI:10.1145/384197
Chairmen:
Seongsoo Hong
Snow Bird, UT
,
Santosh Pande
Snow Bird, UT

Copyright © 2001 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2001

Published in SIGPLAN Volume 36, Issue 8

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
298
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bendersky APetrank E(2012)Space overhead bounds for dynamic memory management with partial compactionACM Transactions on Programming Languages and Systems10.1145/2362389.236239234:3(1-43)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2362389.2362392
Albert EGenaim SGómez-Zamalloa Gil MKolodner HSteele G(2009)Live heap space analysis for languages with garbage collectionProceedings of the 2009 international symposium on Memory management10.1145/1542431.1542450(129-138)Online publication date: 19-Jun-2009
https://dl.acm.org/doi/10.1145/1542431.1542450
Liu YStoller S(2008)Dynamic Programming via Static IncrementalizationAutomatic Program Development10.1007/978-1-4020-6585-9_9(71-92)Online publication date: 2008
https://doi.org/10.1007/978-1-4020-6585-9_9
Krone JOgden WSitaraman M(2006)Performance analysis based upon complete profilesProceedings of the 2006 conference on Specification and verification of component-based systems10.1145/1181195.1181197(3-10)Online publication date: 10-Nov-2006
https://dl.acm.org/doi/10.1145/1181195.1181197
Hofmann MJost S(2006)Type-Based amortised heap-space analysisProceedings of the 15th European conference on Programming Languages and Systems10.1007/11693024_3(22-37)Online publication date: 27-Mar-2006
https://dl.acm.org/doi/10.1007/11693024_3
Hofmann MJost S(2003)Static prediction of heap space usage for first-order functional programsACM SIGPLAN Notices10.1145/640128.60414838:1(185-197)Online publication date: 15-Jan-2003
https://dl.acm.org/doi/10.1145/640128.604148
Hofmann MJost SAiken AMorrisett G(2003)Static prediction of heap space usage for first-order functional programsProceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/604131.604148(185-197)Online publication date: 15-Jan-2003
https://dl.acm.org/doi/10.1145/604131.604148
Liu YStoller S(2003)Dynamic Programming via Static IncrementalizationHigher-Order and Symbolic Computation10.1023/A:102306802048316:1-2(37-62)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1023/A%3A1023068020483
Unnikrishnan LStoller SLiu Y(2002)Optimized Live Heap Bound AnalysisVerification, Model Checking, and Abstract Interpretation10.1007/3-540-36384-X_9(70-85)Online publication date: 16-Dec-2002
https://doi.org/10.1007/3-540-36384-X_9
Liu YGómez G(2001)Automatic Accurate Cost-Bound Analysis for High-Level LanguagesIEEE Transactions on Computers10.1109/TC.2001.97056950:12(1295-1309)Online publication date: 1-Dec-2001
https://dl.acm.org/doi/10.1109/TC.2001.970569

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents