Article

Profile-guided proactive garbage collection for locality optimization

Authors:

Sanjay Bhansali,

Trishul Chilimbi,

Weihaw ChuangAuthors Info & Claims

PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 332 - 340

https://doi.org/10.1145/1133981.1134021

Published: 11 June 2006 Publication History

Abstract

Many applications written in garbage collected languages have large dynamic working sets and poor data locality. We present a new system for continuously improving program data locality at run time with low overhead. Our system proactively reorganizes the heap by leveraging the garbage collector and uses profile information collected through a low-overhead mechanism to guide the reorganization at run time. The key contributions include making a case that garbage collection should be viewed as a proactive technique for improving data locality by triggering garbage collection for locality optimization independently of normal garbage collection for space, combining page and cache locality optimization in the same system, and demonstrating that sampling provides sufficiently detailed data access information to guide both page and cache locality optimization with low runtime overhead. We present experimental results obtained by modifying a commercial, state-of-the-art garbage collector to support our claims. Independently triggering garbage collection for locality optimization significantly improved optimizations benefits. Combining page and cache locality optimizations in the same system provided larger average execution time improvements (17%) than either alone (page 8%, cache 7%). Finally, using sampling limited profiling overhead to less than 3%, on average.

References

[1]

Adl-Tabatabai, A., Hudson, R., Serrano, M., Subramoney, S. "Prefetch Injection Based on Hardware Monitoring and Object Matadata." In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '04), 2004, 267--276.

Digital Library

[2]

Arnold, M. and Ryder, B. "A Framework for Reducing the Cost of Instrumented Code." In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '01), 2001, 168--179.

Digital Library

[3]

Bacon, D.F., Cheng, Perry, Rajan V.T. "A Real-time Garbage Collector with Low Overhead and Consistent Utilization" In Principles of Programming Languages (POPL '03), 2003.

Digital Library

[4]

Cheney, C. "A Non-recursive List Compacting Algorithm." Communications of the ACM, 13(11), November 1970, 677--678.

Digital Library

[5]

Hirzel, M. and Chilimbi, T. "Bursty Tracing: A Framework for Low-Overhead Temporal Profiling." In 4th ACM Workshop on Feedback-Directed and Dynamic Optimization '01 (FDDO), 2001, 117--126.

[6]

Chilimbi, T. and Larus, J. "Using Generational Garbage Collection to implement Cache-conscious Data placement." In Proceedings of the 1st International Symposium on Memory Management, October 1998, 37--48.

Digital Library

[7]

Chilimbi, T., and Larus, J. "Cache-conscious Structure Definition." In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '99), 1999, 1--12.

Digital Library

[8]

Courts, R. "Improving Locality of Reference in a Garbage-Collecting Memory Management System." Communications of the ACM, 31(9), September 1988, 1128--1138.

Digital Library

[9]

Zorn, B. The Effect of Garbage Collection on Cache Performance, Technical Report CU-CS-528-91, Department of Computer Science, University of Colorado at Boulder, 1991.

[10]

Hennessy, J. and Patterson, D. Computer Architecture: A Quantitative Approach. Morgan Kaufman, San Mateo, CA. 3rd edition, 2002.

Digital Library

[11]

Hertz, M., Feng, Y., and Berger, E. D. "Garbage Collection without Paging" In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '05), 2005.

Digital Library

[12]

Inagaki, T., Onodera, T., Komastu, H., and Nakatani, T. "Stride Prefecthing by Dynamically Inspecting Objects." In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '03), 2003, 269--277.

Digital Library

[13]

Lam, M., Wilson, P., and Moher, T. "Object Type Directed Garbage Collection to Improve Locality." In Proceedings of the International Workshop on Memory Management, 1992, 404--425.

Digital Library

[14]

Hirzel, M., Diwan, A. and Hertz, M. "Connectivity-based Garbage Collection." In Proceedings of the 18th annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'03), 2003, 359--373.

Digital Library

[15]

Richter, J. "Garbage Collection: Automatic Memory Management in the Microsoft .NET Framework (Part I and II)." MSDN Magazine, 2000, http://msdn.microsoft.com/msdnmag/issues/1100/GCI/ and http://msdn.microsoft.com/msdnmag/issues/1200/GCI2/.

[16]

Moon, D. "Garbage Collection in a Large LISP System." In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming, August 1984, 235--246.

Digital Library

[17]

Nagpurkar, P., Krintz, C., and Sherwood, T. Phase-aware Remote Profiling, Technical report UCSB 2004-21, Department of Computer Science, University of California at Santa Barbara, 2004.

[18]

White, J. "Address/Memory Management for a Gigantic LISP Environment or, GC Considered Harmful." In Proceedings of the 1980 ACM Conference on LISP and Functional Programming, 1980, 119--127.

Digital Library

[19]

Wilson, P. "Uniprocessor Garbage Collection Techniques." In Proceedings of the International Workshop on Memory Management, 1992, 1--42.

Digital Library

[20]

Wilson, P., Lam, M., and Moher, T. "Effective Static-graph Reorganization to Improve Locality in Garbage Collected Systems." In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '91), 1991, 177--191.

Digital Library

[21]

Shuf, Y., Gupta, M., Franke, H., Appel, A., and Singh, J. "Creating and Preserving Locality of Java Applications at Allocation and Garbage Collection Times." In Proceedings of the 18th annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'02), 2002, 13--25.

Digital Library

[22]

Huang, X., Blackburn, S., McKinley, K., Moss, J., Wang, Z., and Cheng, P. "The Garbage Collection Advantage: Improving Program Locality." In Proceedings of the 18th annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'04), 2004, 29--80.

Digital Library

[23]

Shen, X., Zhong, Y., and Ding, C. "Locality Phase Prediction." In Proceedings of the 11th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '04), 2004, 165--176.

Digital Library

[24]

Chilimbi, T. "Efficient Representations and Abstractions for Quantifying and Exploiting Data Reference Locality." In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '01), 2001, 191--202.

Digital Library

[25]

Wilkes, R. "Ngen Revs up your performance with Powerful New Features", MSDN Magazine April 2005.

Cited By

Norlinder JYang ABlack-Schaffer DWrigstad TErtl MKirsch C(2024)Mutator-Driven Object Placement using Load BarriersProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685060(14-27)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685060
Carpen-Amarie MVavouliotis GTovletoglou KGrot BMueller RBlackburn SPetrank E(2023)Concurrent GCs and Modern Java Workloads: A Cache PerspectiveProceedings of the 2023 ACM SIGPLAN International Symposium on Memory Management10.1145/3591195.3595269(71-84)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591195.3595269
Kayraklioglu EFavry EEl-Ghazawi T(2021)A Machine-Learning-Based Framework for Productive Locality ExploitationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.305134832:6(1409-1424)Online publication date: 1-Jun-2021
https://doi.org/10.1109/TPDS.2021.3051348
Show More Cited By

Index Terms

Profile-guided proactive garbage collection for locality optimization
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Runtime environments
      2. Source code generation
  2. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection

Recommendations

Profile-guided proactive garbage collection for locality optimization
Proceedings of the 2006 PLDI Conference

Many applications written in garbage collected languages have large dynamic working sets and poor data locality. We present a new system for continuously improving program data locality at run time with low overhead. Our system proactively reorganizes ...
Impact of Data Locality on Garbage Collection in SSDs: A General Analytical Study
ICPE '15: Proceedings of the 6th ACM/SPEC International Conference on Performance Engineering

Solid-state drives (SSDs) necessitate garbage collection (GC) to erase data blocks and reclaim the space of invalidated data, and GC inevitably introduces additional writes due to data relocation. The performance of GC, which is quantified by cleaning ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '06: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2006

438 pages

ISBN:1595933204

DOI:10.1145/1133981

General Chair:
Michael Schwartzbach
University of Aarhus, Denmark
,
Program Chair:
Thomas Ball
Microsoft Research

ACM SIGPLAN Notices Volume 41, Issue 6
Proceedings of the 2006 PLDI Conference
June 2006
426 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1133255
Issue’s Table of Contents

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

In-Cooperation

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI06

Sponsor:

PLDI06: ACM SIGPLAN Conference on Programming Language Design and Implementation 2006

June 11 - 14, 2006

Ontario, Ottawa, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
729
Total Downloads

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

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Norlinder JYang ABlack-Schaffer DWrigstad TErtl MKirsch C(2024)Mutator-Driven Object Placement using Load BarriersProceedings of the 21st ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3679007.3685060(14-27)Online publication date: 13-Sep-2024
https://dl.acm.org/doi/10.1145/3679007.3685060
Carpen-Amarie MVavouliotis GTovletoglou KGrot BMueller RBlackburn SPetrank E(2023)Concurrent GCs and Modern Java Workloads: A Cache PerspectiveProceedings of the 2023 ACM SIGPLAN International Symposium on Memory Management10.1145/3591195.3595269(71-84)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591195.3595269
Kayraklioglu EFavry EEl-Ghazawi T(2021)A Machine-Learning-Based Framework for Productive Locality ExploitationIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.305134832:6(1409-1424)Online publication date: 1-Jun-2021
https://doi.org/10.1109/TPDS.2021.3051348
Akram SSartor JMcKinley KEeckhout L(2019)Crystal GazerProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/3322205.33110803:1(1-27)Online publication date: 26-Mar-2019
https://dl.acm.org/doi/10.1145/3322205.3311080
Kayraklioglu EFavry EEl-Ghazawi T(2019)A Machine Learning Approach for Productive Data Locality Exploitation in Parallel Computing Systems2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID)10.1109/CCGRID.2019.00050(361-370)Online publication date: May-2019
https://doi.org/10.1109/CCGRID.2019.00050
Chiu MMoss ETilevich EMössenböck H(2018)Run-time program-specific phase prediction for python programsProceedings of the 15th International Conference on Managed Languages & Runtimes10.1145/3237009.3237011(1-10)Online publication date: 12-Sep-2018
https://dl.acm.org/doi/10.1145/3237009.3237011
Patrício DBruno RSimão JFerreira PVeiga L(2017)Locality-Aware GC Optimisations for Big Data WorkloadsOn the Move to Meaningful Internet Systems. OTM 2017 Conferences10.1007/978-3-319-69459-7_4(50-67)Online publication date: 21-Oct-2017
https://doi.org/10.1007/978-3-319-69459-7_4
Li PLuo HDing C(2016)Rethinking a heap hierarchy as a cache hierarchy: a higher-order theory of memory demand (HOTM)ACM SIGPLAN Notices10.1145/3241624.292670851:11(111-121)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/3241624.2926708
Chiu MMarlin BMoss EZheng YBinder WTůma P(2016)Real-Time Program-Specific Phase Change Detection for Java ProgramsProceedings of the 13th International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools10.1145/2972206.2972221(1-11)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.1145/2972206.2972221
Li PLuo HDing CFlood CZhang Z(2016)Rethinking a heap hierarchy as a cache hierarchy: a higher-order theory of memory demand (HOTM)Proceedings of the 2016 ACM SIGPLAN International Symposium on Memory Management10.1145/2926697.2926708(111-121)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/2926697.2926708
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 Table of Conten