Article

Finding your cronies: static analysis for dynamic object colocation

Authors:

Samuel Z. Guyer,

Kathryn S. McKinleyAuthors Info & Claims

OOPSLA '04: Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Pages 237 - 250

https://doi.org/10.1145/1028976.1028996

Published: 01 October 2004 Publication History

Abstract

This paper introduces <i>dynamic</i> object colocation, an optimization to reduce copying costs in generational and other incremental garbage collectors by allocating connected objects together in the same space. Previous work indicates that connected objects belong together because they often have similar lifetimes. Generational collectors, however, allocate all new objects in a <i>nursery</i> space. If these objects are connected to data structures residing in the <i>mature</i> space, the collector must copy them. Our solution is a cooperative optimization that exploits compiler analysis to make runtime allocation decisions. The compiler analysis discovers potential object connectivity for newly allocated objects. It then replaces these allocations with calls to <i>coalloc</i>, which takes an extra parameter called the <i>colocator</i> object. At runtime, coalloc determines the location of the colocator and allocates the new object together with it in either the nursery or mature space. Unlike pretenuring, colocation makes precise per-object allocation decisions and does not require lifetime analysis or allocation site homogeneity. Experimental results for SPEC Java benchmarks using Jikes RVM show colocation can reduce garbage collection time by 50% to 75%, and total performance by up to 1%.

References

[1]

O. Agesen and A. Garthwaite. Efficient object sampling via weak references. In ACM International Symposium on Memory Management, pages 121--127, Minneapolis, MN, Oct. 2000.

Digital Library

[2]

B. Alpern et al. Implementing Jalapeno in Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 314--324, Denver, CO, Nov. 1999.

Digital Library

[3]

B. Alpern et al. The Jalapeno virtual machine. IBM Systems Journal, 39(1):211--238, February 2000.

Digital Library

[4]

L. O. Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994.

[5]

A. W. Appel. Simple generational garbage collection and fast allocation. Software Practice and Experience, 19(2):171--183, 1989.

Digital Library

[6]

S. M. Blackburn, P. Cheng, and K. S. McKinley. Myths and realities: The performance impact of garbage collection. In ACM Conference on Measurement & Modeling Computer Systems, pages 25--36, New York, NY, June 2004.

Digital Library

[7]

S. M. Blackburn, P. Cheng, and K. S. McKinley. Oil and water? High performance garbage collection in Java with JMTk. In Proceedings of the International Conference on Software Engineering, pages 137--146, Scotland, UK, May 2004.

Digital Library

[8]

S. M. Blackburn, R. E. Jones, K. S. McKinley, and J. E. B. Moss. Beltway: Getting around garbage collection gridlock. In ACM Conference on Programming Languages Design and Implementation, pages 153--164, Berlin, Germany, June 2002.

Digital Library

[9]

S. M. Blackburn, S. Singhai, M. Hertz, K. S. McKinley, and J. E. B. Moss. Pretenuring for Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 342--352, Tampa, FL, Oct. 2001. ACM.

Digital Library

[10]

B. Blanchet. Escape analysis for Java: Theory and practice. ACM Transactions on Programming Languages and Systems, 25(6):713--775, Nov. 2003.

Digital Library

[11]

D. R. Chase, M. Wegman, and F. K. Zadeck. Analysis of pointers and structures. In ACM Conference on Programming Languages Design and Implementation, pages 296--310, White Plains, NY, June 1990.

Digital Library

[12]

P. Cheng, R. Harper, and P. Lee. Generational stack collection and profile-driven pretenuring. In ACM Conference on Programming Languages Design and Implementation, pages 162--173, Montreal, Canada, May 1998.

Digital Library

[13]

T. M. Chilimbi, M. D. Hill, and J. R. Larus. Cache-conscious structure layout. In ACM Conference on Programming Languages Design and Implementation, pages 1--12, Atlanta, GA, May 1999.

Digital Library

[14]

T. M. Chilimbi and J. R. Larus. Using generational garbage collection to implement cache-conscious data placement. In ACM International Symposium on Memory Management, pages 37--48, Vancouver, BC, Oct. 1998.

Digital Library

[15]

J. Choi, M. Gupta, M. J. Serrano, V. C. Sreedhar, and S. P. Midkiff. Stack allocation and synchronization optimizations for Java using escape analysis. ACM Transactions on Programming Languages and Systems, 25(6):876--910, Nov. 2003.

Digital Library

[16]

R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions

Digital Library

[17]

T. Domani, G. Goldshtein, E. Kolodner, E. Lewis, E. Petrank, and D. Sheinwald. Thread-local heaps for Java. In ACM International Symposium on Memory Management, pages 76--87, Berlin, Germany, June 2002.

Digital Library

[18]

M. Emami, R. Ghiya, and L. J. Hendren. Context-sensitive interprocedural Points-to analysis in the presence of function pointers. In ACM Conference on Programming Languages Design and Implementation, pages 242--256, June 1994.

Digital Library

[19]

R. Ghiya and L. J. Hendren. Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C. In ACM Symposium on the Principles of Programming Languages, St. Petersburg Beach, FL, Jan. 1996.

Digital Library

[20]

T. L. Harris. Dynamic adaptive pre-tenuring. In ACM International Symposium on Memory Management, pages 127--136, Minneapolis, MN, Oct. 2000.

Digital Library

[21]

M. Hirzel, A. Diwan, and M. Hertz. Connectivity-based garbage collection. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 359--373, Anaheim, CA, Oct. 2003.

Digital Library

[22]

M. Hirzel, J. Hinkel, A. Diwan, and M. Hind. Understanding the connectivity of heap objects. In ACM International Symposium on Memory Management, pages 36--49, Berlin, Germany, June 2002.

Digital Library

[23]

X. Huang, Z. Wang, S. M. Blackburn, K. S. McKinley, J. E. B. Moss, and P. Cheng. The garbage collection advantage: Improving mutator locality. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, Vancouver, BC, 2004. To appear.

Digital Library

[24]

R. L. Hudson and J. E. B. Moss. Incremental garbage collection for mature objects. In Y. Bekkers and J. Cohen, editors, International Workshop on Memory Management, St. Malo, France, volume 637 of Lecture Notes in Computer Science. Springer-Verlag, 1992.

Digital Library

[25]

M. S. Lam, P. R. Wilson, and T. G. Moher. Object type directed garbage collection to improve locality. In Y. Bekkers and J. Cohen, editors, ACM International Workshop on Memory Management, number 637 in Lecture Notes in Computer Science, pages 404--425, St. Malo, France, Sept. 1992. Springer-Verlag.

Digital Library

[26]

D. Lea. A memory allocator. http://gee.cs.oswego.edu/dl/html/malloc.html, 1997.

[27]

H. Lieberman and C. E. Hewitt. A real time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419--429, 1983.

Digital Library

[28]

F. Qian and L. Hendren. An adaptive, region-based allocator for Java. In ACM International Symposium on Memory Management, Berlin, Germany, June 2002.

Digital Library

[29]

N. Sachindran and J. E. B. Moss. Mark-Copy: Fast copying GC with less space overhead. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 326--343, Anahiem, CA, Oct. 2003.

Digital Library

[30]

Y. Shuf, M. Gupta, R. Bordawekar, and J. P. Singh. Exploiting prolific types for memory management and optimzations. In ACM Symposium on the Principles of Programming Languages, pages 295--306, Portland, OR, Jan. 2002.

Digital Library

[31]

Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03 edition, March 1999.

[32]

Standard Performance Evaluation Corporation. SPECjbb2000 (Java Business Benchmark) Documentation, release 1.01 edition, 2001.

[33]

D. Stefanovic, K. McKinley, and J. Moss. Age-based garbage collection. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 370--381, Denver, CO, Nov. 1999.

Digital Library

[34]

D. Ungar and F. Jackson. Tenuring policies for generation-based storage reclamation. In ACM Conference on Object Oriented Programming Systems, Languages, and Applications, pages 1--17, San Diego, California, Nov. 1988.

Digital Library

[35]

D. Ungar and F. Jackson. An adaptive tenuring policy for generation scavengers. ACM Transactions on Programming Languages and Systems, 14(1):1--27, 1992.

Digital Library

[36]

D. M. Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In ACM Software Engineering Symposium on Practical Software Development Environments, pages 157--167, April 1984.

Digital Library

[37]

P. R. Wilson, M. S. Lam, and T. G. Moher. Effective static-graph reorganization to improve locality in garbage-collected systems. In ACM SIGPLAN Conference on Programming Languages Design and Implementation, pages 177--191, Toronto, Canada, June 1991.

Digital Library

Cited By

Olson MKammerdiener BJantz MDoshi KJones T(2022)Online Application Guidance for Heterogeneous Memory SystemsACM Transactions on Architecture and Code Optimization10.1145/353385519:3(1-27)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3533855
Wang YGu NSu JQi DNing Z(2022)Data layout optimization based on the spatio-temporal model of field access2022 5th International Conference on Advanced Electronic Materials, Computers and Software Engineering (AEMCSE)10.1109/AEMCSE55572.2022.00055(238-244)Online publication date: Apr-2022
https://doi.org/10.1109/AEMCSE55572.2022.00055
Bruno ROliveira LFerreira P(2017)NG2C: pretenuring garbage collection with dynamic generations for HotSpot big data applicationsACM SIGPLAN Notices10.1145/3156685.309227252:9(2-13)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3156685.3092272
Show More Cited By

Index Terms

Finding your cronies: static analysis for dynamic object colocation
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Finding your cronies: static analysis for dynamic object colocation
OOPSLA '04

This paper introduces <i>dynamic</i> object colocation, an optimization to reduce copying costs in generational and other incremental garbage collectors by allocating connected objects together in the same space. Previous work indicates that connected ...
Integrated Hardware Garbage Collection

Garbage collected programming languages, such as Python and C#, have accelerated software development. These modern languages increase productivity and software reliability as they provide high-level data representation and control structures. Modern ...
Static determination of allocation rates to support real-time garbage collection
LCTES '05: Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

While it is generally accepted that garbage-collected languages offer advantages over languages in which objects must be explicitly deallocated, real-time developers are leery of the adverse effects a garbage collector might have on real-time ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OOPSLA '04: Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

October 2004

462 pages

ISBN:1581138318

DOI:10.1145/1028976

General Chair:
John Vlissides
IBM Research
,
Program Chair:
Doug Schmidt
Vanderbilt

ACM SIGPLAN Notices Volume 39, Issue 10
OOPSLA '04
October 2004
448 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1035292
Issue’s Table of Contents

Copyright © 2004 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: 01 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

OOPSLA04

Sponsor:

OOPSLA04: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 24 - 28, 2004

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
503
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)2

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Olson MKammerdiener BJantz MDoshi KJones T(2022)Online Application Guidance for Heterogeneous Memory SystemsACM Transactions on Architecture and Code Optimization10.1145/353385519:3(1-27)Online publication date: 6-Jul-2022
https://dl.acm.org/doi/10.1145/3533855
Wang YGu NSu JQi DNing Z(2022)Data layout optimization based on the spatio-temporal model of field access2022 5th International Conference on Advanced Electronic Materials, Computers and Software Engineering (AEMCSE)10.1109/AEMCSE55572.2022.00055(238-244)Online publication date: Apr-2022
https://doi.org/10.1109/AEMCSE55572.2022.00055
Bruno ROliveira LFerreira P(2017)NG2C: pretenuring garbage collection with dynamic generations for HotSpot big data applicationsACM SIGPLAN Notices10.1145/3156685.309227252:9(2-13)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3156685.3092272
Bruno ROliveira LFerreira PKirsch CTitzer B(2017)NG2C: pretenuring garbage collection with dynamic generations for HotSpot big data applicationsProceedings of the 2017 ACM SIGPLAN International Symposium on Memory Management10.1145/3092255.3092272(2-13)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3092255.3092272
Wagner GLarsen PBrunthaler SFranz M(2016)Thinking Inside the BoxACM Transactions on Programming Languages and Systems10.1145/286657638:3(1-37)Online publication date: 8-Apr-2016
https://dl.acm.org/doi/10.1145/2866576
Jantz MRobinson FKulkarni PDoshi K(2015)Cross-layer memory management for managed language applicationsACM SIGPLAN Notices10.1145/2858965.281432250:10(488-504)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2858965.2814322
Jantz MRobinson FKulkarni PDoshi KAldrich JEugster P(2015)Cross-layer memory management for managed language applicationsProceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2814270.2814322(488-504)Online publication date: 23-Oct-2015
https://dl.acm.org/doi/10.1145/2814270.2814322
Clifford DPayer HStarzinger MTitzer B(2014)Allocation folding based on dominanceACM SIGPLAN Notices10.1145/2775049.260299449:11(15-24)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2775049.2602994
Clifford DPayer HStarzinger MTitzer BGrove DGuyer S(2014)Allocation folding based on dominanceProceedings of the 2014 international symposium on Memory management10.1145/2602988.2602994(15-24)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2602988.2602994
Marron MLhoták OBanerjee A(2012)Programming paradigm driven heap analysisProceedings of the 21st international conference on Compiler Construction10.1007/978-3-642-28652-0_3(41-60)Online publication date: 24-Mar-2012
https://dl.acm.org/doi/10.1007/978-3-642-28652-0_3
Show More Cited By

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 Table of Contents