Kindergarten cop: Dynamic nursery resizing for GHC

Henrique Ferreiro, Laura Castro, Vladimir Janjic, Kevin Hammond

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

Original languageEnglish
Title of host publicationProceedings of CC 2016
Subtitle of host publicationThe 25th International Conference on Compiler Construction
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Pages56-66
Number of pages11
ISBN (Electronic)9781450342414
DOIs
Publication statusPublished - 17 Mar 2016
Event25th International Conference on Compiler Construction, CC 2016 - Barcelona, Spain
Duration: 17 Mar 201618 Mar 2016

Conference

Conference25th International Conference on Compiler Construction, CC 2016
CountrySpain
CityBarcelona
Period17/03/1618/03/16

Keywords

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

Fingerprint Dive into the research topics of 'Kindergarten cop: Dynamic nursery resizing for GHC'. Together they form a unique fingerprint.

Cite this