research-article

Open access

Learned garbage collection

Authors:

Justin Gottschlich,

Mohammad Alizadeh,

Tim KraskaAuthors Info & Claims

MAPL 2020: Proceedings of the 4th ACM SIGPLAN International Workshop on Machine Learning and Programming Languages

Pages 38 - 44

https://doi.org/10.1145/3394450.3397469

Published: 15 June 2020 Publication History

Abstract

Several programming languages use garbage collectors (GCs) to automatically manage memory for the programmer. Such collectors must decide when to look for unreachable objects to free, which can have a large performance impact on some applications. In this preliminary work, we propose a design for a learned garbage collector that autonomously learns over time when to perform collections. By using reinforcement learning, our design can incorporate user-defined reward functions, allowing an autonomous garbage collector to learn to optimize the exact metric the user desires (e.g., request latency or queries per second). We conduct an initial experimental study on a prototype, demonstrating that an approach based on tabular Q learning may be promising.

References

[1]

M. Alam, J. Gottschlich, N. Tatbul, J. S. Turek, T. Mattson, and A. Muzahid. A Zero-Positive Learning Approach for Diagnosing Software Performance Regressions. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlchBuc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, NeurIPS 2019, pages 11623–11635.

[2]

Curran Associates, Inc., 2019.

[3]

U. Degenbaev, J. Eisinger, M. Ernst, R. McIlroy, and H. Payer. Idle time garbage collection scheduling. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’16, pages 570–583, Santa Barbara, CA, USA, June 2016.

Digital Library

[4]

Association for Computing Machinery. ISBN 978-1-4503-4261-2.

Digital Library

[5]

Learned Garbage Collection MAPL ’20, June 15, 2020, London, UK

[6]

D. Detlefs, C. Flood, S. Heller, and T. Printezis. Garbage-first garbage collection. In Proceedings of the 4th International Symposium on Memory Management, ISMM ’04, pages 37–48, Vancouver, BC, Canada, Oct. 2004. Association for Computing Machinery. ISBN 978-1-58113-945-7.

Digital Library

[7]

E. Dinella, H. Dai, Z. Li, M. Naik, L. Song, and K. Wang. Hoppity: Learning Graph Transformations to Detect and Fix Bugs in Programs. In International Conference on Learning Representations, 2020.

[8]

Y. Y. Elboher, J. Gottschlich, and G. Katz. An Abstraction-Based Framework for Neural Network Verification. In Computer Aided Verification, Cham, 2020. Springer International Publishing.

[9]

K. Ellis, M. Nye, Y. Pu, F. Sosa, J. Tenenbaum, and A. Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 9169–9178. Curran Associates, Inc., 2019.

[10]

J. Gottschlich, A. Solar-Lezama, N. Tatbul, M. Carbin, M. Rinard, R. Barzilay, S. Amarasinghe, J. B. Tenenbaum, and T. Mattson. The three pillars of machine programming. In Proceedings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, MAPL 2018, pages 69–80, Philadelphia, PA, USA, June 2018. Association for Computing Machinery. ISBN 978-1-4503-5834-7.

Digital Library

[11]

K. Heo, W. Lee, P. Pashakhanloo, and M. Naik. Effective program debloating via reinforcement learning. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS ’18, page 380–394, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450356930.

Digital Library

[12]

Instagram. Instagram engineering, https://instagramengineering.com/dismissing-python-garbage-collection-atinstagram-4dca40b29172. 2017.

[13]

R. G. Iyer, Y. Sun, W. Wang, and J. Gottschlich. Software language comprehension using a program-derived semantic graph, 2020.

[14]

N. Jacek and J. E. B. Moss. Learning when to garbage collect with random forests. In Proceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management, ISMM 2019, pages 53–63, Phoenix, AZ, USA, June 2019. Association for Computing Machinery. ISBN 978-1-4503-6722-6.

Digital Library

[15]

N. Jacek, M.-C. Chiu, B. M. Marlin, and J. E. B. Moss. Optimal Choice of When to Garbage Collect. In ACM Transactions on Programming Languages and Systems, volume 41 of TOPS ’19. Association for Computing Machinery, Jan. 2019.

[16]

A. Jangda and R. Nasre. FastCollect: Offloading generational garbage collection to integrated GPUs. In Proceedings of the International Conference on Compilers, Architectures and Synthesis for Embedded Systems, CASES ’16, pages 1–10, Pittsburgh, Pennsylvania, Oct. 2016.

[17]

Association for Computing Machinery. ISBN 978-1-4503-4482-1.

Digital Library

[18]

G. Katz, C. Barrett, D. L. Dill, K. Julian, and M. J. Kochenderfer. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks. In R. Majumdar and V. Kunčak, editors, Computer Aided Verification, pages 97–117, Cham, 2017. Springer International Publishing. ISBN 978-3-319-63387-9.

[19]

G. Katz, D. A. Huang, D. Ibeling, K. Julian, C. Lazarus, R. Lim, P. Shah, S. Thakoor, H. Wu, A. Zeljić, D. L. Dill, M. J. Kochenderfer, and C. Barrett. The Marabou Framework for Verification and Analysis of Deep Neural Networks. In I. Dillig and S. Tasiran, editors, Computer Aided Verification, pages 443–452, Cham, 2019. Springer International Publishing. ISBN 978-3-030-25540-4.

[20]

C. Lemieux, R. Padhye, K. Sen, and D. Song. Perffuzz: Automatically generating pathological inputs. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA 2018, page 254–265, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450356992.

Digital Library

[21]

H. Lieberman and C. Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, June 1983.

Digital Library

[22]

S. Luan, D. Yang, C. Barnaby, K. Sen, and S. Chandra. Aroma: Code Recommendation via Structural Code Search. Proc. ACM Program. Lang., 3(OOPSLA):152:1–152:28, October 2019. ISSN 2475-1421.

Digital Library

[23]

S. Mandal, T. A. Anderson, J. S. Turek, J. Gottschlich, S. Zhou, and A. Muzahid. Learning Fitness Functions for Genetic Algorithms, 2019.

[24]

H. Mao, M. Schwarzkopf, S. B. Venkatakrishnan, Z. Meng, and M. Alizadeh. Learning Scheduling Algorithms for Data Processing Clusters. arXiv:1810.01963 [cs, stat], 2018.

[25]

R. Marcus and O. Papaemmanouil. Releasing Cloud Databases from the Chains of Performance Prediction Models. In 8th Biennial Conference on Innovative Data Systems Research, CIDR ’17, San Jose, CA, 2017.

[26]

R. Marcus, P. Negi, H. Mao, C. Zhang, M. Alizadeh, T. Kraska, O. Papaemmanouil, and N. Tatbul. Neo: A Learned Query Optimizer. PVLDB, 12(11):1705–1718, 2019.

[27]

J. McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. Commun. ACM, Apr. 1960.

Digital Library

[28]

V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, and G. Ostrovski. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015.

[29]

A. Y. Ng, D. Harada, and S. J. Russell. Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping. In Proceedings of the Sixteenth International Conference on Machine Learning, ICML ’99, pages 278–287, San Francisco, CA, USA, June 1999. Morgan Kaufmann Publishers Inc. ISBN 978-1-55860-612-8.

[30]

D. Nunez, S. Z. Guyer, and E. D. Berger. Prioritized garbage collection: Explicit GC support for software caches. In ACM SIGPLAN Notices, volume 51 of SIGPLAN ’16. Association for Computing Machinery, Oct. 2016.

[31]

J. Ortiz, B. Lee, and M. Balazinska. PerfEnforce Demonstration: Data Analytics with Performance Guarantees. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, pages 2141–2144, San Francisco, California, USA, 2016. ACM. ISBN 978-1- 4503-3531-7.

Digital Library

[32]

J. Ortiz, M. Balazinska, J. Gehrke, and S. S. Keerthi. Learning State Representations for Query Optimization with Deep Reinforcement Learning. In 2nd Workshop on Data Managmeent for End-to-End Machine Learning, DEEM ’18, 2018.

[33]

M. Schaarschmidt, A. Kuhnle, B. Ellis, K. Fricke, F. Gessert, and E. Yoneki. LIFT: Reinforcement Learning in Computer Systems by Learning From Demonstrations. arXiv:1808.07903 [cs, stat], Aug. 2018.

[34]

R. S. Sutton and A. G. Barto. Introduction to Reinforcement Learning. MIT Press, Cambridge, MA, USA, 1st edition, 1998. ISBN 978-0-262- 19398-6.

[35]

C. J. Watkins and P. Dayan. Q-learning. Machine learning, 8(3-4): 279–292, 1992.

Digital Library

[36]

F. Xian, W. Srisa-an, and H. Jiang. Garbage collection: Java application servers’ Achilles heel. Science of Computer Programming, 70(2):89–110, Feb. 2008. ISSN 0167-6423.

Digital Library

[37]

F. Ye, S. Zhou, A. Venkat, R. Marcus, P. Petersen, J. J. Tithi, T. Mattson, T. Kraska, P. Dubey, V. Sarkar, and J. Gottschlich. Context-aware parse trees, 2020.

[38]

Y. Yu, T. Lei, W. Zhang, H. Chen, and B. Zang. Performance Analysis and Optimization of Full Garbage Collection in Memory-hungry Environments. In Proceedings of The12th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments, VEE ’16, pages 123–130, Atlanta, Georgia, USA, Mar. 2016. Association for Computing Machinery. ISBN 978-1-4503-3947-6.

Digital Library

[39]

Abstract 1 Introduction 2 Related Work 3 Overview & Formulation 4 Learned GC 4.1 Optimizations & Discussion 5 Experiments 6 Future Work and Conclusion References

Cited By

Wu CAmiri MQin HMehta BMarcus RLoo B(2024)Towards Full Stack Adaptivity in Permissioned BlockchainsProceedings of the VLDB Endowment10.14778/3641204.364121617:5(1073-1080)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.14778/3641204.3641216
Wu CMehta BAmiri MMarcus RLoo B(2023)AdaChain: A Learned Adaptive BlockchainProceedings of the VLDB Endowment10.14778/3594512.359453116:8(2033-2046)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.14778/3594512.3594531
Neder FMiranda Filho RAzevedo JPessoa LDe Freitas RBarreto R(2023)Análise comparativa entre linguagens de programação em sistemas embarcados móveis AndroidProceedings of the XXVII Brazilian Symposium on Programming Languages10.1145/3624309.3624319(56-63)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1145/3624309.3624319
Show More Cited By

Index Terms

Learned garbage collection
1. Computing methodologies
  1. Machine learning

Recommendations

Age-based garbage collection

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, ...
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, ...
Garbage collection in LINDACAP
iiWAS '09: Proceedings of the 11th International Conference on Information Integration and Web-based Applications & Services

LINDACAP provides a capability-based coordination for open distributed systems. As open systems are persistent, garbage collection (GC) can be a vital aspect in managing the systems' resources. Garbage collection has been proposed for the standard Linda ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MAPL 2020: Proceedings of the 4th ACM SIGPLAN International Workshop on Machine Learning and Programming Languages

June 2020

44 pages

ISBN:9781450379960

DOI:10.1145/3394450

General Chair:
Koushik Sen,
Program Chair:
Mayur Naik

Copyright © 2020 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2020

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '20

Sponsor:

SIGPLAN

PLDI '20: 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 15, 2020

London, UK

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
1,154
Total Downloads

Downloads (Last 12 months)283
Downloads (Last 6 weeks)49

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu CAmiri MQin HMehta BMarcus RLoo B(2024)Towards Full Stack Adaptivity in Permissioned BlockchainsProceedings of the VLDB Endowment10.14778/3641204.364121617:5(1073-1080)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.14778/3641204.3641216
Wu CMehta BAmiri MMarcus RLoo B(2023)AdaChain: A Learned Adaptive BlockchainProceedings of the VLDB Endowment10.14778/3594512.359453116:8(2033-2046)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.14778/3594512.3594531
Neder FMiranda Filho RAzevedo JPessoa LDe Freitas RBarreto R(2023)Análise comparativa entre linguagens de programação em sistemas embarcados móveis AndroidProceedings of the XXVII Brazilian Symposium on Programming Languages10.1145/3624309.3624319(56-63)Online publication date: 25-Sep-2023
https://dl.acm.org/doi/10.1145/3624309.3624319
Tabassum FIslam MUr Rahman MMajumder J(2023)A Comprehensive Study on Different Optimizations of Pure Reference Counting Garbage Collectors2023 International Conference on Computational Intelligence, Networks and Security (ICCINS)10.1109/ICCINS58907.2023.10450100(1-6)Online publication date: 22-Dec-2023
https://doi.org/10.1109/ICCINS58907.2023.10450100
Katsaragakis MPapadopoulos LKonijnenburg MCatthoor FSoudris D(2023)A memory footprint optimization framework for Python applications targeting edge devicesJournal of Systems Architecture10.1016/j.sysarc.2023.102936142(102936)Online publication date: Sep-2023
https://doi.org/10.1016/j.sysarc.2023.102936
Marcus RNegi PMao HTatbul NAlizadeh MKraska TLi GLi ZIdreos SSrivastava D(2021)Bao: Making Learned Query Optimization PracticalProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452838(1275-1288)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452838
Gangwar DKatal A(2021)Memory Leak Detection Tools: A Comparative Analysis2021 International Conference on Recent Trends on Electronics, Information, Communication & Technology (RTEICT)10.1109/RTEICT52294.2021.9574012(315-320)Online publication date: 27-Aug-2021
https://doi.org/10.1109/RTEICT52294.2021.9574012
Asmarawati CSusanti EWibowo S(2021)Determination of the Distribution Center Location of the Batam City Garbage Bank using Gravity method2021 International Conference on Computer Science and Engineering (IC2SE)10.1109/IC2SE52832.2021.9791866(1-6)Online publication date: 16-Nov-2021
https://doi.org/10.1109/IC2SE52832.2021.9791866

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents