Reference Counting with Reuse in Roc
Summary
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.