Skip to content

Research at St Andrews

Kindergarten Cop: dynamic nursery resizing for GHC

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

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
StatePublished - 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. 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

  2. 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

  3. Lapedo: hybrid skeletons for programming heterogeneous multicore machines in Erlang

    Janjic, V., Brown, C. M. & Hammond, K. Apr 2016 Parallel Computing: On the Road to Exascale. Joubert, G. R., Leather, H., Parsons, M., Peters, F. & Sawyer, M. (eds.). IOS Press, p. 185-195 (Advances in Parallel Computing; vol. 27)

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

  4. RPL: a domain-specific language for designing and implementing parallel C++ applications

    Janjic, V., Brown, C. M., MacKenzie, K. W., Hammond, K., Danelutto, M., Aldinucci, M. & Garcia, D. J. 31 Mar 2016 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP). Cotronis, Y., Daneshtalab, M. & Papadopoulos, G. A. (eds.). Institute of Electrical and Electronics Engineers Inc., p. 288-295 7445342

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

  5. Space exploration using parallel orbits: a study in parallel symbolic computing

    Janjic, V., Brown, C. M., Neunhoeffer, M., Hammond, K., Linton, S. A. & Loidl, H-W. Sep 2013 Parallel Computing: Accelerating Computational Science and Engineering (CSE). Bader, . M., Bode, A., Bungartz, H-J., Gerndt, M., Joubert, G. R. & Peters, F. (eds.). IOS Press, Vol. 25, p. 225-232 8 p. (Advances in Parallel Computing)

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

ID: 241569241