View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Reference Counting with Reuse in Roc

        Thumbnail
        View/Open
        Reference_Counting_with_Reuse_in_Roc.pdf (256.8Kb)
        Publication date
        2023
        Author
        Teeuwissen, Jelle
        Metadata
        Show full item record
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/44634
        Collections
        • Theses
        Utrecht university logo