Kindergarten cop: dynamic nursery resizing for GHC
Pages 56 - 66
Abstract
Generational garbage collectors are among the most popular garbage collectors used in programming language runtime systems. Their performance is known to depend heavily on choosing the appropriate size of the area where new objects are allocated (the nursery). In imperative languages, it is usual to make the nursery as large as possible, within the limits imposed by the heap size. Functional languages, however, have quite different memory be- haviour. In this paper, we study the effect that the nursery size has on the performance of lazy functional programs, through the interplay between cache locality and the frequency of collections. We demonstrate that, in contrast with imperative programs, having large nurseries is not always the best solution. Based on these re- sults, we propose two novel algorithms for dynamic nursery resiz- ing that aim to achieve a compromise between good cache locality and the frequency of garbage collections. We present an implemen- tation of these algorithms in the state-of-the-art GHC compiler for the functional language Haskell, and evaluate them using an exten- sive benchmark suite. In the best case, we demonstrate a reduction in total execution times of up to 88.5%, or an 8.7 overall speedup, compared to using the production GHC garbage collector. On aver- age, our technique gives an improvement of 9.3% in overall perfor- mance across a standard suite of 63 benchmarks for the production GHC compiler.
References
[1]
A. Ahmad and H. DeYoung. Cache Performance of Lazy Functional Programs on Current Hardware. Technical report, Carnegie Mellon University, 2009.
[2]
T. A. Anderson. Optimizations in a Private Nursery-based Garbage Collector. In Proceedings of the 2010 International Symposium on Memory Management, ISMM ’10, pages 21–30, New York, NY, USA, 2010. ACM.
[3]
A. W. Appel. Simple Generational Garbage Collection and Fast Allocation, 1989.
[4]
S. M. Blackburn, P. Cheng, and K. S. McKinley. Myths and Realities: The Performance Impact of Garbage Collection. In Proceedings of the Joint International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’04/Performance ’04, pages 25–36, New York, NY, USA, 2004. ACM.
[5]
A. M. Cheadle, A. J. Field, S. Marlow, S. L. P. Jones, and R. L. While. Exploring the Barrier to Entry - Incremental Generational Garbage Collection for Haskell. In Proceedings of the 4th International Symposium on Memory Management, ISMM ’04, pages 163–174, New York, NY, USA, 2004. ACM.
[6]
X. Guan, W. Srisa-an, and C. Jia. Investigating the Effects of Using Different Nursery Sizing Policies on Performance. In Proceedings of the 2009 International Symposium on Memory Management, ISMM ’09, pages 59–68, New York, NY, USA, 2009. ACM.
[7]
R. Jones. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, 1996.
[8]
S. Marlow. Haskell 2010. Language Report, 2010.
[9]
S. Marlow and S. Peyton Jones. Multicore Garbage Collection with Local Heaps. In Proceedings of the 10th International Symposium on Memory Management, ISMM ’11, pages 21–32, New York, NY, USA, 2011. ACM.
[10]
S. Marlow, T. Harris, R. P. James, and S. Peyton Jones. Parallel generational-copying garbage collection with a block-structured heap. In Proceedings of the 7th International Symposium on Memory Management, ISMM ’08, pages 11–20, New York, NY, USA, 2008. ACM.
[11]
W. Partain. The nofib Benchmark Suite of Haskell Programs. In Proceedings of the 1992 Glasgow Workshop on Functional Programming, pages 195–202, London, UK, 1993. Springer-Verlag.
[12]
S. Peyton Jones, C. Hall, K. Hammond, W. Partain, and P. Wadler. The Glasgow Haskell Compiler: a Technical Overview. In Proc. JFIT ’93, Keele, Mar. 1993.
[13]
D. Stewart. The ghc-gc-tune package. https://hackage.haskell. org/package/ghc-gc-tune, 2015.
[14]
J. M. Velasco, A. Ortiz, K. Olcoz, and F. Tirado. Dynamic Management of Nursery Space Organization in Generational Collection. In Proceedings of the 8th Annual Workshop on Interaction between Compilers and Computer Architectures, INTERACT ’04, pages 33–40, Los Alamitos, CA, USA, 2004. IEEE Computer Society.
[15]
D. R. White, J. Singer, J. M. Aitken, and R. E. Jones. Control theory for principled heap sizing. In Proceedings of the 2013 International Symposium on Memory Management, ISMM ’13, pages 27–38, New York, NY, USA, 2013. ACM.
[16]
P. R. Wilson, M. S. Lam, and T. G. Moher. Caching Considerations for Generational Garbage Collection. In Proceedings of the 1992 ACM Conference on LISP and Functional Programming, LFP ’92, pages 32–42, New York, NY, USA, 1992. ACM.
[17]
Y. Zhao, J. Shi, K. Zheng, H. Wang, H. Lin, and L. Shao. Allocation Wall: a Limiting Factor of Java Applications on Emerging Multi-core Platforms. In Proceedings of the 24th ACM SIGPLAN Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’09, pages 361–376, New York, NY, USA, 2009. ACM.
[18]
B. Zorn. The Effect of Garbage Collection on Cache Performance. Technical Report CU-CS-528-91, University of Colorado, Boulder, May 1991.
Index Terms
- Kindergarten cop: dynamic nursery resizing for GHC
Recommendations
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationAn on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
A generational on-the-fly garbage collector for Java
An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
An experimental study of renewal-older-first garbage collection
Generational collection has improved the efficiency of garbage collection in fast-allocating programs by focusing on collecting young garbage, but has done little to reduce the cost of collecting a heap containing large amounts of older data. A new ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2016
270 pages
Copyright © 2016 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
- IEEE-CS: Computer Society
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 March 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- EU
Conference
CGO '16: 14th Annual IEEE/ACM International Symposium on Code Generation and Optimization
March 17 - 18, 2016
Barcelona, Spain
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 124Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 23 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in