research-article

Modeling heap data growth using average liveness

Authors:

Hao LuoAuthors Info & Claims

ACM SIGPLAN Notices, Volume 49, Issue 11

Pages 71 - 82

https://doi.org/10.1145/2775049.2602997

Published: 12 June 2014 Publication History

Abstract

Most of today's programs make use of a sizable heap to store dynamic data. To characterize the heap dynamics, this paper presents a set of metrics to measure the average amount of data live and dead in a period of execution. They are collectively called average liveness. The paper defines these metrics of average liveness, gives linear-time algorithms for measurement, and discusses their use in finding the best heap size. The algorithms are implemented in a Java tracing system called Elephant Tracks and evaluated using the Dacapo benchmarks running on the Oracle HotSpot and IBM J9 Java virtual machines.

References

[1]

E. Albert, S. Genaim, and M. Gomez-Zamalloa Gil. Live heap space analysis for languages with garbage collection. In ISMM, pages 129--138, 2009.

Digital Library

[2]

E. Albert, S. Genaim, and M. Gomez-Zamalloa. Parametric inference of memory requirements for garbage collected languages. In ISMM, pages 121--130, 2010.

Digital Library

[3]

D. F. Bacon and V. T. Rajan. Concurrent cycle collection in reference counted systems. In Proceedings of the 15th European Conference on Object-Oriented Programming, pages 207--235, 2001.

Digital Library

[4]

D. F. Bacon, C. R. Attanasio, H. B. Lee, V. T. Rajan, and S. Smith. Java without the coffee breaks: a nonintrusive multiprocessor garbage collector. Proceedings of PLDI, 36(5):92--103, 2001. ISSN 0362- 1340.

Digital Library

[5]

D. F. Bacon, P. Cheng, and V. T. Rajan. A unified theory of garbage collection. In Proceedings of OOPSLA, pages 50--68, Vancouver, British Columbia, 2004.

Digital Library

[6]

S. Blackburn, R. E. Jones, K. S. McKinley, and J. E. B. Moss. Beltway: Getting around garbage collection gridlock. In Proceedings of PLDI, pages 153--164, 2002.

Digital Library

[7]

S. M. Blackburn et al. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of OOPSLA, 2006.

Digital Library

[8]

V. Braberman, F. Fernandez, D. Garbervetsky, and S. Yovine. Parametric prediction of heap memory requirements. In ISMM, pages 141--150, 2008.

Digital Library

[9]

S. Dieckmann and U. Holzle. A study of the allocation behavior of the specjvm98 java benchmark. In ECOOP, pages 92--115, 1999.

Digital Library

[10]

C. Ding and T. Chilimbi. All-window profiling of concurrent executions. In Proceedings of PPoPP, 2008. Poster paper.

Digital Library

[11]

B. Dufour, K. Driesen, L. Hendren, and C. Verbrugge. Dynamic metrics for java. In Proceedings of OOPSLA, pages 149--168, 2003.

Digital Library

[12]

H. Eran and E. Petrank. A study of data structures with a deep heap shape. In Proceedings of the ACM SIGPLAN Workshop on Memory System Performance and Correctness, page 2, 2013.

Digital Library

[13]

M. Hertz, S. M. Blackburn, K. S. McKinley, J. E. B. Moss, and D. Stefanovic. Generating object lifetime traces with Merlin. ACM TOPLAS, 28(3):476--516, 2006.

Digital Library

[14]

R. E. Jones and C. Ryder. A study of java object demographics. In ISMM, pages 121--130, 2008.

Digital Library

[15]

J.-S. Kim and Y. Hsu. Memory system behavior of java programs: Methodology and analysis. In Proceedings of the 2000 ACM SIG- METRICS International Conference on Measurement and Modeling of Computer Systems, pages 264--274, 2000.

Digital Library

[16]

P. Li and C. Ding. All-window data liveness. In Proceedings of the ACM SIGPLAN Workshop on Memory Systems Performance and Correctness, 2013.

Digital Library

[17]

H. Luo, X. Xiang, and C. Ding. Characterizing active data sharing in threaded applications using shared footprint. In Proceedings of the The 11th International Workshop on Dynamic Analysis, 2013.

[18]

S. Microsystems. Jvm tool interface. In http://java.sun.com/javase/6/docs/platform/jvmti/jvmti.html., 2004.

[19]

T. Mytkowicz, A. Diwan, M. Hauswirth, and P. F. Sweeney. Producing wrong data without doing anything obviously wrong! In Proceedings of ASPLOS, pages 265--276, 2009.

Digital Library

[20]

N. Ricci, S. Guyer, and E. Moss. Elephant tracks: Portable production of complete and precise GC traces. In Proceedings of ISMM, pages 109--118, 2013.

Digital Library

[21]

N. Rojemo and C. Runciman. Lag, drag, void and use - heap profiling and space-efficient compilation revisited. In Proceedings of ICFP, pages 34--41, 1996.

Digital Library

[22]

J. Singer, G. Brown, I.Watson, and J. Cavazos. Intelligent selection of application-specific garbage collectors. In Proceedings of the International Symposium on Memory Management, 2007.

Digital Library

[23]

D. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. SIGSOFT Softw. Eng. Notes, 9(3):157--167, Apr. 1984. ISSN 0163--5948. . URL http://doi.acm.org/10.1145/390010.808261.

Digital Library

[24]

S. C. Vestal. Garbage collection: an exercise in distributed, fault- tolerant programming. PhD thesis, 1987.

Digital Library

[25]

F. Xian, W. Srisa-an, and H. Jiang. Allocation-phase aware thread scheduling policies to improve garbage collection performance. In Proceedings of the 6th International Symposium on Memory Management, 2007.

Digital Library

[26]

X. Xiang, B. Bao, T. Bai, C. Ding, and T. M. Chilimbi. All-window profiling and composable models of cache sharing. In Proceedings of PPoPP, pages 91--102, 2011.

Digital Library

[27]

X. Xiang, B. Bao, C. Ding, and Y. Gao. Linear-time modeling of program working set in shared cache. In Proceedings of PACT, pages 350--360, 2011.

Digital Library

[28]

X. Xiang, C. Ding, H. Luo, and B. Bao. HOTL: a higher order theory of locality. In Proceedings of ASPLOS, pages 343--356, 2013.

Digital Library

[29]

G. H. Xu. Resurrector: a tunable object lifetime profiling technique for optimizing real-world programs. In Proceedings of OOPSLA, pages 111--130, 2013.

Digital Library

Cited By

Libič PBulej LHorký VTůma P(2015)Estimating the Impact of Code Additions on Garbage Collection OverheadComputer Performance Engineering10.1007/978-3-319-23267-6_9(130-145)Online publication date: 22-Aug-2015
https://doi.org/10.1007/978-3-319-23267-6_9
Li PGuo YGu Y(2022)Predicting Reuse Interval for Optimized Web Caching: An LSTM-Based Machine Learning ApproachSC22: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41404.2022.00091(1-15)Online publication date: Nov-2022
https://doi.org/10.1109/SC41404.2022.00091
Li PLuo HDing CSinger JXu H(2019)Timescale functions for parallel memory allocationProceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management10.1145/3315573.3329987(64-78)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3315573.3329987
Show More Cited By

Index Terms

Modeling heap data growth using average liveness

Recommendations

Modeling heap data growth using average liveness
ISMM '14: Proceedings of the 2014 international symposium on Memory management

Most of today's programs make use of a sizable heap to store dynamic data. To characterize the heap dynamics, this paper presents a set of metrics to measure the average amount of data live and dead in a period of execution. They are collectively called ...
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 ...
Controlling garbage collection and heap growth to reduce the execution time of Java applications
OOPSLA '01: Proceedings of the 16th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

In systems that support garbage collection, a tension exists between collecting garbage too frequently and not collecting garbage frequently enough. Garbage collection that occurs too frequently may introduce unnecessary overheads at the rist of not ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 49, Issue 11

ISMM '14

November 2014

121 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2775049

Editor:
Andy Gill
University of Kansas, Lawrence, KS

Issue’s Table of Contents

ISMM '14: Proceedings of the 2014 international symposium on Memory management
June 2014
136 pages
ISBN:9781450329217
DOI:10.1145/2602988
General Chair:
David Grove
IBM Research, USA
,
Program Chair:
Samuel Z. Guyer
Tufts University, USA

Copyright © 2014 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: 12 June 2014

Published in SIGPLAN Volume 49, Issue 11

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
238
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Libič PBulej LHorký VTůma P(2015)Estimating the Impact of Code Additions on Garbage Collection OverheadComputer Performance Engineering10.1007/978-3-319-23267-6_9(130-145)Online publication date: 22-Aug-2015
https://doi.org/10.1007/978-3-319-23267-6_9
Li PGuo YGu Y(2022)Predicting Reuse Interval for Optimized Web Caching: An LSTM-Based Machine Learning ApproachSC22: International Conference for High Performance Computing, Networking, Storage and Analysis10.1109/SC41404.2022.00091(1-15)Online publication date: Nov-2022
https://doi.org/10.1109/SC41404.2022.00091
Li PLuo HDing CSinger JXu H(2019)Timescale functions for parallel memory allocationProceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management10.1145/3315573.3329987(64-78)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3315573.3329987
Li PPronovost CWilson WTait BZhou JDing CCriswell JBahar IHerlihy MWitchel ELebeck A(2019)Beating OPT with Statistical Clairvoyance and Variable Size CachingProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304067(243-256)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304067
Brock JDing CLavaee RLiu FYuan L(2018)Prediction and bounds on shared cache demand from memory access interleavingACM SIGPLAN Notices10.1145/3299706.321056553:5(96-108)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3299706.3210565
Brock JDing CLavaee RLiu FYuan LPayer HSartor J(2018)Prediction and bounds on shared cache demand from memory access interleavingProceedings of the 2018 ACM SIGPLAN International Symposium on Memory Management10.1145/3210563.3210565(96-108)Online publication date: 18-Jun-2018
https://dl.acm.org/doi/10.1145/3210563.3210565
Bruno RFerreira PJayaram KGandhi AKemme BPietzuch P(2017)POLM2Proceedings of the 18th ACM/IFIP/USENIX Middleware Conference10.1145/3135974.3135986(147-160)Online publication date: 11-Dec-2017
https://dl.acm.org/doi/10.1145/3135974.3135986
Li PChakrabarti DDing CYuan L(2017)Adaptive Software Caching for Efficient NVRAM Data Persistence2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2017.83(112-122)Online publication date: May-2017
https://doi.org/10.1109/IPDPS.2017.83
Ye CBrock JDing CJin H(2017)Rochester Elastic Cache Utility (RECU)International Journal of Parallel Programming10.1007/s10766-015-0384-345:1(30-44)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10766-015-0384-3
Li PChakrabarti D(2017)Adaptive Software Caching for Efficient NVRAM Data PersistenceLanguages and Compilers for Parallel Computing10.1007/978-3-319-52709-3_8(93-97)Online publication date: 24-Jan-2017
https://doi.org/10.1007/978-3-319-52709-3_8
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.

Figures

Tables

Media

View Issue’s Table of Contents