Skip to content

Research at St Andrews

Kindergarten Cop: dynamic nursery resizing for GHC

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Author(s)

Henrique Ferreiro, Laura Castro, Vladimir Janjic, Kevin Hammond

School/Research organisations

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 behaviour. 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 results, we propose two novel algorithms for dynamic nursery resizing that aim to achieve a compromise between good cache locality and the frequency of garbage collections. We present an implementation of these algorithms in the state-of-the-art GHC compiler for the functional language Haskell, and evaluate them using an extensive 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 average, our technique gives an improvement of 9.3% in overall performance across a standard suite of 63 benchmarks for the production GHC compiler.
Close

Details

Original languageEnglish
Title of host publicationCC 2016 Proceedings of the 25th International Conference on Compiler Construction
Place of PublicationNew York
PublisherACM
Pages56-66
Number of pages10
ISBN (Print)9781450342414
DOIs
Publication statusPublished - 17 Mar 2016
Event25th International Conference on Compiler Construction - Barcelona, Barcelona, Spain
Duration: 17 Mar 201618 Mar 2016
http://cc2016.eew.technion.ac.il/

Conference

Conference25th International Conference on Compiler Construction
CountrySpain
CityBarcelona
Period17/03/1618/03/16
Internet address

    Research areas

  • Generational garbage collection, Cache locality, Allocation area, Functional programming

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Learning-based dynamic pinning of parallelized applications in many-core systems

    Chasparis, G., Rossbory, M., Janjic, V. & Hammond, K., 21 Mar 2019, Proceedings 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP 2019). Institute of Electrical and Electronics Engineers Inc., 8 p. 8671569

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. The Missing Link! A new skeleton for evolutionary multi-agent systems in Erlang

    Stypka, J., Turek, W., Byrski, A., Kisiel-Dorohinicki, M., Barwell, A. D., Brown, C. M., Hammond, K. & Janjic, V., Feb 2018, In : International Journal of Parallel Programming. 46, 1, p. 4-22 19 p.

    Research output: Contribution to journalArticle

  3. Efficient dynamic pinning of parallelized applications by reinforcement learning with applications

    Chasparis, G., Rossbory, M. & Janjic, V., 1 Aug 2017, Euro-Par 2017: Parallel Processing: 23rd International Conference on Parallel and Distributed Computing, Santiago de Compostela, Spain, August 28 – September 1, 2017, Proceedings. Rivera, F. F., Pena, T. F. & Cabaleiro, J. C. (eds.). Cham: Springer, p. 164-176 13 p. (Lecture Notes in Computer Science (Theoretical Computer Science and General Issues); vol. 10417).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. HPC-GAP: engineering a 21st-century High-Performance Computer algebra system

    Behrends, R., Hammond, K., Janjic, V., Konovalov, A., Linton, S. A., Loidl, H-W., Maier, P. & Trinder, P., 10 Sep 2016, In : Concurrency and Computation : Practice and Experience. 28, 13, p. 3606-3636 33 p.

    Research output: Contribution to journalArticle

ID: 241569241