KIT | KIT-Bibliothek | Impressum | Datenschutz

Counting Immutable Beans: Reference Counting Optimized for Purely Functional Programming [in press]

Ullrich, Sebastian; de Moura, Leonardo

Abstract:
Most functional languages rely on some garbage collection for automatic memory management. They usually eschew reference counting in favor of a tracing garbage collector, which has less bookkeeping overhead at runtime. On the other hand, having an exact reference count of each value can enable optimizations, such as destructive updates. We explore these optimization opportunities in the context of an eager, purely functional programming language. We propose a new mechanism for efficiently reclaiming memory used by nonshared values, reducing stress on the global memory allocator. We describe an approach for minimizing the number of reference counts updates using borrowed references and a heuristic for automatically inferring borrow annotations. We implemented all these techniques in a new compiler for an eager and purely functional programming language with support for multi-threading. Our preliminary experimental results demonstrate our approach is competitive and often outperforms state-of-the-art compilers.



Zugehörige Institution(en) am KIT Lehrstuhl IPD Snelting (Lehrstuhl IPD Snelting)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2019
Sprache Englisch
Identifikator KITopen-ID: 1000120596
Erschienen in 31st Symposium on Implementation and Application of Functional Languages
Veranstaltung 31st Symposium on Implementation and Application of Functional Languages (IFL 2019), Singapur, Singapur, 25.09.2019 – 27.09.2019
Externe Relationen arXiv
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page