Reference Counting with Reuse in Roc

Abstract

Most functional programming languages use a tracing garbage collector to automatically reclaim unused memory. But tracing garbage collection reclaims garbage memory at an un- specified time, which results in stop-the-world pauses, an increase in peak memory usage, and the inability to perform in-place mutations. Instead, a reference counting garbage collector can be used. Having the exact reference count of a structure allows for in-place mutation and the immediate reclamation of unused memory, at the cost of runtime overhead. The reference counting and reuse algorithm Counting Immutable Beans from Ullrich and de Moura attempts to reduce this overhead by borrowing references. However, their reuse imple- mentation can lead to an arbitrary increase in peak memory usage. The reference counting algorithm Perceus from Reinking et al opts for precise reference counting instead, resulting in garbage free programs. Programs that can be further improved by cancelling out matching opposite reference counting operations with drop specialisation and with the drop guided reuse algorithm from Lorenzen and Leijen. Despite both reuse algorithms showing excellent performance for simple programs, they are unable to fully utilise reuse opportunities across join points. We use Roc, a purely functional programming language, to compare the previ- ous Counting Immutable Beans implementation to an extended version of Perceus with drop guided reuse. We show that our new implementation decreases reference counting overhead, increases memory reuse, and is competitive with functional programming languages that use tracing garbage collection.