Perceus: garbage free reference counting with reuse
Authors:
Open Access
- 18 June 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 96-111
Abstract
We introduce Perceus, an algorithm for precise reference counting with reuse and specialization. Starting from a functional core language with explicit control-flow, Perceus emits precise reference counting instructions such that (cycle-free) programs are _garbage free_, where only live references are retained. This enables further optimizations, like reuse analysis that allows for guaranteed in-place updates at runtime. This in turn enables a novel programming paradigm that we call _functional but in-place_ (FBIP). Much like tail-call optimization enables writing loops with regular function calls, reuse analysis enables writing in-place mutating algorithms in a purely functional way. We give a novel formalization of reference counting in a linear resource calculus, and prove that Perceus is sound and garbage free. We show evidence that Perceus, as implemented in Koka, has good performance and is competitive with other state-of-the-art memory collectors.Keywords
This publication has 32 references indexed in Scilit:
- Hazard pointers: safe memory reclamation for lock-free objectsIEEE Transactions on Parallel and Distributed Systems, 2004
- Single Assignment C: efficient support for high-level array operations in a functional settingJournal of Functional Programming, 2003
- Red-black trees in a functional settingJournal of Functional Programming, 1999
- A transformation-based optimiser for HaskellScience of Computer Programming, 1998
- The ZipperJournal of Functional Programming, 1997
- Reference counting as a computational interpretation of linear logicJournal of Functional Programming, 1996
- Morris' tree traversal algorithm reconsideredScience of Computer Programming, 1988
- An efficient, incremental, automatic garbage collectorCommunications of the ACM, 1976
- A method for overlapping and erasure of listsCommunications of the ACM, 1960
- Recursive functions of symbolic expressions and their computation by machine, Part ICommunications of the ACM, 1960